While We're on the Subject of Polygons...
Author Message
While We're on the Subject of Polygons...

This probably doesn't strictly pertain to this newsgoup, but I was reminded of
this problem by the "Bounds Checking for Point Inside a Polygon" thread.

Suppose you have a list of points which are known to be the vertices of a
convex (but possibly irregular) polygon.  The points, however, are in no
particular order.  How would one go about sorting the points in a clockwise or
counterclockwise direction around the polygon?  (This is important, because
functions that deal with polygons typically require the vertex list in a
particular order.)  Any ideas out there?

Mon, 17 Jul 2000 03:00:00 GMT
While We're on the Subject of Polygons...

First of all determine the topmost and bottommost points (Y value). I would
then move to the topmose point. Cycel thorugh the points and ignore all
points to the left of the current point. Find the point (from this subset)
that has the highes Y value (if some have the same Y value, pick the one
closest to by the X value).

Anyway, contine to do this till you run out of the points within the
subgroup. Now use the last point of the subgroup and go through the
remaining points by the Y value again, but this time reverse the logic (go
from bootom to top instead of top to bottom).

This is explained crude, but when coding it, there finished routine would
actually be quite small.

This is one way that does take a math wizard to perform.

Greg

Tue, 18 Jul 2000 03:00:00 GMT
While We're on the Subject of Polygons...

Here is how I would do it:

Find a vertice with the minimum x value.
Sort the vertices by the slope of the line
connecting the min x vertice.

Jeff Hack

ie:

'find point with minimum x value
'becomes xs,ys
'--put code here --

For i = 0 To numPts - 1
dx = xs - p(i).x
dy = ys - p(i).y
If dx = 0 Then
If dy = 0 Then
m = -100000
Else
m = Sgn(dy) * (100000 - Abs(dy))
End If
Else
m = dy / dx
End If

'Insert into output list by m value
'--put code here --

Next

Quote:
>That *almost* works.  But if I understand your message correctly, it would
>fail
>on a polygon like the one in the attached bitmap.  Your message pointed me in
>the right direction, though.  Here's a revised algorithm:

>=======================

>Sort the input list of points from highest Y value to lowest Y value.  In the
>case of identical Y values, lower X values go first.  Remove the first and
>last
>elements from this list (the topmost and bottommost points, respectively) and
>store them in an output list.

>Step through the remaining points in the input list (in order) and test the
>position of each one relative to a line through the topmost and bottommost
>points [PointPos = ToLeft/Collinear/ToRight].  Keep a tally of the number of
>points found for each of the three cases [ToLeftTotal, CollinearTotal,
>ToRightTotal].  If PointPos = ToRight, remove the point from the input list
>and
>insert it into the output list immediately before the bottommost point.

>If ToRightTotal = 0 and CollinearTotal > 0, step through the input list
>again,
>this time moving points from the input list to the output list when PointPos
>=
>Collinear.  (Again, immediately before the bottommost point in the output
>list.)

>Finally, step through what remains of the input list in reverse order,
>appending each point to the end of the output list.

>=======================

>Can anyone think of a better algorithm?

Tue, 18 Jul 2000 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages