Sign in to follow this  
bleabox

Distance between line segment and point

Recommended Posts

bleabox    100
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]

Share this post


Link to post
Share on other sites
Zipster    2365
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).

Share this post


Link to post
Share on other sites
Atrix256    539
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)

(:

Share this post


Link to post
Share on other sites
bleabox    100
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.

Share this post


Link to post
Share on other sites
Atrix256    539
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

Share this post


Link to post
Share on other sites
Atrix256    539
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.

Share this post


Link to post
Share on other sites
Medium9    192
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.

Share this post


Link to post
Share on other sites
Atrix256    539
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)

Share this post


Link to post
Share on other sites
bleabox    100
Python

import math

def 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 dist



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]

Share this post


Link to post
Share on other sites
Atrix256    539
Hey btw, i was thinking about the grid solution some more and it won't actually work as i laid it out.

The reason is, the point you are testing could be right against a cell edge and in the next cell over there could be a line really close to the edge (close to the point) and in the current cell edge there could be a line near the far edge of cell.

Using the method i said it would incorrectly say the line in the current grid cell was the closest.

The brute force method i said should work, and you could use a grid to optimize your search, just not in the way i laid it out.

sorry about that!

Share this post


Link to post
Share on other sites
bleabox    100
I actually never have to try this against more than 8 lines at a time, so it doesn't really matter for me. :) Doing brute force everytime works just fine..

[Edited by - bleabox on February 9, 2010 9:44:28 PM]

Share this post


Link to post
Share on other sites
Medium9    192
The method you found looks interesting! I haven't yet checked it's validity, but from the looks it seems reasonable. Can you confirm that it's working?

A slight improvement: It's a bit pointless to calculate the magnitude if you're only going to use it's square. With just eight segments this probably won't do much, but a sqrt and a mul can be spared there.
Also, x2-x1 and y2-y1 are done twice. We can reuse px and py in the equations for x and y.

I might be able to speed up some project of mine with this... thanks :)

Share this post


Link to post
Share on other sites
bleabox    100
I haven't done any unit testing, I just put it right into my game and it works fine (unlike everything else I've tried, especially from here http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment (though I added this method there now)).

Yeah, I'm extremely lazy with optimization. :p As long as it works, it's fine is my motto. I use ugly hacks all the time instead of making elegant solutions, unless I'm really forced to because of performance issues or complexity that otherwise would be added. (Though hacks vs elegant solution is usually complexity vs effort. Sometimes it just isn't worth the effort, and other times you wish you would've thought things through a little bit more before resorting to hacking. :p)

I don't even know what I'm doing here. I just tried to follow that page someone linked to (http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/) the best I could, and it seems to work. And once I got it to work, I didn't even think twice about actually improving the code somehow. I can see now that it indeed does some silly things and has some redundancy.

edit:
I edited the function. Maybe I missed something.

[Edited by - bleabox on February 9, 2010 11:52:11 PM]

Share this post


Link to post
Share on other sites
Atrix256    539
Quote:
Original post by bleabox
Yeah, I'm extremely lazy with optimization. :p As long as it works, it's fine is my motto


That is the correct attitude (:

You shouldn't optimize until you profile and find out what the bottleneck in your game is.

also macro optimizations pwn micro optimizations most of the time.

That means, changing your strategy will be bigger win 99% of the time, removing multiplies and square roots will be the correct thing just 1% of the time (made up statistics but you get what i mean) :P

EDIT: btw tho if you wanna do another micro optimization, where you do a square root at the end to get the distance, you could make this function return the SQUARED distance and save yourself another square root. Comparing squared distances will give you the same result as comparing real distances.

But yeah, with the number of lines you have im sure this isn't a big preformance hit hehe (:

Share this post


Link to post
Share on other sites
Medium9    192
While it's true that better strategies almost always lead to the biggest improvements, I still try to go as far as I don't destroy readability and as long as I don't burn hours on it. That way, I can really be sure, that it's my method in general that's flawed.
Howerver in this case, the difference reall IS tiiiny. I still got these urges though =D

The method works fine by the way, but didn't help much with speed in my case, since I already have a surrounding algo that partitions space, and it misses one option for an early-out that my old method had, leaving me with more operations in the end.

Still an interesting approach!

Share this post


Link to post
Share on other sites
bleabox    100
Quote:
Original post by Atrix256EDIT: btw tho if you wanna do another micro optimization, where you do a square root at the end to get the distance, you could make this function return the SQUARED distance and save yourself another square root. Comparing squared distances will give you the same result as comparing real distances.


Ah, this is true. Though I'm going to leave it as it is, so when someone googles this on the internet, they will indeed find a function that does return the actual distance, without having to read an entire thread and finding out that the distance returned is actually squared. I can however put a note in the code to point this out. Thanks!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this