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?