I want to find the line closest to a point. The lines are finite. There's only one point. What's the most efficient way to do this?
edit:
This has a solution. See solution here.
(You would of course have to iterate over the lines and compare distances yourself.)
[Edited by - bleabox on February 9, 2010 11:28:42 PM]
Distance between line segment and point
Author
I want to find the line closest to a point. The lines are finite. There's only one point. What's the most efficient way to do this?
edit:
This has a solution. See solution here.
(You would of course have to iterate over the lines and compare distances yourself.)
[Edited by - bleabox on February 9, 2010 11:28:42 PM]
There's a recent thread here about finding the closest point which will help with optimizing the search, so all you need is a method to calculate the distance between a point and a line segment (and to add to the link, if u is outside the range [0,1] then the closest point on the line is one of the endpoints).
Hrm...
#1 - BRUTE FORCE
Well a brute force way would be to calculate the closest point on each line to the point (using dot product to project the point onto the line)
Then get the squared distance from the point to each closest point and pick the closest one.
#2 - BRUTE FORCE MADE SMARTER WITH A GRID
Another way, if you have a grid like in your image, you could store a list of what lines went through each grid square.
Then, if there are any lines in the grid cell you currently occupy, you have to only do the steps from #1 on the lines in the current grid cell and choose the closest one.
If there is only one line in your current grid cell line in your example image, you'd be able to "early out" without doing the closest point / distance check as a lil bonus.
If there aren't any lines in your current grid cell, test the 9 grid cells surrounding your grid cell and choose the closest one.
If there aren't any lines in the 9 surrounding grid cells, then test the 14 outside of that
(etc)
(:
#1 - BRUTE FORCE
Well a brute force way would be to calculate the closest point on each line to the point (using dot product to project the point onto the line)
Then get the squared distance from the point to each closest point and pick the closest one.
#2 - BRUTE FORCE MADE SMARTER WITH A GRID
Another way, if you have a grid like in your image, you could store a list of what lines went through each grid square.
Then, if there are any lines in the grid cell you currently occupy, you have to only do the steps from #1 on the lines in the current grid cell and choose the closest one.
If there is only one line in your current grid cell line in your example image, you'd be able to "early out" without doing the closest point / distance check as a lil bonus.
If there aren't any lines in your current grid cell, test the 9 grid cells surrounding your grid cell and choose the closest one.
If there aren't any lines in the 9 surrounding grid cells, then test the 14 outside of that
(etc)
(:
Author
Quote:Original post by Atrix256
#1 - BRUTE FORCE
(:
I'm having problem with this. I've been googling a lot, and every solution I find either doesn't work properly (i.e. suggests wrong lines to be closest) or is not applicable to line segments, only infinite lines.
I thought this was pretty basic. :p Yet it is easier to find and make a polygon triangulation method than this, lol.
It looks like this page has some code to do it
http://www.codeguru.com/forum/showthread.php?threadid=194400
they argue afterwords about whether the code should be branching or not but it looks like nobody is disputing that the source code works (they dispute that the alternate non branch method works but who cares...) :P
http://www.codeguru.com/forum/showthread.php?threadid=194400
they argue afterwords about whether the code should be branching or not but it looks like nobody is disputing that the source code works (they dispute that the alternate non branch method works but who cares...) :P
oh hey, this actually looks like a more informative article:
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
in there, they calculate u which is "how far from point A to point B does the closest point lie (in percent of total line distance)".
If it's between A and B, u will be in the range of 0 to 1.
so..
after you calculate u, just do this...
if(u < 0.0f)
u = 0.0f;
else if(u > 1.0f)
u = 1.0f;
then plug u into the equation like you would normally and it will give you the closest point to the line SEGMENT instead of infinite line.
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
in there, they calculate u which is "how far from point A to point B does the closest point lie (in percent of total line distance)".
If it's between A and B, u will be in the range of 0 to 1.
so..
after you calculate u, just do this...
if(u < 0.0f)
u = 0.0f;
else if(u > 1.0f)
u = 1.0f;
then plug u into the equation like you would normally and it will give you the closest point to the line SEGMENT instead of infinite line.
Author
What does the double || || mean?
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/pointline2.gif
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/pointline2.gif
The thing with limiting to segments is to consider one particular parameter.
You basically need to find the intersection of a segment, and a ray that goes from your point in the normal direction to the segment (it would eventually hit the so called foot point on the line the segment lies on).
Let your segment be defined by points A and B, and Vs := (B-A). Also let P be your point and N the normal to the segment (N := norm(-Vsy, Vsx) if Vsx != 0, else negate Vsy).
Your two lines then are:
L1 := A + t*Vs
L2 := P + s*N
Find their intersection by setting L1 = L2, and solve for t. If then t is not in the range of [0, 1], then the nearest one of A and B is the actual segment's distance, since a ray going from P will never hit the segment perpendicular. If t is in [0, 1], your intersection is of course given by setting t in it's line equation, and that point's distance is the actual distance to P.
You basically need to find the intersection of a segment, and a ray that goes from your point in the normal direction to the segment (it would eventually hit the so called foot point on the line the segment lies on).
Let your segment be defined by points A and B, and Vs := (B-A). Also let P be your point and N the normal to the segment (N := norm(-Vsy, Vsx) if Vsx != 0, else negate Vsy).
Your two lines then are:
L1 := A + t*Vs
L2 := P + s*N
Find their intersection by setting L1 = L2, and solve for t. If then t is not in the range of [0, 1], then the nearest one of A and B is the actual segment's distance, since a ray going from P will never hit the segment perpendicular. If t is in [0, 1], your intersection is of course given by setting t in it's line equation, and that point's distance is the actual distance to P.
Quote:Original post by bleabox
What does the double || || mean?
http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/pointline2.gif
it's just absolute value.
||x||
is the same as
fabs(x)
Author
Python
Here you go, internet!
Shortest distance between a line SEGMENT and a point.
Thanks for the help.
[Edited by - bleabox on February 10, 2010 9:44:40 AM]
import mathdef dist(x1,y1, x2,y2, x3,y3): # x3,y3 is the point px = x2-x1 py = y2-y1 something = px*px + py*py u = ((x3 - x1) * px + (y3 - y1) * py) / something if u > 1: u = 1 elif u < 0: u = 0 x = x1 + u * px y = y1 + u * py dx = x - x3 dy = y - y3 # Note: If the actual distance does not matter, # if you only want to compare what this function # returns to other results of this function, you # can just return the squared distance instead # (i.e. remove the sqrt) to gain a little performance dist = math.sqrt(dx*dx + dy*dy) return distHere you go, internet!
Shortest distance between a line SEGMENT and a point.
Thanks for the help.
[Edited by - bleabox on February 10, 2010 9:44:40 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
