## Algorithm: Check It two polygon intersect is not working for some points

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.