2

多角形の点を見つける方法はありますか? ポイントがポリゴン内にあるかどうかを調べたいのではなく、内側のポイント自体を見つけたい。x 座標の平均と y 座標の平均を使用してポリゴンの重心を求めようとしましたが、次のように重心が外側にある特定のポリゴンの場合、これは当てはまりません。

ここに画像の説明を入力

4

7 に答える 7

0

本格的なアルゴリズムがなければ、次のことができます。

時計回りの順序でポイントに追加したポリゴンがあるとします。

    p.addPoint(100, 200);
    p.addPoint(200, 100);
    p.addPoint(160, 200);
    p.addPoint(200, 300);
    for(i=0; i<p.npoints; i++) {
      int[] p0={p.xpoints[i], h-1-p.ypoints[i]}, p1={p.xpoints[(i+1)%p.npoints], h-1-p.ypoints[(i+1)%p.npoints]}, p2={p.xpoints[(i+2)%p.npoints], h-1-p.ypoints[(i+2)%p.npoints]};
      System.out.println(" angle "+angle(p0, p1, p2));
    }

つまり、連続する 3 つの点を取り、角度 p0、p1、p2 を決定します (この順序で、p1 は角度の角です)。辺 p2-p1 が向きを変えて辺 p0-p2 に合うように時計回りの順序で): 180 度よりも凸角であり、その内側にいくつかの点を取得できます (たとえば、2 つの辺の中点を取り、それらの接続線の中点を見つけるなど)。

180以上なら続けます。

angle() は角度を求めるメソッドです。

座標を通常の幾何学系に変換する場合は h-1-p[] が必要です (h はウィンドウの高さです)。それ以外の場合は使用しないでください。

要約すると、角度アプローチまたはその他のアプローチのいずれかを使用して、凸状のコーナーを見つけます。

于 2016-03-28T19:18:53.450 に答える
0

n 個の頂点があるポリゴンがあると仮定するとV_n = (x_n,y_n)、次のことができます。

  1. A = (max(x_n),max(y_n))ポイントと を計算しB = (min(x_n),min(y_n))ます。両方の点が実際に頂点であるかどうかを確認し、そうでない場合は次の手順に進みますが、両方のC = (max(x_n),min(y_n))点が頂点である場合は、代わりに点を取得しD = (min(x_n),max(y_n))ます。
  2. ラインAB(またはCD) をポリゴンと交差させます (つまり、すべてのエッジと交差させ、すべての頂点がそのライン上にあるかどうかをテストします)。
  3. 前のステップで取得したすべてのポイントについて、 までの距離を計算しA(またはCそれぞれ)、距離を に増やして並べ替えますA。
  4. A に最も近い点 (A が頂点の場合は A 自体) から始めて、その点と次に近い点の間の点を選びます。その点がポリゴンの内側にあるかどうかをテストします。完了している場合は、完了していない場合は、次のポイント (最後の反復の 2 番目のポイント) でこの手順を繰り返します。

説明

長方形ACBDは、ポリゴンの軸に沿った境界ボックスであるため、ポリゴンの内側にあるすべてのポイントもその長方形の内側になります。ABそしてCDはその長方形の対角線です。

ステップ 1 では、点Aとの両方Bが頂点であるかどうかを確認します。これは重要です。それらのいずれかがそうでない場合、ポリゴンの少なくとも 1 つの頂点が対角線の「上」にあり、少なくとも 1 つの頂点が「下」にあることを確認できるため、対角線はポリゴンと交差します。

両方の点が頂点である場合、対角線が実際にはエッジである三角形、または対角線の片側に完全にある凹型多角形を扱っている可能性があります。したがって、対角線を切り替えるだけで、もう一方の対角線が交差することが保証されますポリゴン。

対角線がポリゴンと交差することがわかっているので、すべての線分を繰り返し処理し、それぞれから点を選択して、内側にあるかどうかを確認できます。そのうちの 1 つが内側にある必要があります。通常、テストするのは最初の線分ですが、この線分が多角形の外側になる特殊なケースがあります (繰り返します: 凹型多角形で、最初の交点がエッジではなく頂点です)。セグメントは内側にある必要があります。

これはより効率的に行うことができると思いますが、n が十分に小さく、多数のポリゴンに対してそれを行う必要がない場合、問題はないはずです。

于 2016-03-27T21:58:11.723 に答える
-1

これはコーディングというよりも数学の問題ですが、次のようなことを試してみてください

その点から光線を開始し、その光線がポリゴンと交差する回数を確認します。ポイントがポリゴンの外側にある場合でも

于 2016-03-27T21:32:53.997 に答える