Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search