I found this algorithm to check if two polygons intersect:

https://rbrundritt.wordpress.com/2008/10/20/determine-if-two-polygons-overlap/#comment-6287

//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;
}


function SimplePolylineIntersection(latlong1,latlong2,latlong3,latlong4)
{
    //Line segment 1 (p1, p2)
    var A1 = latlong2.Latitude - latlong1.Latitude;
    var B1 = latlong1.Longitude - latlong2.Longitude;
    var C1 = A1*latlong1.Longitude + B1*latlong1.Latitude;

    //Line segment 2 (p3,  p4)
    var A2 = latlong4.Latitude - latlong3.Latitude;
    var B2 = latlong3.Longitude - latlong4.Longitude;
    var C2 = A2*latlong3.Longitude + B2*latlong3.Latitude;

    var determinate = A1*B2 - A2*B1;

    var intersection;
    if(determinate != 0)
    {
        var x = (B2*C1 - B1*C2)/determinate;
        var y = (A1*C2 - A2*C1)/determinate;

        var intersect = new VELatLong(y,x);

        if(inBoundedBox(latlong1, latlong2, intersect) && 
inBoundedBox(latlong3, latlong4, intersect))
            intersection = intersect;
        else
            intersection = null;
    }
    else //lines are parrallel
        intersection = null; 

    return intersection;
}

//latlong1 and latlong2 represent two coordinates that make up the bounded box
//latlong3 is a point that we are checking to see is inside the box
function inBoundedBox(latlong1, latlong2, latlong3)
{
    var betweenLats;
    var betweenLons;

    if(latlong1.Latitude < latlong2.Latitude)
        betweenLats = (latlong1.Latitude <= latlong3.Latitude && 
latlong2.Latitude >= latlong3.Latitude);
    else
        betweenLats = (latlong1.Latitude >= latlong3.Latitude && 
latlong2.Latitude <= latlong3.Latitude);

    if(latlong1.Longitude < latlong2.Longitude)
        betweenLons = (latlong1.Longitude <= latlong3.Longitude && 
latlong2.Longitude >= latlong3.Longitude);
    else
        betweenLons = (latlong1.Longitude >= latlong3.Longitude && 
latlong2.Longitude <= latlong3.Longitude);

    return (betweenLats && betweenLons);
}

However, when I was testing this algorithm with these two polygons, Checking 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

I’ve read the algorithm properly. It doesnot seem to have any issues. It tries to check if the intersection point of two edges is inbound or not. Don’t understand the issue.

Read more here: Algorithm: Check It two polygon intersect is not working for some points


Solution:

If you know the solution of this issue, please leave us a reply in Comment section, to update the question.


Wordpress related questions and answers: