3

次のコードを使用しました: http://www.amphibian.com/blogstuff/collision.html。HTMLテストファイルで、最初の三角形を次のように変更しました

triangle1.addPoint({"x":-20, "y":-20});
triangle1.addPoint({"x":-20, "y":20});
triangle1.addPoint({"x":20, "y":20});
triangle1.addPoint({"x":20, "y":10});
triangle1.addPoint({"x":10, "y":10});
triangle1.addPoint({"x":10, "y":-20});

交差する前にこの形状の内側で他の三角形を移動すると、間違って交差します。どこに問題があるのでしょうか？

4

2 に答える 2

9

よし、これで遊びたい人のためにフィドルを用意した。結果は次のとおりです。

問題のある交差のデモンストレーション

このスクリプトは、次のソースで説明されているように、分離軸定理または (ウィキペディアが呼んでいるように)超平面分離定理polygon.jsを使用します。

/*
 *  To detect intersection with another Polygon object, this
 *  function uses the Separating Axis Theorem. It returns false
 *  if there is no intersection, or an object if there is. The object
 *  contains 2 fields, overlap and axis. Moving the polygon by overlap
 *  on axis will get the polygons out of intersection.
 */
Polygon.prototype.intersectsWith = function(other) {

この定理は、凸多角形にのみ適用されます。「へこみ」があるため、形状は凸状ではありません。そのため、スクリプトは形状が交差していると誤って報告します。凹形状で機能させる必要がある場合は、最初に凹形状を別々の凸部分に分割してから、すべての個々の部分に定理を適用する必要があります。明らかに、2 つの形状の凹面部分の外積を反復処理する必要があるため、スクリプトがより複雑になります。

于 2012-05-31T18:03:19.677 に答える
0

これは、2 つのポリゴンの交差ポリゴンを見つけるための、あまり複雑ではない実装です。

凸面ポリゴンと凹面ポリゴンでは機能しますが、複雑な (自己交差する) ポリゴンでは機能しません。アルゴリズムは、 Margalit & Knottで提示されたものとかなり似ています。

その複雑さは約 4*n1*n2 です。ここで、n1 と n2 は、交差が計算されるポリゴンの頂点の数です。

これは、単一のスタンドアロン .js ファイルです。「ポリゴン」は、2D ポイントの任意の JavaScript 配列と見なされます。「ポイント」は、x および y の数値プロパティを持つ任意の JavaScript オブジェクトです。

Union 機能を既存のものの上に実装することは問題にはならないはずです。

2D ポリゴンの交差

于 2014-04-14T14:07:37.120 に答える