Checking CLOCKWISELY defined polygon??

Checking CLOCKWISELY defined polygon??

Post by Chan Lap Wah Sams » Wed, 15 Dec 1993 21:50:55



Hi,

I want to know if there is any method to check if *any* polygon,
represented by points, can be checked if it is clockwisely
defined or anti-clockwise.

Actually, I want to know if two polygons are equally defined in
the same direction, will this condition make the alogorithm easier?

Sams

 
 
 

Checking CLOCKWISELY defined polygon??

Post by Glen Nieb » Fri, 17 Dec 1993 15:52:39



Quote:>Hi,
>I want to know if there is any method to check if *any* polygon,
>represented by points, can be checked if it is clockwisely
>defined or anti-clockwise.
>Actually, I want to know if two polygons are equally defined in
>the same direction, will this condition make the alogorithm easier?

If the two polygons share a common edge (which is the most useful
case for checking this), then the edge they have in common should be
defined in opposite directions on each polygon.

        1--------2-------3
        |    >   |   >   |
        |        |       |
        |/\  1 \/|/\ 2 \/|
        |        |       |
        |    <   |   <   |
        4--------5-------6

In this case points 2 and 5 form the common edge.  If both polygons are
clockwise then polygon 1 must have edge [2,5] while polygon 2 has edge
[5,2].

In a more general case (no common edge, or don't want to look for one),
take two succesive edges on each polygon, and take the cross product.
Now take the dot product of the two resulting vectors.  If the value of
the dot product is less than zero, the polygons face in opposite
directions.  If it is greater than 0 the polygons face the same
direction.

This only works if your polygons are pretty flat, and you consider
polygons whose normals have an included angle greater than 90 degrees
to be facing in opposite directions.  You can expand on the general
theme if you want, but i doubt that it would ever be foolproof except
in the purely planar case.

Glen

--
Glen Niebur     | By the force of will, my lungs are filled,
Mayo Clinic     | and so i breathe.
Biomechanics Lab|


 
 
 

Checking CLOCKWISELY defined polygon??

Post by Sum L » Sat, 18 Dec 1993 03:25:06


I believe you can just compute the area of the polygon and
look at the sign of the quantity.  If they are the same
the are oriented in the same direction.

This fails if the polygons are self intersecting.

Sum

 
 
 

Checking CLOCKWISELY defined polygon??

Post by Sum L » Sat, 18 Dec 1993 08:41:58


The original poster stated "*any* polygon".  I believe your
approach of selecting two arbitrary edges may not work if
the polygon is a non-convex one.


 
 
 

Checking CLOCKWISELY defined polygon??

Post by Tom Wrig » Sun, 19 Dec 1993 02:39:59



>Hi,

>I want to know if there is any method to check if *any* polygon,
>represented by points, can be checked if it is clockwisely
>defined or anti-clockwise.

>Actually, I want to know if two polygons are equally defined in
>the same direction, will this condition make the alogorithm easier?

>Sams

easy: compute the area using the conventional method and look at the
sign of the result.
 
 
 

Checking CLOCKWISELY defined polygon??

Post by Jens Alfk » Sun, 19 Dec 1993 09:40:36



> take two succesive edges on each polygon, and take the cross product.
> Now take the dot product of the two resulting vectors.  If the value of
> the dot product is less than zero, the polygons face in opposite
> directions.  If it is greater than 0 the polygons face the same
> direction.

You are comparing the surface normals of two polygons embedded in 3-space to
see if they face the same direction. I don't think this is what the original
poster was asking for; he wanted to know whether polygons in 2-space are
defined as clockwise or counterclockwise. You do this, as someone else has
posted, by computing the area and checking its sign.

                                    This sound has no waves
--Jens Alfke                        This sound has no waves

            .apple.com              Through fog and other grey things
                                                  --Dog Faced Hermans

 
 
 

Checking CLOCKWISELY defined polygon??

Post by Joseph O'Rour » Wed, 22 Dec 1993 09:43:38





>> take two succesive edges on each polygon, and take the cross product.
>> Now take the dot product of the two resulting vectors.  If the value of
>> the dot product is less than zero, the polygons face in opposite
>> directions.  If it is greater than 0 the polygons face the same
>> direction.

>You are comparing the surface normals of two polygons embedded in 3-space to
>see if they face the same direction. I don't think this is what the original
>poster was asking for; he wanted to know whether polygons in 2-space are
>defined as clockwise or counterclockwise. You do this, as someone else has
>posted, by computing the area and checking its sign.

        Jens is right I think, but Glen has a point, in that it isn't
necessary to compute the area.  Why not find the lowest, rightmost point
of the polygon, and then take the cross product of the edges fore
and aft of it?  Of course both methods are O(n) for n vertices,
but it does seem a waste to add up that total area when a single
cross product (of just the right edges) suffices.
        The reason that the lowest, rightmost point works is that
the internal angle at this vertex is necessarily convex,
strictly less than pi (even if there are several equally-lowest
points).
 
 
 

Checking CLOCKWISELY defined polygon??

Post by Glen Nieb » Thu, 23 Dec 1993 01:01:21






>>> take two succesive edges on each polygon, and take the cross product.
>>> Now take the dot product of the two resulting vectors.  If the value of
>>> the dot product is less than zero, the polygons face in opposite
>>> directions.  If it is greater than 0 the polygons face the same
>>> direction.

>>You are comparing the surface normals of two polygons embedded in 3-space to
>>see if they face the same direction. I don't think this is what the original
>>poster was asking for; he wanted to know whether polygons in 2-space are
>>defined as clockwise or counterclockwise. You do this, as someone else has
>>posted, by computing the area and checking its sign.
>    Jens is right I think, but Glen has a point, in that it isn't
>necessary to compute the area.  Why not find the lowest, rightmost point
>of the polygon, and then take the cross product of the edges fore
>and aft of it?  Of course both methods are O(n) for n vertices,
>but it does seem a waste to add up that total area when a single
>cross product (of just the right edges) suffices.
>    The reason that the lowest, rightmost point works is that
>the internal angle at this vertex is necessarily convex,

                                                  ^^^^^^

Quote:>strictly less than pi (even if there are several equally-lowest
>points).

In 2D there are simpler methods than i gave, however i assumed
that the original poster was looking for 3D solutions and using the
clockwiseness of the polygons to do backface removal or lighting or
who knows what.  Oh well.

Anyway, as a couple of people have pointed out, you have to be a little
more careful than i stated, as i forgot to consider the concave polygon
issue.

Glen

--
Glen Niebur     |
Mayo Clinic     | Although it's been said many times, many ways,
Biomechanics Lab|              MERRY CHRISTMAS to you!

 
 
 

1. Check a polygon whether it intersects or within another polygon

Hello,
       I am looking for an algorithm or source code that
compares two 2D polygons (A & B), to find out whether

1) polygon A is in within polygon B

2) polygon A is intersect with polygon B

3) both polygon A and B are separated polygons

The answer can be in a form of boolean, true or false for the
above conditions.

Actually I trying to find out which is the "outside" or
"inside" polygon. It maybe a little bit complicated since
it may involved bezier curves (all in 2D of course).

Anybody knows such algorithm ?

Thanks in advance.

Happy Millenium.

--
K.K.Chan

Sent via Deja.com http://www.deja.com/
Before you buy.

2. O.T. IDE-disc-array (Promise RAID)

3. Q: Check for polygon inside a polygon

4. looking for LW reseller in Holland or Belgium

5. defining polygons - closed or open ?

6. I'M ADDICTED TO MUSHROOM PIZZA

7. Getting B_Spline defining polygon from data

8. camera in 3d engine

9. sort points defining polygon counter-clock-wise

10. Polygons defined with evaluated curves

11. checking whether 2 2D polygons overlap

12. need an algorithm to check if a point is inside a polygon

13. checking whether a polygon contains another