algorithm - 在 O(n) 时间内计算星形多边形的凸包

Question

如果多边形内部有一个点在 边界上的每个点的阴影中，则该多边形P是星形的。所有这些点的集合称为的核。pPPpP

例如，在五角星中，P如果光源被认为是无穷大，则可以从位于边界上的所有点的阴影到达中心点。星形多边形不一定是星形。

P给定一个由其顶点按逆时针顺序指定的 n 顶点星形多边形，如何在线性时间内计算该多边形的凸包。

我对这个问题一无所知。我能想到的算法是 O(n * log(n))。我无法理解如何使用这些额外的信息。

Answer 1

我假设这是某种家庭作业，无论是分配给班级还是您自己的学习，所以我只是给你一个提示：

这里的关键是逆时针顺序，或者更准确地说，顶点的顺序是一致的。

给定三个连续的顶点 p ₁、 p ₂和 p ₃，考虑由以下定义的两个向量：

V ₁ = (p ₁ - p ₂ ) 和
V ₂ = (p ₃ - p ₂ )。

我们对叉积 V ₁ x V ₂了解多少？_{如果 p 2}在多边形的边界上而不是在中心，这个值会有什么不同？对此的正确答案应该将我们的顶点分为两类。这些类对于顺时针而不是逆时针排序有何不同？