30

ランダムな順序でポイントの配列があり、すべてのポイントを通過する多角形を (隣接するすべてのペアが辺を表すようにソートすることによって) 見つける必要があり、その辺はもちろん交差していないとします。

ポイントを選択し、その下にあるすべてのポイントを最終的な配列に追加して、左から右に並べ替えることでそれを実行しようとしました。次に、その上にあるすべてのポイントを追加し、右から左に並べ替えます。

自己交差を避けるために、ポイントを追加して自然に並べ替えることができると言われました..しかし、それを理解することはできません。これを行う簡単な方法は何ですか？

4

11 に答える 11

36

私たちの戦略は、多角形にすべての点が含まれていること、および線が交差しない場所でそれらを接続する順序を見つけることができることを確認する計画を立てることです。

アルゴリズム:

  1. 一番左の点 p を見つける
  2. 一番右の点 q を見つける
  3. 点を pq より下の点の集合である A と、pq より上の点の集合である B に分割します [(p,q,?) で左折テストを使用して、点が線の上にあるかどうかを判断できます]。
  4. A を x 座標 (昇順) で並べ替える
  5. B を x 座標 (減少) で並べ替えます。
  6. A の点を順番に p、B の点を順番に q で定義された多角形を返します。

ランタイム:

ステップ 1、2、3 には O(n) 時間がかかります。
ステップ 4、5 には O(nlogn) 時間がかかります。
ステップ 6 は O(n) 時間かかります。
総実行時間は O(nlogn) です。

正しさ:

構造上、p,q 以外のすべてのポイントはセット A またはセット B に含まれます。したがって、6 行目の出力ポリゴンは、すべてのポイントを含むポリゴンを出力します。ここで、出力ポリゴンのどの線分も互いに交差していないと主張する必要があります。

出力ポリゴンの各セグメントを検討します。p から A の最初の点までの最初のエッジは、どのセグメントとも交差できません (まだセグメントがないため)。A の点を x 座標で順に進むと、各点から、次のセグメントは右に進み、前のすべてのセグメントは左になります。したがって、p から A のすべての点を通って点 q に行くとき、交点はありません。

q から B の点に戻る場合も同様です。これらの線分は右から左に進むため、互いに交差することはできません。これらの線分は、A のすべての点が線 pq より下にあり、B のすべての点がこの線の上にあるため、A のどの点とも交差できません。

したがって、セグメントが互いに交差することはなく、単純な多角形が得られます。

出典：リンク切れ

于 2013-12-17T00:39:50.520 に答える
9

誰かが言ったように、最小の長さの解決策はまさに巡回セールスマン問題です。これは、最適ではありませんが実行可能なアプローチです。

ポイントのドロネー三角形分割を計算します。すべての点を補間する境界が残るか、それ以上セグメントを削除できなくなるまで、境界セグメントを連続して削除します。そのセグメントを使用する三角形のすべてのポイントが境界上にある場合は、境界セグメントを削除しないでください。この境界をあなたの道としてください。

私はこれをMathematicaで40個のランダムな点を使って実装しました。典型的な結果は次のとおりです。 ここに画像の説明を入力してください

明らかな反対意見は、すべてのポイントが境界ポイントであるとは限らないポイントに到達する可能性があることですが、境界を自己交差させずに境界セグメントを削除することはできません。これは正当な異議です。これが発生したケースを確認するのに数十回の実行が必要でしたが、最終的にこのケースが発生しました。 ここに画像の説明を入力してください

ローカルトポロジを使用してこれを修正するいくつかの明白な方法をおそらく見ることができますが、詳細はあなたに任せます！役立つかもしれない1つのことは、辺を共有する2つの三角形、たとえば三角形（p、q、r）と（q、p、s）を取り、それらを（r、p、s）と（ r、s、q）（三角形の周りのすべての座標は反時計回り）。これは、この変換で結果として得られる三角形も反時計回りに順序付けられている限り実行できます。

修正の必要性を減らすために、各ステップで削除するセグメントを適切に選択する必要があります。境界セグメントの長さの、候補三角形（セグメントとの潜在的に入ってくる点によって形成される三角形）の反対側の長さの合計に対する比率を使用しました。

于 2013-01-10T19:50:51.590 に答える
1

グラハム スキャンアルゴリズムを使用して問題を解決できると思います。

編集：一般に、凸包アルゴリズムは注目すべきものです。

于 2013-01-10T17:20:04.237 に答える
1

2 つのセグメントが交差しているかどうかのテストは、シンプルかつ高速です。たとえば、それを参照してください。

これにより、多角形を繰り返し構築できます。

ソース ポイント:S = {S0, ... Si, Sj,...}

最終ポリゴン:A = {A0, ... Ai, Aj,...}

あなたはSいっぱいでA空から始めます。

の最初の 3 点をSに移動しますA。もちろん、この三角形は自己交差ではありません。

次に、 untilSが空になるまで、その最初の残りのポイント ( と呼びます) を取得し、挿入できるP位置を探します。A

この位置は、 が他のセグメントとも交差しないことをi+1最初にi確認するためのものです。[Ai-P][Ai+1-P][Ak-Ak+1]

Aしたがって、新しいポリゴンは{A0, ... Ai, P, Ai+1, ...}

于 2013-01-10T17:09:38.860 に答える
0

Flutter と Dart の開発者はこれを使用できます。ポリゴンを作成するためにユーザーが選択したポイントを修正するためにこれを使用しています。ユーザーがマップ上にポリゴンを描画する場合、通常、点を順番にマークしません。

結果の例: この方法を使用して修正された左のもの、右のものはそうではありません。 ここに画像の説明を入力

これがPawelの答えのダーツ実装です。

      LatLng findCentroid(List<LatLng> points) {
        double x = 0;
        double y = 0;
        for (LatLng p in points) {
          x += p.latitude;
          y += p.longitude;
        }
        LatLng center = new LatLng(0, 0);
        center.latitude = x / points.length;
        center.longitude = y / points.length;
        return center;
      }
    
      List<LatLng> sortVerticies(List<LatLng> points) {
        // get centroid
        LatLng center = findCentroid(points);
    
        points.sort((a, b){
          double a1 = (radsToDegrees(Math.atan2(a.latitude - center.latitude, a.longitude - center.longitude)) + 360) % 360;
          double a2 = (radsToDegrees(Math.atan2(b.latitude - center.latitude, b.longitude - center.longitude)) + 360) % 360;
          return (a1 - a2).toInt();
        });
        return points;
      }
    
      num radsToDegrees(num rad) {
        return (rad * 180.0) / Math.pi;
      }
于 2020-12-23T10:27:46.453 に答える