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

### Overlapping Polygons

```Date: 06/10/2003 at 08:35:32
From: Jagdish
Subject: Find whether two polygons are overlapping in a 2d plane

I am trying to write a Java program. Given all the coordinates for two
different polygons in an x,y plane, it must be able to determine
whether the polygons overlap.

Thanking you,
Jagdish
```

```
Date: 06/10/2003 at 09:23:29
From: Doctor George
Subject: Re: Find whether two polygons are overlapping in a 2d plane

Hi Jagdish,

Thanks for writing to Doctor Math.

The polygons overlap if a side of one polygon intersects a side of the
other polygon.

Let's say that line L1 contains vertices V11 and V12 from one polygon,
and line L2 contains vertices V21 and V22 from the other polygon.

We can write vector equations for L1 and L2 like this.

L1 = V11 + a(V12 - V11)

L2 = V21 + b(V22 - V21)

Where L1 and L2 intersect we must have

V11 + a(V12 - V11) = V21 + b(V22 - V21)

a(V12 - V11) = (V21  - V11) + b(V22 - V21)

Now define vector VP to be perpendicular to (V22 - V21) and take the
dot product of both sides with VP.

a[(V12 - V11).VP] = (V21 - V11).VP

Note that the b term has dropped out. If [(V12 - V11).VP] = 0 then
L1 and L2 are parallel; otherwise we can solve for a. In a similar
way we can also make a drop out and solve for b.

Now we need to work through this procedure for every combination of
sides from the two polygons and make a list of all of the (a,b) pairs.

Here are the options.

1. If a and b are both in [0,1] for some (a,b),
then L1 intersects L2 at a point on both polygon edges.

2. If some a is in [0,1] and no b is in [0,1],
then the polygon with the a values contains the polygon
with the b values.

3. If no a is in [0,1] and some b is in [0,1],
then the polygon with the b values contains the polygon
with the a values.

4. If no a is in [0,1] and no b is in [0,1],
then the polygons have no overlap.

Can you take it from here?  Write again if you need more help.

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

```
Date: 06/11/2003 at 00:35:17
From: Jagdish
Subject: Thank you

Dear Sir,

solution is really going to help me.

Regards,
Jagdish
India
```
Associated Topics:
College Coordinate Plane Geometry
High School Coordinate Plane Geometry

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