5

正方形が三角形の中にあるかどうかを確認する簡単で効率的な方法があるかどうか疑問に思っています。または、少なくとも1つのコーナーが内側にあるか、一部が重なっています。たとえば、下の図を考えると、3つの正方形が中にあることがわかります。つまり、正方形1は明らかに内側にあり、正方形2の1つのコーナーは内側にあり、3つは重なっています。 図の例

4

6 に答える 6

4

三角形をすべて固定回転順序の3つのベクトルと見なします：A-> B、B-> C、C-> A

ここで、三角形の頂点ごとに、その頂点から各正方形の頂点までの4つのベクトルがあると考えます。各三角形のエッジベクトルと各三角形の正方形のベクトル（合計12）の間の外積を計算します。外積がすべて同じ符号（またはゼロ）の場合、正方形は内側にあります。

概念的には、正方形の頂点が線の左側にあるか右側にあるかを判断しようとしています。実際には、左か右か、時計回りか反時計回りかは関係ありません...正方形の頂点がすべての三角形ベクトルの同じ側にあることだけです。

于 2012-09-15T22:42:28.160 に答える
2

私はこの素敵なチュートリアルをチェックしています。さまざまな手法を使用して、ポイントが三角形の内側にあるかどうかをテストする方法について説明します。四角い角が中に入ると助かると思います。

そして、私は重心技術が好きでした、ここで私はmatlabのためにそれを再実装しました：

function d = isinside(p,a,b,c)

    % Test if a point p(x,y) is inside a triangle
    % with vertices a(x,y), b(x,y) and c(x,y)

    v0 = c - a;
    v1 = b - a;
    v2 = p - a;

    A = [dot(v0,v0) dot(v1,v0);dot(v0,v1) dot(v1,v1)];
    b = [dot(v2,v0); dot(v2,v1)];

    x  = A\b;

    % Check if point is in triangle
    if (x(1) > 0) && (x(2) > 0) && (sum(x) < 1)
        d = true;
    else
        d = false;
    end

次に、正方形の各頂点をテストします。それが発生した場合は、そのうちの1つが内側に収まります。かなり多くの計算がありますが、試してみる価値があります。

オーバーラップについては、このスレッドで説明されているように、三角形と正方形の両方からの線のすべての組み合わせについて、交差をテストします。

于 2012-09-15T22:34:37.143 に答える
1

ここの初心者。頭に浮かぶアイデアの1つは次のとおりです。これは効率的ではないかもしれませんが、かなり簡単です。

1）正方形の4つの角を計算します。

2）各コーナー/ポイントが「歩く」方向を選択します。基本的に、その点のベクトル方向を選択します。

3）それらの点をベクトルに沿って「歩き」、三角形の境界に関心があるかどうかを確認します。

4）ポイントの歩行ベクトルが奇数回交差する場合、それはそのポイントが内側にあることを意味します。それが偶数回交差する場合、それはそれが外側にあることを意味します。0は偶数としてカウントされることを忘れないでください。

5）実際に三角形の端に沿って歩く場合は、特別な場合を行う必要があります。これはほとんどの場合回避できますが、別の方向を選択するだけです。

于 2012-09-15T20:40:10.680 に答える
1

多分これはアイデアを与えることができます。

ここに画像の説明を入力

0 ～ 1 の値で三角形の画像を作成します (これは難しい部分です)。次に、正方形ごとに 0-1 の画像を作成します。これは非常に単純です。両方の画像を追加し、異なる三角形または正方形の座標で値を計算します。重複領域の面積を計算することもできます。

于 2012-09-16T15:56:26.613 に答える
0

あなたがmatlabについて尋ねたので、他の回答が直接的なアプローチを説明したので、いくつかの利用可能な解決策について言及します。polyxpolyを見てみるとよいでしょう (Mapping Toolbox がある場合)。より一般的なケースを処理できます。それ以外の場合は、File Exchange に多数の寄稿があります。Curve Intersect 2などを参照してください。一方、 Polygon_Intersectionは交点だけでなく、重なり合う領域を返します。

于 2012-09-20T11:54:18.883 に答える
0

実際にしようとしているのは、正方形が三角形から直線的に分離可能かどうか、つまり、2 つのオブジェクトを分離する線があるかどうかを判断することです。そのような線が存在する場合、それらは交差しません。線形分離可能性をテストするアルゴリズムはいくつかあります。利点は、それらが一般的であるため、他のポリゴンでも機能することです。欠点は、それらの一般性のために、ソリューションを単純化するために問題の特定の特性を使用しない可能性があることです。

于 2012-09-17T09:23:55.427 に答える