二维点集Inner Convex Hull（内凸包）求解及相关文献问询

问题定义 #

你提到的需求属于计算几何领域的带锚点约束的最大空凸多边形（Maximum Empty Convex Polygon, MECP） 问题：给定由点集围成的带空洞的平面区域，求解完全位于空洞内部、且包含指定锚点（即你提到的红点）的面积最大的凸多边形。

现有方案的局限性 #

你当前使用的内外翻转+常规凸包计算的思路，本质是假设空洞边界是凸的，翻转后的点集的凸包逆变换正好对应内部最大凸多边形，一旦空洞存在内凹结构，翻转后的点集凸包会引入超出原空洞边界的区域，自然会出现异常结果，仅适用于凸空洞场景符合预期。

适配非凸空洞的可行解法 #

• 极角排序+半平面交法（推荐）
  这是当前处理带锚点约束场景的最优工业级实现方案，步骤如下：
  1. 以指定红点为原点，对空洞边界的所有顶点做极角排序
  2. 初始可行域设为全平面，按极角顺序逐个引入边界点生成的半平面约束（半平面区域完全落在空洞内部），每次引入后执行半平面交更新可行域
  3. 遍历所有极角分区后，取可行域中面积最大的半平面交结果，即为符合要求的最大内接凸多边形
     该方法支持任意简单多边形边界的非凸空洞，时间复杂度为O(n²)，n为空洞边界点数量。
• 增量扩展法
  适合点集稀疏的轻量化场景：
  1. 初始凸包取包含红点的最小凸结构，可直接用红点作为退化初始凸包
  2. 每次尝试将一个空洞内部的合法点加入凸包顶点集，重新计算凸包后验证凸包所有区域是否完全落在空洞内部
  3. 遍历所有合法组合后，记录面积最大的凸包结果即可
• 现成工具调用
  可以直接复用成熟计算几何库的封装能力降低开发成本：
  • CGAL库提供了maximum_empty_convex_polygon专用接口，原生支持边界约束、锚点约束配置
  • Python生态可配合shapely做空间合法性校验，搭配scipy的半平面交接口快速实现原型验证

核心参考文献 #

• 《Finding maximum empty rectangles, circles, and polygons in O(n² log n) time》（1986）：最早系统讨论最大空凸多边形求解的经典文献
• 《Efficient algorithms for the maximum empty convex polygon problem》（2007）：针对一般场景的算法优化，时间复杂度可降低到O(n log n)
• 《Constrained maximum empty convex polygons in a planar point set》（2019）：专门研究带内部锚点约束的MECP变种问题，完全匹配你的需求场景

内容的提问来源于stack exchange，提问作者Antonio Ribeiro