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

Advertisements

11 thoughts on “Determine if Two Polygons overlap

  1. 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.

  2. 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.

  3. 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

  4. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s