ポリゴンの中のポイントjavacript

Question

私が持っているポイントがポリゴンの内側にある場合、JavaScriptを探しています。私は点がポリゴンの中にあるかどうかを比較するためにレイキャスティングアルゴリズムを使用しています。

場合によってはアルゴが完璧に動作しています。しかし、いくつかのケースでは、ポイントがポリゴンの内側にあるときでさえ、ポイントが外側にあることを示しています。

！ https://www.dropbox.com/s/rpxqnw9re3q6vsi/Screen%20Shot.png?dl=0

A1と記された領域は親ポリゴンであり、A2とA3は親ポリゴンの内側です。私はポイントが内部か

以下

function isPointInside(point, vs) 
{ 
// ray-casting algorithm based on 
var x = point[0], y = point[1]; 

var inside = false; 
for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) 
{ 
    var xi = vs[i][0], yi = vs[i][1]; 
    var xj = vs[j][0], yj = vs[j][1]; 
    var intersect = ((yi > y) != (yj > y))&& (x < (xj - xi) * (y - yi)/(yj - yi) + xi); 
    if (intersect) inside = !inside; 
} 

return inside; 
}; 

親ポリゴンのポイントアレイだけでなく、子どものポリゴンが

A1 Array 
0[0, 0] (2) 
1[6096000, 0] (2) 
2[6096000, 0] (2) 
3[6096000, 6096000] (2) 
4[6096000, 6096000] (2) 
5[0, 6096000] (2) 
6[0, 6096000] (2) 
7[0, 0] (2) 
8[0, 0] (2) 
9[0, 0] (2) 


A2 Array (10) 
0[0, 0] (2) 
1[0, 3048000] (2) 
2[0, 3048000] (2) 
3[1524000, 3048000] (2) 
4[1524000, 3048000] (2) 
5[1524000, 0] (2) 
6[1524000, 0] (2) 
7[0, 0] (2) 
8[0, 0] (2) 
9[0, 0] (2) 


A3 Array (10) 
0[4572000, 0] (2) 
1[4572000, 6096000] (2) 
2[4572000, 6096000] (2) 
3[6096000, 6096000] (2) 
4[6096000, 6096000] (2) 
5[6096000, 0] (2) 
6[6096000, 0] (2) 
7[4572000, 0] (2) 
8[4572000, 0] (2) 
9[4572000, 0] (2) 

なぜポイントということですされているかどうかを確認するために使用している機能の下のA3は内部とはみなされません。アルゴに何か間違っていますか？どんな助けもありがとう。

Answer 1

いくつかのユーティリティ機能から始めましょう。

最初はarea（Point、Point、Point）です。引数として3つのポイントが必要です（順序は非常に重要です）。 1番目と2番目の点はベクトルを形成し、3番目の点がこのベクトルの左側にあれば関数は正の値を返し、3番目の点が右側にあれば負の値を返し、3番目の点がベクトルにある場合は0を返します。

function area(p1 , p2, p3) { 
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x); 
}; 

次のユーティリティ関数は、各ポリゴンポイントをソートする際の比較器として使用されるsortCMP（Point、Point）です。

function sortCMP(p1, p2) { 
    var result_area = area(target, p1 ,p2); 
    if(result_area == 0.0) { 
     return (sqrtDist(target, p1) - sqrtDist(target, p2) > 0.0)? 1 : -1; 
    } 
    return (result_area > 0.0)? -1 : 1; 
}; 

ポリゴンにはP1からPNのN点が含まれていて、POINTSという名前の配列に格納されているとしましょう。以前の関数（sortCMP）では、変数TARGETがあります。これは、P1からPNまでのすべてのポイントの中で最も小さいX座標とY座標を指すはずです。

次の機能は、実際だから今戻ってあなたのポリゴンからのすべての点を含む配列名POINTS、にしてみましょう2ポイント

function sqrtDist(p1, p2) { 
     var dx = p1.x - p2.x; 
     var dy = p1.y - p2.y; 
     return dx * dx + dy * dy; 
}; 

の間の距離を返しますsqrdDist、です。 XとYの座標が最も低いもの（目標変数）がすでに見つかりました。今度は配列の最初の要素に移動し、配列全体をソートする必要がありますが、インデックス1の要素から始める必要があります。

配列をソートした後、 Pi + 1、T）は常に正の値を返します（ポリゴン自体を置いておきたい場合は0も返します）。領域関数が負の値を返した場合、点Tは常にあなたのポリゴンです。点Tはポリゴンの内側にある場合にテストする点です。

私はこのように動作するために私のコメントで述べたように、多角形は凸多角形でなければなりません。これは、前のアルゴリズムの最後のステップでチェックすることができます。すべてのポリゴンの点をソートすると、領域（Pi、Pi + 1、Pi + 2）が常にすべてのポリゴンの点に対して正の値（または0）を返すかどうかを調べることができます。それがどこかで負の値を返したら、あなたのポリゴンが凸ではないことを意味します。負の値を返すと、インデックスi + 1のポイントがポリゴンを分割する必要があるポイントでもあることを意味します。私は今覚えていないので、あなたはちょうどそれを分割する方法を詳細については、おそらくあなたはGoogleで検索する必要があります。

これがあなたを少し助けてくれることを願っています。ご質問がありましたらお気軽にお問い合わせください。