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

Question

A polygon P is star-shaped if there exists a point p in the interior of P that is in the shadow of every point on the boundary of P. The set of all such points p is called the kernel of P.

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

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

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

Answer 1

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

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

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

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

我们对叉积 V₁ x V₂ 了解多少？如果 p₂ 位于多边形的边界与中心，该值会有何不同？对此的正确答案应该将我们的顶点分为两类。这些类别对于顺时针顺序与逆时针顺序有何不同？