アルゴリズム：チェックそれ2つのポリゴン2つのポリゴンが交差する場合、私がチェックするために、このアルゴリズムを見つけ

Question

いくつかのポイントのために働いていない交差：

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

しかし、私はこれらの2で、このアルゴリズムをテストしていたとき、ポリゴン、polygon 1のGoogleマップをチェックすると、polygon 2が含まれています。しかしアルゴリズムは偽を返す、すなわちこれらのポリゴンは重なり合わない。これを修正する方法を提案してください。

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  | 
+--------------+------------------+------------------+ 
|   150 | 12.8969871916682 | 77.5722312927246 | 
|   150 | 12.9225875033164 | 77.6108551025391 | 
|   150 | 12.8817596199286 | 77.6197814941406 | 
|   150 | 12.8887878450392 | 77.5693130493164 | 
+--------------+------------------+------------------+ 

Answer 1

交差点に関する部分は、私には正しいように見えますが、私はポリゴンがそう簡単に他のポリゴンの中に含まれていることを主張することが可能であるとは思いません。事実、コードをもっと慎重に見ると、AのセグメントとBのセグメントを見るだけでポリゴンAがポリゴンBに含まれているかどうかを表すことができます。つまり、これらのポリゴンが互いに含まれているかどうかを知るには、各ポリゴンの1つのセグメントを与えるだけで十分です。それは明らかに間違っています。