Seems a common question in linear algebra circles, but having trouble getting a working solution. Anyone have a rhinocommon approach to solving this? Most approaches are least squares fit and I haven’t found a good one(my matlab’s a little rusty). In my case I have 4 planes, and the “lines” are actually the normal vectors, but its the same problem. Also can think of it as the best fit intersection of the lines.
can you provide a visual example of the problem?
or maybe re-explain it?
i’m having trouble understanding the goal.
So we have four infinite lines, none mutually parallel(or else there is probably no solution). At some point in space, the distance(sum of the squares is fine) to each line is at minimum. For two lines its easy, Curve.ClosestPoints. Multiple lines, from all the online posts, requires solving a matrix. I am not against that, if someone can help a bit. I found a pretty good matlab program for it but its hard to translate to c#(python would be fine as well). I will probably use a math lib (math.net or accord.net) to do it once I understand how it works. Or if there really is a trick using some rhino methods that would be ideal…I don’t need super high speed for this…there will typically only be 4 lines.
ok, thanks… i understand now 
i don’t have time to try some things right now… i’ll try later if no one has posted a solution yet.
something like this should do it:
import rhinoscriptsyntax as rs
lines = rs.GetObjects('pick lines')
dlist = []
for l in lines:
if len(lines) > 1:
line = lines.pop(0)
pts = rs.CurveClosestObject(line, lines)
distance = rs.Distance(pts[1], pts[2])
dlist.append([distance, pts[1], pts[2]])
dlist.sort()
pt1 = rs.AddPoint(dlist[0][1])
pt2 = rs.AddPoint(dlist[0][2])
rs.AddLine(pt1, pt2)
(missing some needed checks/formatting/etc but this is the basic… nothing in place to deal with multiple intersecting lines (more than 1 distance of zero, or other instances of distances being equal)) but that should be fairly easy to add)
it’s using list.pop …
so it removes one item from the list then compares it to all the others left in the list using rs.CurveClosestObject() …then keeps doing that until there aren’t any objects left in the list.
Hmm,
Still not the right question I guess. That seems to solve for the point on each of the “two” closest together lines (of the set)…the answer to this won’t be on any of the lines. I think it should be somewhere “in the middle of them”. I’ll try to draw it…admittedly there may be a flaw in the assumption…
heh, right… it finds the closest distance between all of the curves then tells which is the shortest of these.
so you’re looking for a single point which is closest to all of the curves in the set? for example:
the black lines are the original lines… then out of the green set and red, you’d rather the green since the cumulative length is 221 whereas for red, it’s 328… and you’re looking for the point location that will result in the smallest cumulative length possible?
is that closer to what you’re after?
I think so, but I am also stuck drawing it. The lines are infinite, but your example would still be valid. I am wondering if there is another convention. I am attaching a file that illustrates a solution. The green/red are coord planes(known, origin and orientation, so your line above should just be the Z axis of my plane). The black line/point is the solution(which is just the location of the point in local coords of any plane). In this case if you orient the black line to each plane, they will intersect at the point. But in the application case, it should be a best fit, so they won’t intersect perfectly.
Edit:So I think its just the best fit sphere of the plane origins(well with 4 pts I think there is only one possible sphere. I tried this a few days ago but wasn’t convinced. I am still not totally convinced; I will try to setup a test with the physical device that uses this technique(in a black box way). Somehow the real alg also gives an error margin, but I don’t see where that would be produced here.
testprob.3dm (160.1 KB)
Hi Wes,
hope this python script does what you need:
Edit: Note, the lines do not really have to intersect. LineLIneIntersect will find “intersections” if the lines have a “minimum distance” i.e. are not parallel.
#Script to find the closest point between lines
#Jess Maertterer - 3DE, July 2016
import itertools
import rhinoscriptsyntax as rs
def LinesClosestPoint(lines):
pts = []
sumPt = [0,0,0]
for a, b in itertools.combinations(lines, 2):
lineA = [rs.CurveStartPoint(a),rs.CurveEndPoint(a)]
lineB = [rs.CurveStartPoint(b),rs.CurveEndPoint(b)]
llx = rs.LineLineIntersection(lineA,lineB)
if llx:
pts.append(llx[0])
pts.append(llx[1])
sumPt = rs.PointAdd(sumPt,llx[0])
sumPt = rs.PointAdd(sumPt,llx[1])
if pts:
#rs.AddPoints(pts)
ctr = rs.PointDivide(sumPt,len(pts))
return rs.AddPoint(ctr)
else: print "No intersections found!"
if __name__=="__main__":
def linearCrvs(rhino_object, geometry, component_index):
return rs.IsCurveLinear(rhino_object)
lines = rs.GetObjects("Select lines",4,True,custom_filter=linearCrvs)
if lines:
cp = LinesClosestPoint(lines)
if cp: rs.SelectObject(cp)
Jess
The center of a sphere through 4 points will be equidistant from the 4 points, but in general will not be the point which is closest to the 4 points.
How are you defining “closest” point? The point with the smallest sum of the distances from the point to each line? The point with the smallest sum of the squares of the distances from the point to the each line? Or something else?
The sum of the squares (least squares) is a common choice for several reasons. It makes the largest deviation more significant, and mathematically it can be expressed as the solution of set of linear algebraic equations which will usually have a unique solution . For a point in 3D space it would be a set of three equations for the three point coordinates.
Yes, I don’t want the point closest to the 4 points. I want the point closest to the “imaginary” intersection (as they will not really intersect due to errors in the input) Zaxes of the 4 planes. The sphere passes through the origins of those 4 planes, and its center seems to be the right answer. I am going to test it a bit today, against the baseline system.
Actually it seems the sphere is only working in certain cases, and in others very wrong…hmm.
Apparently the sphere approach fails if the 4pts (plane origins) are in plane(makes sense!) So maybe this is OK as that should never happen.
What’s wrong with my solution?
ah I just saw your edit about the linelineIntersection command. I was not aware that it would give a closest intersect to non parallel lines. I will try that.
Hmm,
Doesn’t seem to be working for what I am trying to do(nothing wrong with your approach, I may still be asking the wrong question). Maybe if I show you the general case(file attached). I want to solve for the black line(all 4 of these plane/line pairs are the same, randomly arrayed around the unknown point). The only known values are the planes(defined by the x/y axes provided).
Any ides?testprob.3dm (164.4 KB)
Hmm,
the “sphere approach” solves a different problem than the “imaginary intersection”. I think you want the intersection but it is hard to come up with the solution without knowing the context (where the plane normal come from).
Does the attached makes sense in your context?
testprob_jm.3dm (170.7 KB)
@wes_mcgee_3d What are you trying to accomplish? If you want the closest point in the least squares sense to the lines then the location of planes intersecting the lines is totally irrelevant. The planes can be located anywhere along the lines without affecting the closest point.
If you want the point closest in the least squares sense to a set of points then that is different problem. That corresponds to the volume centroid of the points with an arbitrary but equal volume/mass assigned to each point. One way to solve for this in Rhino is to place a spheres of arbitrary radius centered at each point, and then use VolumeCentroid on the set of spheres. Make sure the spheres are all the same size and are centered on the points. The spheres can overlap as long as they are not trimmed.
As I mentioned above the center of a sphere passing through 4 points is the point equidistant from the 4 points, not the point closest to the 4 points.
Its hard to say; initially to me the black lines are totally unknown. When I was suggesting to use the nearest intersection, I was planning to use it “on” the Zaxes of these planes. The planes are the inputs. I have a positioning system that tells me where the planes are in 3d. I have scanner that tells me where the “imaginary intersection pt” is relative to the Plane. I don’t know the actual location of the imaginary point yet, nor do I know the homogenous transform from the sensor coords to the Plane. In another application, the positioning system is manually positioned such that it approximates a fixed point (physically)(though including an unknown rigid transform).
In the file “testprob” you can see the black line which represents an unknown homogenous transform between the plane(green red lines) and the unknown point. I want the transform (though I only care, and can only solve for the, translation part). I only know the 4 planes. I am using the black line to illustrate, but its not known initially. In the case of the file, the transform is the same for every plane, but in the real case there will be errors in the locations of the planes…so I want the best fitting transform.
Edit: I am starting to think that the initial problem was not the correct one, so don’t limit your thinking to the two cases you mentioned(neither of those is what I want, sorry for the misdirection).