
Signature
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
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 :( )