Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / April 2008

Tip: Looking for answers? Try searching our database.

Java sort polygon points

Thread view: 
saudrey@ee.ethz.ch - 16 Apr 2008 14:40 GMT
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
Peter Duniho - 16 Apr 2008 17:36 GMT
> 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?

1) If you have z coordinates, then you may not have a polygon.  Are you  
sure that the points all lie in the same plane?

2) In three dimensions, "clockwise" and "counter-clockwise" don't really  
mean much without a specific reference point, since you could view the  
polygon from either side.

2) If the points represent a polygon, then they must already be ordered.  
You're not looking for a way to sort them, but rather a way to figure out  
whether they are already in clockwise order, and if not then you know to  
reverse their order so that they are.

As far as the actual approach, here's one possible solution: you can use  
vector dot and cross products to determine a signed angle between segments  
of your polygon (dot product can tell you the angle, cross product can  
tell you which direction/sign).  Arbitrarily assign positive angles as one  
direction and negative angles as the other (left or right, clockwise or  
counter-clockwise).  Then add all of the angles for each apex of the  
polygon.  The sign of the final sum will tell you whether the polygon is  
clockwise or counter-clockwise.

That may or may not be the most efficient solution.

Not that any of this has anything to do with Java.  If the above doesn't  
give you enough information, I recommend doing some research on your own.  
Or ask your teacher.  :)

Pete
Roedy Green - 16 Apr 2008 20:43 GMT
>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
Signature


Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Roedy Green - 16 Apr 2008 22:09 GMT
On Wed, 16 Apr 2008 19:43:05 GMT, Roedy Green
<see_website@mindprod.com.invalid> 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.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Roedy Green - 17 Apr 2008 01:08 GMT
On Wed, 16 Apr 2008 21:09:19 GMT, Roedy Green
<see_website@mindprod.com.invalid> 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.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

saudrey@ee.ethz.ch - 17 Apr 2008 09:28 GMT
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
Patricia Shanahan - 17 Apr 2008 14:06 GMT
...
> What my program is supposed to do is to analyze lines you draw by
> hand. It should detect intersections, the angles between the lines
[quoted text clipped - 5 lines]
> 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
saudrey@ee.ethz.ch - 18 Apr 2008 17:21 GMT
> saud...@ee.ethz.ch wrote:
>
[quoted text clipped - 23 lines]
>
> Patricia

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


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.