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 需要一段时间（从我的偶然情况来看），但我认为 Wikipedia 条目将为您提供一个很好的起点。

于 2012-04-02T01:50:43.510 回答
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 回答
0

三角函数的使用非常缓慢。您应该使用另一个角度比较。

对于两个平面向量之间的角度：

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 回答