# 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.

## 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 on other sites
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 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 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 on other sites

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 on other sites

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 on other sites
What does the double || || mean?

http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/pointline2.gif

##### 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).

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 on other sites
Quote:
 Original post by bleaboxWhat 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 on other sites
Python

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

1. 1
Rutin
24
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 46
• 41
• 23
• 13
• ### Forum Statistics

• Total Topics
631749
• Total Posts
3002031
×