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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.