# Determine if Two Polygons overlap

In order to determine if two polygons overlap we need to iterate through the line segments that make up each polygon and determine if any of the line segments intersect. Once we find a single point where the lines intersect we can then stop the iterations. The following code can be used to determine if two polygons overlap:

```//poly1 and poly2 are arrays of VELatlongs that represent polygons
function ArePolygonsOverlapped(poly1, poly2){    if(poly1.length >= 3 && poly2.length >= 3)    {        //close polygons
poly1.push(poly1[0]);
poly2.push(poly2[0]);

for(var i = 0; i < poly1.length-1;i++)        {            for(var k = 0; k < poly2.length-1; k++)            {    if(SimplePolylineIntersection(poly1[i],poly1[i+1],poly2[k],poly2[k+1])!=null)                    return true;            }        }                return false;    }        return null;}```

The code for the function "SimplePolylineIntersection" can be found here: http://rbrundritt.spaces.live.com/blog/cns!E7DBA9A4BFD458C5!474.entry

## 11 thoughts on “Determine if Two Polygons overlap”

1. Geoffrey says:

Dude you go off.. I just all your posts as a massive dump in my google reader. Keep up the great work!

Great work and explanation given
Thanks a lot.

3. Ross says:

Thanks Ricky, I was wondering if this handles polygon A contains polygon B. Or containing is not consider as overlap?

• The algorithm will determine if a polygon intersects (overlaps) or is complete contained. However it won’t just tell you if is complete contains and not overlapping. The algorithm could be easily changed though to determine that.

4. Praveen says:

This is for Google Maps v2 version I guess(which is depreciated and removed). It would be great if you can update for Google Maps v3. If I end up. I will let you know.

Thanks,
Praveen Jegan

• Nope. This is Bing Maps v6.3, not Google Maps v2. I don’t use Google Maps, note the title of my blog “Ricky’s Bing Maps Blog”. If you want to use this with the latest version of Bing Maps (v7) you can easily modify this code to work by:

* Give all Latitude and Longitude property names small “L”s.
* Change VELatLong to Microsoft.Maps.Location.

5. Hii, I was testing your algorithm with these two polygons. Cheking on google maps polygon 1 contains polygon 2. But the algorithm is returning false, i.e. these polygons do not overlap. Please suggest how to fix this.

Polygon 1:
————–+——————+——————+
| polygon_id | latitude | longitude |
+————–+——————+——————+
| 158 | 13.1303042583903 | 77.7543640136719 |
| 158 | 13.1420061213258 | 77.6383209228516 |
| 158 | 13.1189362005413 | 77.5209045410156 |
| 158 | 12.9209143604345 | 77.3890686035156 |
| 158 | 12.7970707734707 | 77.4900054931641 |
| 158 | 12.8446071570180 | 77.6403808593750 |
| 158 | 12.8499628062145 | 77.8154754638672 |
| 158 | 12.9436681426755 | 77.8504943847656 |
| 158 | 13.0420208479226 | 77.8154754638672

Polygon 2:

————–+——————+——————+
| polygon_id | latitude | longitude |
+————–+——————+——————+
| 158 | 13.1303042583903 | 77.7543640136719 |
| 158 | 13.1420061213258 | 77.6383209228516 |
| 158 | 13.1189362005413 | 77.5209045410156 |
| 158 | 12.9209143604345 | 77.3890686035156 |
| 158 | 12.7970707734707 | 77.4900054931641 |
| 158 | 12.8446071570180 | 77.6403808593750 |
| 158 | 12.8499628062145 | 77.8154754638672 |
| 158 | 12.9436681426755 | 77.8504943847656 |
| 158 | 13.0420208479226 | 77.8154754638672

• Sorry polygon 2 is

+————–+——————+——————+
| polygon_id | latitude | longitude |
+————–+——————+——————+
| 150 | 12.8969871916682 | 77.5722312927246 |
| 150 | 12.9225875033164 | 77.6108551025391 |
| 150 | 12.8817596199286 | 77.6197814941406 |
| 150 | 12.8887878450392 | 77.5693130493164 |
+————–+——————+——————+

6. Hii, thanks for the reply , actually I am writing the code in PHP. I have set of vertices as I have mentioned and want to know if two polygons overlap. I just need the result in true or false. Please tell me how to make this algorithm better.

• I am not using bingmaps. Thank you.