不规则多边形标签中心查找方法

标签定位算法演进总结

尝试过的方法

1. Shoelace 质心（最初方法）

计算多边形面积加权质心：(1/(6A)) * Σ(xi+xj)(xiyj-xj*yi)

  ┌─────────────┐
  │   ●         │  圆形：顶点分布不均 → 质心偏移
  │  ●●●●●      │  ☓ 标签偏下（底边顶点密，拉低了质心）
  │ ●●●●●●●     │
  │  ●●●●●      │
  │   ●         │
  └─────────────┘

有效场景：凹多边形（L 形、C 形），质心通常在有效内部位置 失败场景：顶点分布不均匀的凸多边形（如圆形用更多顶点描述底部）

2. 包围盒中心优先（在内部时使用）

  ┌─────────────┐
  │             │  优先使用 (minX+maxX)/2, (minY+maxY)/2
  │      ●      │
  │             │  ☓ 凹多边形中靠近边缘（bbox 中心在窄区）
  │    ┌──┐     │
  │    │  │●    │
  │    └──┘     │
  └─────────────┘

有效场景：圆形、矩形等规则凸形状 失败场景：凹多边形（bbox 中心虽在内部，但紧贴边缘）

3. 凸/凹分类切换

用 IsConvex() 检测多边形类型，凸的用 bbox 中心，凹的用 shoelace 质心。

  ┌─────────────┐  圆形被正确识别为凸 → bbox 中心 → 位置正确
  │             │  不规则形状 → 凹 → shoelace 质心 → 勉强可用
  │      ●      │  ☓ 但 shoelace 质心仍有顶点分布不均问题
  │    ●●●●●    │
  │   ●     ●   │  ☓ 边界情况分类不准确
  │    ●   ●    │
  └─────────────┘

失败场景：分类二元对立，实际形状介于凸凹之间时表现不稳定

4. Shoelace 质心 Y + 水平扫描 X

保留质心的 Y 坐标，在该 Y 处水平扫描找最长内部段的中点做 X：

      扫描线 → ●─────────●  → 取中点
      ┌──────────┐
      │  扫描线  │
      │    ●     │  ☓ Y 坐标仍受质心偏移影响
      │  ●●●●●   │
      └──────────┘

有效场景：X 方向始终居中，修正了水平偏差 失败场景：Y 坐标仍是质心 Y，对于顶点不均导致的质心偏移无能为力，本质是降维修补

最终方法：Polylabel

核心思想：不依赖顶点分布，也不依赖包围盒。直接在几何空间里搜索"离所有边最远的内部点"。

算法步骤

  迭代 1:                   迭代 6 后:
  ┌──┬──┬──┬──┐            ┌────────────────┐
  │  │  │  │  │            │                │
  ├──┼──┼──┼──┤            │       ●        │  ← 离所有边等距
  │  │  │  │  │   → ... →  │                │    的最优标签点
  ├──┼──┼──┼──┤            │                │
  │  │  │  │  │            └────────────────┘
  └──┴──┴──┴──┘

初始网格(短边/8) 最优候选点

每轮执行:

1. 按 PolyDist 降序排列所有格子
2. 保留前 20 个
3. 检查是否优于当前 best → 更新
4. 有潜力 → 细分为 4 个子格
5. 重复 6 轮

关键函数 PolyDist(px, py)

为每个候选点计算到多边形所有边的最小距离：

• 点在内部 → 返回正值（距最近边的距离）
• 点在外部 → 返回负值

这样算法自动排除外部点，只在内部区域竞争，最终收敛到离各边最远的点。

为什么能解决所有问题

  ┌────────────────────┬────────────────────────────┬────────────┐
  │      形状类型      │       Polylabel 行为       │    效果    │
  ├────────────────────┼────────────────────────────┼────────────┤
  │ 圆形（顶点不均匀） │ 只基于边距离，不看顶点密度 │ 精确中心   │
  ├────────────────────┼────────────────────────────┼────────────┤
  │ 凹多边形（L 形等） │ 找到最宽敞的内部位置       │ 远离边缘   │
  ├────────────────────┼────────────────────────────┼────────────┤
  │ 不规则形状         │ 自适应任何几何形态         │ 最优内部点 │
  └────────────────────┴────────────────────────────┴────────────┘

本质上 Polylabel 搜索的是多边形内部的最大内切圆圆心，这是标签位置的数学最优解。