寻求将自定义2D多边形等面积分割的高效精确算法

你的网格离散化思路虽然直观，但存在精度依赖分辨率、高分辨率下计算效率低的问题。以下是几种速度和精度更优的替代方案：

1. 中轴线分割法 #

• 先计算多边形的中轴线（即所有到多边形两条边距离相等的点组成的集合）
• 在中轴线上寻找合适的点，绘制连接多边形边界的分割线，使得两部分面积相等
• 优势：完全基于多边形几何属性计算，无需离散化网格，精度可控；中轴线计算有成熟的高效算法，速度远快于高分辨率网格法；分割边界更贴合多边形的自然形态
• 注意：凹多边形的中轴线可能存在分支，需要筛选出能有效分割的分支路径

2. 扫描线二分法 #

• 选定一个初始方向（如水平、垂直），用扫描线从多边形一侧向另一侧移动
• 通过计算扫描线与多边形边的交点，实时统计扫过的面积，当面积达到总面积的一半时确定分割线
• 可以用二分法快速定位分割线位置：先确定扫描线的范围，不断取中间位置计算面积，逐步逼近目标分割点
• 优势：仅需遍历多边形的边进行交点计算，计算量小、速度快；精度由计算精度决定，不受网格分辨率限制，凸凹多边形都能处理

3. 重心引导分割法 #

• 先计算多边形的几何重心（对于简单多边形，可通过顶点坐标公式直接计算）
• 从重心出发绘制穿过多边形边界的直线，通过调整直线角度，找到使两部分面积相等的方向
• 角度调整可采用牛顿迭代等数值方法，收敛速度快
• 优势：重心计算高效成熟，分割过程的数值迭代成本低；精度高，适合大多数凸多边形和部分凹多边形
• 注意：若重心位于多边形外部，可改为从多边形边界上的点出发，结合重心方向进行分割调整

4. Voronoi单元合并法 #

• 在多边形内部均匀采样一定数量的点，构建Voronoi图
• 逐步合并面积较小的Voronoi单元，直到合并后的总面积接近多边形面积的一半
• 优势：分割边界平滑自然，适合对分割形态有要求的场景；采样点数量可灵活调整，平衡精度与速度
• 注意：采样密度直接影响精度，需根据需求合理设置

这些方案均避免了网格离散化带来的精度与速度的矛盾，在不同场景下各有优势，可根据多边形的复杂度、精度要求和效率需求选择合适的方法。

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