Java sort polygon points

Discussion in 'Java' started by saudrey@ee.ethz.ch, Apr 16, 2008.

  1. Guest

    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
    , Apr 16, 2008
    #1
    1. Advertising

  2. Roedy Green Guest

    On Wed, 16 Apr 2008 06:40:37 -0700 (PDT), 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
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Apr 16, 2008
    #2
    1. Advertising

  3. Roedy Green Guest

    On Wed, 16 Apr 2008 19:43:05 GMT, Roedy Green
    <> 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.



    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Apr 16, 2008
    #3
  4. Roedy Green Guest

    On Wed, 16 Apr 2008 21:09:19 GMT, Roedy Green
    <> 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.

    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Apr 17, 2008
    #4
  5. Guest

    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
    , Apr 17, 2008
    #5
  6. Guest

    On Apr 17, 3:06 pm, Patricia Shanahan <> wrote:
    > 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 :( )
    , Apr 18, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    974
  2. Luis Pedro Almeida

    Convert points to polygon shapefile

    Luis Pedro Almeida, Jul 24, 2009, in forum: Python
    Replies:
    2
    Views:
    1,804
    Piet van Oostrum
    Jul 24, 2009
  3. Robert Kern

    Re: Convert points to polygon shapefile

    Robert Kern, Jul 24, 2009, in forum: Python
    Replies:
    0
    Views:
    488
    Robert Kern
    Jul 24, 2009
  4. Navin
    Replies:
    1
    Views:
    671
    Ken Schaefer
    Sep 9, 2003
  5. Serge Savoie

    java.awt.Polygon equivalent ?

    Serge Savoie, Dec 4, 2008, in forum: Ruby
    Replies:
    1
    Views:
    155
    Serge Savoie
    Dec 5, 2008
Loading...

Share This Page