24小时热门版块排行榜

返回列表

【有奖交流】积极回复本帖子，参与交流，就有机会分得作者翟亚克的 10 个金币，回帖就立即获得 2 个金币，每人有 1 次机会

翟亚克

铁虫 (小有名气)

应助: 0 (幼儿园)
金币: 821
帖子: 181
在线: 21.4小时
虫号: 30260263

[交流] 新的跨学科启发算法 - 任意多边形最大内圆精确求解(已在IJGIS上发表，中科院一区Top)

向大家介绍我们2025.6 在中科院一区Top期刊《International Journal of Geographical Information Science (IJGIS)》在线发表的一项基础算法工作：Polycenter 算法。该算法解决了计算任意非自交多边形（包括凸多边形、凹多边形及带洞多边形）内部最大内切圆的精确求解问题。

算法核心优势：

   1、精确性：提供数学上精确的最大内圆解。
   2、高效性：实测比常用的近似算法（如 Polylabel）快约 10 倍。
   3、强适用性：能稳定处理凸多边形、任意凹多边形以及带洞多边形。特别解决了现有算法（如 Polylabel）在处理带平行边多边形时的失效问题。
   4、

基础性：作为一项基础几何算法，具有广泛的潜在应用价值。

算法原理简述 (三步迭代)：

   1、二分 (Bisection)：在多边形内任选一条直线，寻找圆心位于该直线上的最大可能圆（称为“极圆”）。方法是通过二分搜索迭代收敛到该直线上的最优圆心点。
   2、追逐 (Pursuit)：利用上一步找到的极圆，确定一条新的搜索直线，在该新直线上寻找更大的极圆。
   3、分治 (Divide & Conquer)：利用当前找到的所有极圆将原多边形分割为若干子多边形。理论证明，更大的内切圆必然存在于某个子多边形内。

迭代执行以上三步（在子多边形上应用二分-追逐-分治），直到所有子多边形的面积小于当前已知最大内圆的面积。此时找到的圆即为全局最大内切圆。

潜在应用领域 (欢迎补充探讨)：
鉴于其基础性与高效性，Polycenter 算法在众多需要定位多边形内部“中心”或“最宽敞空间”的场景中具有应用潜力，例如：

1、地理信息系统 (GIS)：为不规则地块（如行政区、土地利用斑块）确定最佳标注位置、地图综合（缩编）中的要素中心点计算。

2、机器人学/无人机导航：提供障碍物多边形内部的“最宽松”安全位置，用于路径规划、停靠点选择或避障策略。

3、计算机视觉/图像识别：为不规则目标区域提供稳定的初始定位点或形状描述特征。

4、材料科学：材料截面或颗粒的圆度分析（例如，计算最大内圆周长与多边形周长之比作为圆度指标）。

5、制造业与切割优化：在原材料（如皮革、布料、板材）的不规则轮廓内寻找可切割出的最大圆形部件，最大化材料利用率。

6、城市规划与计算机辅助设计 (CAD)：在复杂建筑平面或场地设计中定位关键设施点（如消防栓、树木、装饰元素）或评估空间开阔度。

7、水文学/地貌学：估算湖泊或其他水域剖面的最深处位置。

8、计算几何：作为凸包计算或其他几何算法的预处理步骤。

9、工程学 (狭缝计算)：定义和计算不规则形状狭缝的有效宽度（常被定义为该狭缝多边形剖面的最大内圆直径）。

10、医学图像分析：在组织切片或细胞图像中，定位不规则区域内的“核心”区域或测量形态学指标。

11、游戏开发/物理模拟：在复杂碰撞体内快速定位可供物体放置或生成的安全空间。

12、芯片设计/微流控：在复杂微通道或腔室布局中寻找最大可用空间点。

论文地址: https://doi.org/10.1080/13658816.2025.2514056

源代码: https://doi.org/10.6084/m9.figshare.28244642

期待Polycenter能在各位研究者的相关领域带来新的启发或解决实际问题。非常欢迎大家试用代码、反馈意见，并探讨其在您所在学科中的潜在应用场景！

回复此楼