Determining If A Polygon's Edges Cross

Date: 10/29/2003 at 16:54:23
From: Anastasia
Subject: Polygons that have lines that cross themselves

Is there a way to determine if the vertices that define a polygon 
[(x1,y1) to (xn,yn)] have lines that cross themselves?

I think that the ordering of the points is important. I thought I
could calculate the slope of the lines formed by point 1 to point 2,
point 2 to point 3 and so on, then analyze the slopes to determine if
a line is crossing, but it's not working.

Date: 10/30/2003 at 16:34:58
From: Doctor Korsak
Subject: Re: Polygons that have lines that cross themselves

Hello Anastasia,

I think you meant to ask if there is a way to tell if any of the
polygon edges cross other edges.

If my assumption is correct, here is a trick you can use.  When one 
edge of a polygon crosses another one, the end points of one edge lie
on opposite sides of the other edge.  There is a simple way to tell if
two points are on the same side of a line, so you can use that to test
all the end points of edges against other edges as follows:

Let P1 = (x1,y1), P2 = (x2,y2) be ends of one polygon edge, and P3 = 
(x3,y3), P4 = (x4,y4) be ends of another edge.  The determinants

 | x1 y1 1 |        | x1 y1 1 | 
 | x2 y2 1 |        | x2 y2 1 |
 | x3 y3 1 |        | x4 y4 1 |

are positive when the points P1, P2, P3 and P1, P2, P4 are in counter-
clockwise order, and negative for clockwise order.  In other words, 
points P3 and P4 are on opposite sides of the line segment P1_P2 when 
the above two determinants are of opposite sign.  If these
determinants are 0, P3 and P4 lie on the line P1_P2.  

The following is another way of writing the equation of a line:

 | x1 y1 1 |
 | x2 y2 1 |  = 0
 | x  y  1 |

Please contact Dr. Math if you need further help on this topic.

- Doctor Korsak, The Math Forum
  http://mathforum.org/dr.math/