Velocity Reviews > Java > Java sort polygon points

# Java sort polygon points

saudrey@ee.ethz.ch
Guest
Posts: n/a

 04-16-2008
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?

Audrey

Roedy Green
Guest
Posts: n/a

 04-16-2008
On Wed, 16 Apr 2008 06:40:37 -0700 (PDT), http://www.velocityreviews.com/forums/(E-Mail Removed) wrote,
quoted or indirectly quoted someone who said :

>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
--

The Java Glossary
http://mindprod.com

Roedy Green
Guest
Posts: n/a

 04-16-2008
On Wed, 16 Apr 2008 19:43:05 GMT, Roedy Green
<(E-Mail Removed)> wrote, quoted or indirectly quoted
someone who said :

>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.

--

The Java Glossary
http://mindprod.com

Roedy Green
Guest
Posts: n/a

 04-17-2008
On Wed, 16 Apr 2008 21:09:19 GMT, Roedy Green
<(E-Mail Removed)> wrote, quoted or indirectly quoted
someone who said :

>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.

--

The Java Glossary
http://mindprod.com

saudrey@ee.ethz.ch
Guest
Posts: n/a

 04-17-2008
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.

saudrey@ee.ethz.ch
Guest
Posts: n/a

 04-18-2008
On Apr 17, 3:06 pm, Patricia Shanahan <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
>
> ...> 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...

>
> ...
>
> 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 )