使用指定的属性确定多边形

Question

我正在创建一个图形项目,我必须在某个时间点找到如果x在多边形内部存在一个点,如果我将此点连接到该多边形的所有顶点,那么所有连接顶点的线段和这一点都x在于完全在Polygon里面.

我想知道是否有一些着名的算法可以这样做,或者你们中的任何一个人都可以描述一个算法来做到这一点.

我正在寻找线性时间算法.

Answer 1

您询问如何计算星形多边形的内核。1979 年，Lee 和 Preparata 在一篇题为“寻找多边形核的最佳算法”的论文中解决了这个问题。从他们的摘要来看：

具有顶点K(P)的简单多边形的核是其所有顶点可见的内部点的轨迹。等效地，是由多边形的边确定的适当半平面的交集。尽管众所周知，找到通用半平面的交集需要时间，但我们表明可以利用与多边形边的序列相对应的半平面的排序来获得一种及时运行的核查找算法，并且因此是最佳的。PnPPK(P)nO(n log n)O(n)