扩展凸包以减少边
Expanding Convex Hull to Reduce Sides
我们有一组凸包不重叠的标记点。凸包之间有一些空space。
给定一个不在我们数据中的未标记点，我们想大致确定它位于哪个凸包内。
为了加快计算速度，我们想减少凸包的边数（从而使凸包扩大一点，但不要太多）。
我可以使用哪些算法？
更新：理想情况下，我想在不与给定的附近多边形相交的约束下进行扩展。 （这个约束的动机是我有几个不相交的船体，我想减少它们的边数，同时仍然保持它们不相交。但是把它当作一个括号，因为我不想做联合修改。我是很高兴修改一个船体，同时保持其他船体不变。我很高兴破解这个简单的案例，以迭代方式进行联合修改。）
也许这值得一试。
求A联合x的凸包A'，凸包 B 联合 x 的 B'。
Select 增加船体面积最少的那个。
在下面的示例中，A' 是获胜者。
为回应评论而添加：
一条路线是通过 "minimal enclosing k-gons":
- Mictchell 等人："Minimum-Perimeter Enclosing k-gon" 2006 (CiteSeer link)
- Aggarwal 等人："Minimum Area Circumscribing Polygons" 1985 (CiteSeer link)
- O'Rourke 等人："An optimal algorithm for fnding minimal enclosing triangles" 1986，Algorithmica (ACM link)
但是，这些算法非常复杂，不太可能有多大帮助。
如果在粗略阶段包含检查中少处理一个边缘所节省的时间被充气船体增加的误报率所抵消，我不会感到惊讶。事实上，您甚至可能让 更多 为自己工作 - 通过粗略阶段检查的每个点无论如何都必须根据真实船体进行检查。
与其尝试减少 O(n) 中的 n 包含支票，我很想直接使用一些摊销的东西 O(1) 粗略的传递：
- 第 1 遍 - 检查轴对齐边界框 (AABB)。这可以快速拒绝多边形外的绝大多数点。
- 第 2 遍 - 将 AABB 划分为网格，其中每个网格四边形处于三种状态之一：完全在船体外部、与船体边缘相交或完全在船体内部。如果您的观点在 "in" 或 "out" 四边形中，您可以到此为止。
- 第 3 遍 - 与多边形相交的网格四边形中的任何点都会照常检查船体。
可以提前计算网格的状态：
- 将每个网格四边形初始化为船体外部
- 使用 this answer 中链接的算法在网格上追踪外壳的边缘并设置所有相交的四边形。
- 网格现在包含船体的轮廓，因此使用简单的填充或扫描线方法来查找和设置船体内部的所有四边形。
可以改变网格的分辨率，以在内存成本（每个四边形 2 位）和误报率（低分辨率网格将导致更多 O(n) 常规船体检查）之间进行权衡。
"point in convex polygon" 测试并不昂贵，因为它可以在 Lg(N) 比较中通过二分法执行（用一条直线将多边形一分为二，递归地直到剩下一个三角形). N 是边数。实际上，27（或 130）条边的多边形的成本是三角形的两倍（三倍）。
如果您有很多船体，将点与每个船体进行详尽比较是一种浪费。有更好的方法，例如使用单调细分，这可以在预处理后将总共 M 边的搜索时间降低到 O(Log(M)) 查询时间。
看起来你的最终目标并不是关于凸包，而是关于解决点定位问题 (https://en.wikipedia.org/wiki/Point_location)。而且您似乎决心通过简单地针对多个凸包反复检查您的观点来解决它。虽然我了解凸包的来源（它们实际上代表点集），但仍然不是在算法中直接使用它们的理由。点定位问题可以通过许多更有效的算法（如基于梯形分解的搜索树）来解决，这些算法对外壳中的边数不太敏感。
我们有一组凸包不重叠的标记点。凸包之间有一些空space。
给定一个不在我们数据中的未标记点，我们想大致确定它位于哪个凸包内。
为了加快计算速度，我们想减少凸包的边数（从而使凸包扩大一点，但不要太多）。
我可以使用哪些算法？
更新：理想情况下，我想在不与给定的附近多边形相交的约束下进行扩展。 （这个约束的动机是我有几个不相交的船体，我想减少它们的边数，同时仍然保持它们不相交。但是把它当作一个括号，因为我不想做联合修改。我是很高兴修改一个船体，同时保持其他船体不变。我很高兴破解这个简单的案例，以迭代方式进行联合修改。）
也许这值得一试。 求A联合x的凸包A'，凸包 B 联合 x 的 B'。 Select 增加船体面积最少的那个。 在下面的示例中，A' 是获胜者。
为回应评论而添加： 一条路线是通过 "minimal enclosing k-gons":
- Mictchell 等人："Minimum-Perimeter Enclosing k-gon" 2006 (CiteSeer link)
- Aggarwal 等人："Minimum Area Circumscribing Polygons" 1985 (CiteSeer link)
- O'Rourke 等人："An optimal algorithm for fnding minimal enclosing triangles" 1986，Algorithmica (ACM link)
但是，这些算法非常复杂，不太可能有多大帮助。
如果在粗略阶段包含检查中少处理一个边缘所节省的时间被充气船体增加的误报率所抵消，我不会感到惊讶。事实上，您甚至可能让 更多 为自己工作 - 通过粗略阶段检查的每个点无论如何都必须根据真实船体进行检查。
与其尝试减少 O(n) 中的 n 包含支票，我很想直接使用一些摊销的东西 O(1) 粗略的传递：
- 第 1 遍 - 检查轴对齐边界框 (AABB)。这可以快速拒绝多边形外的绝大多数点。
- 第 2 遍 - 将 AABB 划分为网格，其中每个网格四边形处于三种状态之一：完全在船体外部、与船体边缘相交或完全在船体内部。如果您的观点在 "in" 或 "out" 四边形中，您可以到此为止。
- 第 3 遍 - 与多边形相交的网格四边形中的任何点都会照常检查船体。
可以提前计算网格的状态：
- 将每个网格四边形初始化为船体外部
- 使用 this answer 中链接的算法在网格上追踪外壳的边缘并设置所有相交的四边形。
- 网格现在包含船体的轮廓，因此使用简单的填充或扫描线方法来查找和设置船体内部的所有四边形。
可以改变网格的分辨率，以在内存成本（每个四边形 2 位）和误报率（低分辨率网格将导致更多 O(n) 常规船体检查）之间进行权衡。
"point in convex polygon" 测试并不昂贵，因为它可以在 Lg(N) 比较中通过二分法执行（用一条直线将多边形一分为二，递归地直到剩下一个三角形). N 是边数。实际上，27（或 130）条边的多边形的成本是三角形的两倍（三倍）。
如果您有很多船体，将点与每个船体进行详尽比较是一种浪费。有更好的方法，例如使用单调细分，这可以在预处理后将总共 M 边的搜索时间降低到 O(Log(M)) 查询时间。
看起来你的最终目标并不是关于凸包，而是关于解决点定位问题 (https://en.wikipedia.org/wiki/Point_location)。而且您似乎决心通过简单地针对多个凸包反复检查您的观点来解决它。虽然我了解凸包的来源（它们实际上代表点集），但仍然不是在算法中直接使用它们的理由。点定位问题可以通过许多更有效的算法（如基于梯形分解的搜索树）来解决，这些算法对外壳中的边数不太敏感。