7

元の投稿：

凸多角形の最も外側の頂点を見つけようとしています（多角形の外側の点Pに関連して）。今のところ、私は長方形だけに関心があります（ただし、任意の凸多角形で機能するアルゴリズムが必要です）。

ポイントデモンストレーション

私の計画は、外部点Pから中心点Cまでの線を作成することです。この参照線から、点Pから点1、2、3、4までの線を作成します。ポイント2と4は、基準線から最大（最も正）と最小（最も負）の角度を持つため、最も外側の頂点として識別されます。

これは仕事に最適なアルゴリズムですか？参照角度から角度を計算するにはどうすればよいですか（できればJavaで）？

明確化のための更新：

ここに画像の説明を入力してください

線を引きました（赤の参照線）。ご覧のとおり、Pから2までの線は、基準線の一方の側に最大の角度を作成し、 Pから4までの線は、もう一方の側の最大の角度を作成します。したがって、これらは最も外側の頂点です。

4

3 に答える 3

2

これはほとんど凸包の問題です。ポリゴンの周りの頂点のセット（x 1、x 2 ）を探します。適用される方法論は「クイックハル」と呼ばれ、クイックソートに似ています（ステップスルーするたびにポイントの領域を分割するという点で）。また、 Pを任意の始点とその平行な終点の間の中点として使用できることも安全な仮定であるため、 Pの周りに凸包が得られます。

（私の偶然から）信頼できるJavaを作成するにはしばらく時間がかかりますが、ウィキペディアのエントリは素晴らしい出発点になると思います。

于 2012-04-02T01:50:43.510 に答える
0

三角法の使用は非常に遅いです。別の角度比較を使用する必要があります。

2つのフラットベクトル間の角度の場合：

cos（OA、OB）=（OA x * OB x + OA y * OB y）/ sqrt（（OA x 2 + OA y 2）*（OB x 2 + OB y 2））

余弦定理のある角度を比較できると思います。

于 2012-04-01T21:13:32.483 に答える
0

私は次のように問題を解決しました：

            // code simplified for demonstration
            double angleBetweenVertices;
            double maxAngleBetweenVertices;
            vectorA.setStartingPoint(outerPoint);
            vectorA.setTerminationPoint(polygonCenter);
            vectorB.setStartingPoint(outerPount);

            // For each vertex, calculate the angle between the outer point, the polygon's center and the vertex
            for (Point2D.Double vertex : vertices) {    
                vectorB.setTerminationPoint(vertex);
                double angleBetweenVertices = 
                    Math.toDegrees(
                        Math.atan2(
                            (vectorA.perpDotProduct(vectorB)),
                            (vectorA.dotProduct(vectorB)) 
                        )
                    );

                // Update the min and Max
                if (angleBetweenVertices >= maxAngleBetweenVertices) {
                    maxVertex = vertex;
                    maxAngleBetweenVertices = angleBetweenVertices;
                } else if (angleBetweenVertices <= minAngleBetweenVertices) {
                    minVertex = vertex;
                    minAngleBetweenVertices = angleBetweenVertices;
                }
            }
于 2012-04-17T02:52:34.383 に答える