Closest point pair between BoundingBox and infinite Line

Rhino Developer
1

Does anyone know a fast way to measure the distance between a world oriented box (ON_BoundingBox or BoundingBox) and an infinite line? If the line intersects the box, I need a distance of zero.

Best I could come up with is bouncing a point back and forth between the line and the box using closest point methods until the point remains the same, but this could take many iterations if the line is nearly parallel to one of the box edges.

2

Hi David, first I’d check if the line intersects the box. If not I’d go for Intersection.LineLine with the edges and the line. This method returns the closest point between two lines. Maybe you can optimize by finding the probable edges?

3

shouldn’t _ClosestPt do this? (or rs.CurveClosestObject)

it seems like it should but i keep getting a crash on mac when trying anything other than a line/line or line/surface intersection… does it crash on windows too?

the prompt and help at least imply it should work between a line&multiple lines or a line&polysurface…
(but either way, it still shouldn’t be crashing if i try multiple lines against a line… i’ll report that separately)

edit- that said, i suppose even if it didn’t crash, it still wouldn’t work on an infinite line so nevermind… : )

4

Looking at this page http://geomalgorithms.com/a07-_distance.html#dist3D_Segment_to_Segment

I would compute the shortest distance between the line and each of the 8 (infinite) lines that represent the edges of the bounding box. Each line is characterized as L = P0 + t(P1-P0) so that the t-interval [0,1] describes the edge. Then check if the parameter found on the edges is in [0,1] or not for all edges. If all edges of a face report their parameter in [0,1], the line intersects the face.

If no face is intersected: for each edge that has its parameter outside [0,1], use the closest-point algorithm for both vertices P0 and P1 to the line and decide which one is closer.

There are probably some details where the line intersects a vertex or an edge within the desired tolerance.

5

Also, there is ON_BoundingBox::GetClosestPoint that seems to do what you want.

  // Description:
  //   Get point in a bounding box that is closest to a line
  //   segment.
  // Parameters:
  //   line - [in] line segment
  //   box_point - [out] point in box that is closest to line
  //       segment point at t0.
  //   t0 - [out] parameter of point on line that is closest to
  //       the box.
  //   t1 - [out] parameter of point on line that is closest to
  //       the box.
  // Returns:
  //   3 success - line segments intersects box in a segment
  //               from line(t0) to line(t1) (t0 < t1)
  //   2 success - line segments intersects box in a single point
  //               at line(t0) (t0==t1)
  //   1 success - line segment does not intersect box.  Closest
  //               point on the line is at line(t0) (t0==t1)
  //   0 failure - box is invalid.
  // Remarks:
  //   The box is treated as a solid box.  If the intersection
  //   of the line segment, then 3 is returned.
  int GetClosestPoint( 
    const ON_Line&, // line
    ON_3dPoint&,    // box_point
    double*,        // t0
    double*         // t1
    ) const;
6

any way to scramble python scripts so other people can’t see them? :smile:
(like the brute force extending of the line and other non-elegant solutions)

import rhinoscriptsyntax as rs

def closest(b, xline):
    l1=rs.AddLine(b[0],b[1])
    l2=rs.AddLine(b[1],b[2])
    l3=rs.AddLine(b[2],b[3])
    l4=rs.AddLine(b[3],b[0])
    l5=rs.AddLine(b[4],b[5])
    l6=rs.AddLine(b[5],b[6])
    l7=rs.AddLine(b[6],b[7])
    l8=rs.AddLine(b[7],b[4])
    l9=rs.AddLine(b[0],b[4])
    l10=rs.AddLine(b[1],b[5])
    l11=rs.AddLine(b[2],b[6])
    l12=rs.AddLine(b[3],b[7])

    blines=[l1,l2,l3,l4,l5,l6,l7,l8,l9,l10,l11,l12]
    distlist=[]

    for i in range (0,12):
        cco= rs.CurveClosestObject(xline, blines[i])
        dist = rs.Distance(cco[1],cco[2])
        distlist.append(dist)

    shortest = distlist.index(min(distlist))
    theone= blines.pop(shortest)
    thex= rs.CurveClosestObject(theone, xline)

    shrtdist= rs.Distance(thex[1],thex[2])
    rs.AddPoint(thex[1])
    rs.AddPoint(thex[2])

    print "Shortest Distance = "+str(shrtdist)
    rs.DeleteObject(xline)
    rs.DeleteObjects(blines)


def input():
    object = rs.GetObject("Select object")
    if not object: return
    b = rs.BoundingBox(object)

    line=rs.GetObject("select line",4)
    if not line: return
    if not rs.IsCurveLinear(line): return
    xline = rs.CopyObject(line)
    xline = rs.ExtendCurveLength(xline,0,2,10000)
    
    box= rs.AddBox(b)
    cbx= rs.CurveBrepIntersect (xline, box)
    if cbx:
        print 'Distance = 0'
        rs.DeleteObject(xline)
        return
    closest(b, xline)

input()

it’s not really checking for much… probably won’t work if the object being bounded isn’t 3D… probably also won’t work if the object and lines are super far away from each other.

seems to work otherwise.

7

he needs that to work with an infinite line…
regardless, i think it’s probably the much better path to go down than how i went about it.

8

Isn’t that just checking the points of the BoundingBox? If so then one has to check the line-line intersection with the finite segment option of course.

9

ON_BoundingBox::GetClosestPoint it says line segment in the documentation - my bad for not reading properly :frowning:

10

Yeah that seems to be the ideal function to use. I can’t find it in the RhinoCommon SDK though. Suppose I’d better add it.

11

Seems like the best approach. Thanks.