18

編集：私は答えでプログラムを更新しました、そしてそれは素晴らしい働きをします！

私は、ユーザーがポリゴンを描画して三角形分割できるプログラムを作成しています（自由に試してみてください）。クリックして頂点を追加し、Enterキーを押して三角形分割することができます。とにかく、ポイントが時計回りまたは反時計回りのどちらで描画されたかを指定する限り、アルゴリズムは正常に機能します（現在、時計回りのポリゴンでのみ機能するように設定しています）。私はこれを何日も理解しようとしてきましたが、ポイントが時計回りか反時計回りかを判断する方法がわかりません。先に述べたプログラムで形を描いてみてください。より良いアイデアを得ることができます。私が話していることを、説明するよりもよく体験することができます。

ポイントの定義方法は次のとおりです。

function Point(x, y) {
    this.x = x;
    this.y = y;
}

var vertices = [];

// Called on click
function addPoint(mouseX, mouseY) {
    vertices.push(new Point(mouseX, mouseY));
}

時計回りのポリゴンの画像は次のとおりです。

時計回りのポリゴン

これが反時計回りのポリゴンの画像です。

反時計回りのポリゴン

ポイントの「時計回り」を判断する方法を教えていただければ幸いです。

4

5 に答える 5

29

靴ひも式を使用して多角形面積を計算しますが、絶対値記号は使用しません。結果が正の場合、ポイントは反時計回りに並べられ、負の場合は時計回りに並べられます。

function polygonArea() { 
    var area = 0;
    for (var i = 0; i < vertices.length; i++) {
        j = (i + 1) % vertices.length;
        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
    }
    return area / 2;
}
var clockwise = polygonArea() > 0;
于 2013-01-24T16:52:27.100 に答える
1

一般的な考え方は、ポリゴンの凸包を見て、そこから向きを推測することです。ただし、方向を見つけるために船体全体を構築する必要はなく、船体に属する 1 つのセグメントだけを構築する必要があると思います。

そう：

  • 他のすべての点がこの線の片側にくるように、多角形の 2 つの点を見つけます。
  • すべてのポイントが左側にある場合 (ポイントの 1 つだけをチェックしてください)、反時計回りです。それらが右側にある場合は、時計回りです。

例：

上図：4-5は右図、5-11は右図、下図：6-7は左図、7-14は右図左、 ...

警告: 多角形を「歩いている」間は、計算を再開しないでください。そうしないと、正しくありません。上の図に 4-(n-1) を左の図に！

于 2013-01-24T16:40:56.387 に答える
1

時計回りの直感的な定義は明確ではありません。たとえば、蹄鉄を描く場合:

   /---a-b--\
  /   _d_c_  \
 /  /       \ \
 | |        | |
 | |        | |
  \ \       / /
   \ \     / /
    --     --

私0 = a < b < b < dが見てa、bあなたの説明から、形状は時計回りに描かれている0 = c < d < a < bと結論付けますが、形状が反時計回りに描かれていると結論付けます. これらのシナリオはどちらも、ポイントが描かれた方向が同じであるため、出発点が異なるだけなので、あなたの定義が欠けているとしか言えません。

私が描いた蹄鉄は最高ではありません。アイデアは、反対側を反対方向に描くことができるように、底に小さな穴があるだけのほぼ円であるということです.

物事をより厳密に定義することに興味がある場合は、次の行に沿ったものをお勧めします。

平面を 2 つの異なる領域 (1 つは有限でもう 1 つは無限) に分割する有限単純多角形を考えると、有限領域は常に多角形の内部であると見なすことができます。このようなシナリオでは、頂点の順序が時計回りになるように定義します。ただし、点の順序が右側に沿って外側に沿っている場合です。これは、カーブの向きと呼ばれます。

このより確実な定義があれば、実装は巻き数を数えるのと同じくらい簡単になります。任意の順序付けられたペアの中点、たとえば 0 と 1 を取り、順序付けられたペアの右側に線分を取り (任意の角度で、垂直とします)、他の線分との交点の数を数えます: 曲線は時計回りです。数は奇数です。

これは実装が簡単で、時間的に線形でO(n)あり、一定のスペースが追加されますO(1)。

于 2013-01-24T16:43:19.787 に答える
0

これは、OpenLayers に特化した関数関数です。ご覧のとおり、時計回りのポリゴンの条件はarea<0です。この参照を確認してください。

function IsClockwise(feature)
{
if(feature.geometry==null)return -1;
var vertices=feature.geometry.getVertices();
var area=0;
for (var i = 0; i < (vertices.length); i++) 
    {
    j = (i + 1) % vertices.length;
    area += vertices[i].x * vertices[j].y;
    area -= vertices[j].x * vertices[i].y;
    // console.log(area);
    }
return (area < 0);
}
于 2014-11-18T10:45:12.377 に答える