Connecting an arbitrary list of points

I have an arbitrary list of coordinates that I know represent the boundary of a polygon. Is there some sort of function from the contouring or path codes that would allow me to pass in that list and get back the resorted list with the path codes with it?

Thanks,
Ben Root

From: Benjamin Root [mailto:ben.root@…1304…]
Sent: Friday, August 19, 2011 13:43

I have an arbitrary list of coordinates that I know represent the boundary of a polygon. Is there some sort of function from the contouring or path codes that would allow me to pass in that list and get back the resorted list with the path codes with it?

Hi, Ben. Is it the order of the points around the polygon that is unknown, and is it unambiguous because the polygon is known to be convex? If so, I believe you could use part of the Graham scan [1] convex hull algorithm. The function you need would find the point P with the lowest Y coordinate, then sort the remaining points by the cosine of the angle they and P make with the X axis. After that, the list comprising P and the sorted points would need the path codes.

If the polygon is concave but the order is somehow clear (e.g., a radial progression about the average coordinate), you might be able to adapt the method. I hope I understood your problem correctly and that this helps.

[1] http://en.wikipedia.org/wiki/Graham_scan

Actually, that might be useful. The current solution I have is to use the core contouring function in mpl to generate paths, but they doesn’t seem to guarantee either clockwise or counter-clockwise traversals.

Does graham scan guarantee something like that? I need to calculate outward-facing normal vectors.

Ben Root

···

On Friday, August 26, 2011, Stan West <stan.west@…706…> wrote:

From: Benjamin Root [mailto:ben.root@…1304…]
Sent: Friday, August 19, 2011 13:43

I have an arbitrary list of coordinates that I know represent the boundary of a polygon. Is there some sort of function from the contouring or path codes that would allow me to pass in that list and get back the resorted list with the path codes with it?

Hi, Ben. Is it the order of the points around the polygon that is unknown, and is it unambiguous because the polygon is known to be convex? If so, I believe you could use part of the Graham scan [1] convex hull algorithm. The function you need would find the point P with the lowest Y coordinate, then sort the remaining points by the cosine of the angle they and P make with the X axis. After that, the list comprising P and the sorted points would need the path codes.

If the polygon is concave but the order is somehow clear (e.g., a radial progression about the average coordinate), you might be able to adapt the method. I hope I understood your problem correctly and that this helps.

[1] http://en.wikipedia.org/wiki/Graham_scan

From: ben.v.root@…287… [mailto:ben.v.root@…1972…] On Behalf Of Benjamin Root
Sent: Friday, August 26, 2011 13:11

Actually, that might be useful. The current solution I have is to use the core contouring function in mpl to generate paths, but they doesn’t seem to guarantee either clockwise or counter-clockwise traversals.

Does graham scan guarantee something like that? I need to calculate outward-facing normal vectors.

The points would be traversed in radial order from P’s vantage, as if a radar sweep numbered each point as it passed by. I suppose that if the points form a convex polygon, then that traversal order is the same one that would result from anywhere in the interior, and it would be unambiguously clockwise or counter-clockwise depending on the sort order. (You might have to handle the case in which P and two or more other points are colinear by breaking the tie in the sort appropriately.) If the points form a concave polygon—that is, if one or more points lie inside the convex hull of the points—then I suppose you would need additional constraints or information to choose where those points should fall in the traversal order.

I’m glad the method might help.