Algorithm for point to edge of a polygon

[Martin]

Given that a point A is within a 2d polygon defined by a sequential series of points (non overlapping), how can I determine the location of the point on the edge of the polygon that is nearest to A?

[Andy]

how many points will there be approximately? if its not too many, why not just go through each line segament and compute the distance from that segament and A, record all of them in a struct along with the perpendicular intersection, and then find the min?

[Cervantes]

Andy's idea sounds like a nice and easy way to do it, but I think it can be easily optimized.

As you're searching, keep track of the distance with respect to the last distances. You want to find the minimum distance, so if you're searching around the polygon in a clockwise or counterclockwise fashion, then if your distance is decreasing and then all of a sudden it increases, you can bet the minimum distance is the last one. (Sort of like calculus -- finding the minimum of a function by looking at the slopes. Decreasing, decreasing, decreasing... increasing!)

Combine that with an algorithm to guess where to start and you'd be in good shape.

[md]

I dunno if this even works...

Assume you have a point A inside triangle BCD, and that point A is closest to side BC. Would length(AB) + length(CA) be smaller then both length(AC) + length(DA) and length(BA) + length(DA)? I think it might be. Then you'd just have to find the point one one of the lines. 'Course I can think of cases where the distances from two sides might be the same... however that would cause problems anyways.

It might be worth checking out to see if it even remotely works.

[Andy]

you're thinking concave polygons cervantes.. if its convex then your method will not work. think star with the point outside the central hexagon

[md]

umm... I did say triangles right?

Why in gods name anyone is using anything other then a triangle as the basic usit of a shape I don't know. With yoru star though you can easily break the star into triangles and then solve for the triangle containing the point.

[Andy]

i was refering to cervantes comment about keeping track the rate of change

[Martin]

Cornflake wrote:

umm... I did say triangles right?

Why in gods name anyone is using anything other then a triangle as the basic usit of a shape I don't know. With yoru star though you can easily break the star into triangles and then solve for the triangle containing the point.

Because lines are so much easier to work with.

[md]

lines are easily converted to triangles

I suppose I should really have said who uses anything but triangles _and_ lines. There are times when a line is all that is needed... but for filled, complex shapes triangles make things easy. Unless they are round. Then it becomes hard.

[bugzpodder]

all round objects are triangulated into a mesh or whatever, since your screen is pixilated so there is no such thing as a "round object" as long as it shows on your screen.

[NikG]

Cervantes wrote:

As you're searching, keep track of the distance with respect to the last distances. You want to find the minimum distance, so if you're searching around the polygon in a clockwise or counterclockwise fashion, then if your distance is decreasing and then all of a sudden it increases, you can bet the minimum distance is the last one

Why even worry about sudden increases in distance? Just measure the distance to all line segments from the point and keep track of the lowest one.

Untested turing code (pass the point and the polygon into this function):

code:

fcn SMALLEST_DIST_SEG (xp, yp : int, x, y : array 1 .. * of int) : int     var min_dist := Math.DistancePointLine (xp, yp, x (1), y (1), x (2), y (2))     var min_dist_seg := 1     for i : 2 .. upper (x) - 1         if Math.DistancePointLine (xp, yp, x (i), y (i), x (i + 1), y (i + 1)) < min_dist then             min_dist := Math.DistancePointLine (xp, yp, x (i), y (i), x (i + 1), y (i + 1))             min_dist_seg := i         end if     end for     result min_dist_seg end SMALLEST_DIST_SEG

Then to figure out a point on that segment (which is from i to i+1 in the polygon's array) involves some slopes and such...

[Cervantes]

NikG wrote:

Cervantes wrote:

As you're searching, keep track of the distance with respect to the last distances. You want to find the minimum distance, so if you're searching around the polygon in a clockwise or counterclockwise fashion, then if your distance is decreasing and then all of a sudden it increases, you can bet the minimum distance is the last one

Why even worry about sudden increases in distance? Just measure the distance to all line segments from the point and keep track of the lowest one.

Because doing so allows you to not test every point. If you can get some good guess work going, you could test as little as three points in a n-sided polygon.

But as Andy correctly pointed out, this only works for concave polygons.

[Panopticon]

bugzpodder wrote:

all round objects are triangulated into a mesh or whatever, since your screen is pixilated so there is no such thing as a "round object" as long as it shows on your screen.

Vector?

[Andy]

what?