Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Java sort polygon points

Reply
Thread Tools

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?

Thanks in advance,

Audrey
 
Reply With Quote
 
 
 
 
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
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
 
 
 
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.



--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
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.

--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
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.

Thanks again for your answers
 
Reply With Quote
 
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 )
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Convert points to polygon shapefile Robert Kern Python 0 07-24-2009 07:01 PM
Convert points to polygon shapefile Luis Pedro Almeida Python 2 07-24-2009 12:14 PM
java.awt.Polygon equivalent ? Serge Savoie Ruby 1 12-05-2008 05:29 PM
Strange problem intersecting java.awt.Polygon 418928@cepsz.unizar.es Java 4 11-13-2007 12:11 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM



Advertisments