Jump to content
  • Advertisement
Sign in to follow this  
bleabox

Distance between line segment and point

This topic is 3081 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!