Java:查找凸多边形的最外侧顶点

Question

原帖:

我正在尝试找到凸多边形的最外侧顶点(与多边形外的点P有关).现在,我只关心矩形(但是,我想要一个适用于任何凸多边形的算法).

我的计划是从外部点P到中心点C构造一条线.从该线的参考,我将构建从点线P至点1,2,3和4.由于点2和4将具有距参考线最大(最正)和最小(最负)角度,因此它们将被识别为最外侧顶点.

这是这项工作的最佳算法吗？如何从参考角度(最好用Java)计算角度？

---

更新澄清:

我绘制了线条(参考线为红色).如您所见,从P到2的线在参考线的一侧创建最大角度,而从P到4的线创建另一侧的最大角度.因此,这些是最外面的顶点.

Answer 1

我解决了这个问题如下：

            // 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;
                }
            }