Java sort polygon points

[saudrey]

hey,

I have the following problem:
I have a list of all the x, y and z coordinates of a polygon's points.
I now need to sort them in such a way that I obtain the points in a
clockwise order.
Does anyone know how to accomplish that?

Thanks in advance,

Audrey

 

[Roedy Green]

I have the following problem:
I have a list of all the x, y and z coordinates of a polygon's points.
I now need to sort them in such a way that I obtain the points in a
clockwise order.
Does anyone know how to accomplish that?

see http://mindprod.com/jgloss/sort.html

If the class that describes the points does not support a natural
Comparable ordering, extend the class and write one, or implement an
Comparator. see http://mindprod.com/jgloss/comparable.html
http://mindprod.com/jgloss/comparator.html

 

[Roedy Green]

see http://mindprod.com/jgloss/sort.html

If the class that describes the points does not support a natural
Comparable ordering, extend the class and write one, or implement an
Comparator. see http://mindprod.com/jgloss/comparable.html
http://mindprod.com/jgloss/comparator.html

To determine clockwise order you might use a hanging moss algorithm
to find a line segment that leaves from the current spot.
http://mindprod.com/jgloss/hangingmoss.html

If you allow absolutely no slop, i.e. have integral co-ordinates and
insist on the next segment leaving from precisely where the previous
left off, you can so something simpler.

Create two HashMaps,'a's and 'b's. Put the start endpoints in one and
the end endpoints in the other.

Make up some arbitrary rule to decide which end is the A and B end.

Then look in both the a and b hashmap for a match to the current
point. You will find two points, yourself and one other (if this is
indeed a closed polygon). You know where you are, so you only need
look in the other set. (A toggle boolean might be helpful).

This presumes that no three line segments meet at a common point.

Chase the segments until you get back where you started.

When done do the test in your textbook to determine if what you have
is clockwise. If not, reverse it.

 

[Roedy Green]

If you allow absolutely no slop, i.e. have integral co-ordinates and
insist on the next segment leaving from precisely where the previous
left off, you can so something simpler.

If you have only a small number of points, N (to be determined by
experiment, but my gut says probably N > 100 ), you can create a
linear array of unsorted segment objects, and repeatedly scan the list
looking for a matching point with either end.

 

[saudrey]

Thank you all for your answers. I think I'll try the HashMaps idea, it
sounds easy to implement

Maybe I should have been a little more specific, because I didn't
mention that it doesn't matter if the points are in clockwise or
counterclockwise direction, as log as they all follow the same
direction.

What my program is supposed to do is to analyze lines you draw by
hand. It should detect intersections, the angles between the lines
intersecting and also detect if a polygon has been completed
(totalAngle == (nrIntersections-2)*180). I have gotten up to this
point, so I now detect if a polygon has been closed and i have a list
of all the points making up the polygon. what I now wanted to do is
fill the polygons area instead of only having the corner points. If I
don't pass the points in a sequential order though the polygon isn't
filled properly...

So I guess it should be fairly easy to just use the HashMaps method.

Thanks again for your answers

 

[saudrey]

(e-mail address removed) wrote:

...> What my program is supposed to do is to analyze lines you draw by

...

In that case, I think you need to look at the lines, not just the
points, because looking only at the points introduces ambiguity and
makes the problem harder. Unless you know the polygon has a nice
property such as being convex, there may be more than one polygon using
the same set of points.

For example, consider the corners of a square and the center point.
There are four polygons that can be produced by replacing one edge of
the square with a pair of lines connecting the center to the ends of the
edge. All are equally valid solutions to point-based problem, but
presumably the original lines tell you which one to use.

Patricia

Thanks, that's exactly what i did and it works perfectly (even though
the code got rather long )