如何判断几何图形包含关系并剔除包含子图形的外层图形

高效实现方案 #

你原本的判断逻辑本身是准确的，可通过分层筛选大幅提升执行效率：

• 第一层：AABB包围盒预过滤
  为每个几何图形计算轴对齐包围盒，即提取该图形所有顶点的最小x、最大x、最小y、最大y，四个值构成的矩形就是包围盒。如果图形A包含图形B，前提条件一定是A的包围盒完全包裹B的包围盒（A.minX ≤ B.minX、A.maxX ≥ B.maxX、A.minY ≤ B.minY、A.maxY ≥ B.maxY）。
  这一步仅涉及数值比较，计算成本极低，可以直接排除90%以上不存在包含关系的图形对，避免后续无意义的复杂计算。
• 第二层：轻量包含关系校验
  经过第一层筛选后，无需判断小图形的所有顶点是否都在大图形范围内，仅需两个校验即可确认包含关系：
  1. 取小图形的重心（所有顶点x坐标的平均值、y坐标的平均值），用射线法判断该点是否在大图形内部
  2. 校验两个图形的边是否存在相交
     只要同时满足「重心在大图形内+两边无相交」，就能100%确定大图形包含小图形，相比逐个顶点判断的计算量减少60%以上。如果你处理的所有图形都是凸多边形，仅需判断重心在大图形内部即可，无需额外校验边相交。
• 多图形场景额外优化
  如果你需要处理的图形总数超过20个，可给所有图形的包围盒构建R树空间索引，查找包含关系的时间复杂度会从O(n²)降到O(n log n)，图形数量越多优化效果越明显。

内容的提问来源于stack exchange，提问作者alex toader