| 查看: 3306 | 回复: 44 | |||
| 【有奖交流】积极回复本帖子，参与交流，就有机会分得作者 翟亚克 的 10 个金币 ，回帖就立即获得 2 个金币，每人有 1 次机会 | |||
[交流]
新的跨学科启发算法 - 任意多边形最大内圆精确求解(已在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能在各位研究者的相关领域带来新的启发或解决实际问题。非常欢迎大家试用代码、反馈意见，并探讨其在您所在学科中的潜在应用场景！ |
回复此楼» 猜你喜欢
315分求调剂
已经有3人回复
-
材料与化工304求B区调剂
已经有3人回复
-
一志愿天津大学339材料与化工求调剂
已经有3人回复
-
297求调剂
已经有3人回复
-
一志愿北京化工大学材料与化工（085600）296求调剂
已经有3人回复
-
打过很多竞赛，085406控制工程300分，求调剂
已经有3人回复
-
北京林业大学硕导招生广告
已经有5人回复
-
一志愿北京化工大学材料与化工 264分各科过A区国家线
已经有4人回复
-
一志愿 西北大学 总分282 英语一62 求调剂
已经有4人回复
-
274求调剂
已经有15人回复
» 本主题相关商家推荐: (我也要在这里推广)
» 抢金币啦！回帖就可以得到:
-
温柔善良，重庆女孩，找男友……好像是乱码，内容在40楼看查看
+2/382
-
课题组接收化学、材料科学与工程、材料工程及化学工程专业硕士研究生
+1/185
-
中国科学院青岛生物能源与过程研究所 招生2-3名联培生
+1/181
-
澳门科技大学创新工程学院诚招博士生
+2/136
-
艾里卡特 (Alicat) - 燃料电池测试系统与质量流量和压力仪表
+3/100
-
马尔文激光粒度+纳米粒径Zeta电位测试原始数据与Origin绘图V131/2039/8821
+1/91
-
太原科技大学材料科学与工程学院招收金属材料类博士一名
+1/85
-
坐标广州，征女友
+2/82
-
广东工业大学-木质纤维素高值化利用团队招博士研究生
+1/80
-
南方油校——资源与环境专硕招生，化学环境生物类专业均可，就业好，有专业壁垒
+1/48
-
【全额奖学金+英国博士学位】国科大杭高院Nathan课题组招收2026级联培博士生1名！
+1/46
-
天津城建大学招收物理、化学或者生物调剂生一名，前往天津大学联合培养
+1/43
-
上海大学 “生物有机电子材料及器件”团队硕士、博士研究生招聘
+1/35
-
上海中医药大学创新中药研究院 招收审核制博士生一名
+1/18
-
双一流湘潭大学化工学院招收化工、能源动力、工程热物理相关研究生调剂
+1/14
-
广东唯一石化院校——资源与环境专硕招生
+1/13
-
中国科学技术大学纳米科学技术学院张振教授/江雷院士诚招2026级博士
+1/6
-
香港大学 化学系 博后招聘
+1/4
-
山东烟台某高校材料专业研究生调剂
+1/4
-
天津大学浙江研究院（宁波）诚聘高分子/化学/材料/石化方向博士后
+1/2
3楼2025-07-22 11:47:04
6楼2025-07-22 11:59:16
9楼2025-07-22 12:03:58
10楼2025-07-22 12:05:19
14楼2025-07-22 12:36:43
35楼2025-07-25 15:03:13
42楼2025-07-28 22:22:27
43楼2025-07-30 08:19:02
简单回复
tzynew2楼
2025-07-22 11:42
回复
翟亚克(金币+1): 谢谢参与
k 发自小木虫手机客户端
2025-07-22 11:49
回复
翟亚克(金币+1): 谢谢参与
牛！ 发自小木虫IOS客户端
2025-07-22 11:55
回复
翟亚克(金币+1): 谢谢参与
tfang7楼
2025-07-22 12:01
回复
tfang8楼
2025-07-22 12:03
回复
xiaoqiuqiu2011楼
2025-07-22 12:17
回复
翟亚克(金币+1): 谢谢参与
jiaoxg12楼
2025-07-22 12:20
回复
翟亚克(金币+1): 谢谢参与
nono200913楼
2025-07-22 12:36
回复
翟亚克(金币+1): 谢谢参与
。 发自小木虫手机客户端
我才是肖牧冲15楼
2025-07-22 12:42
回复
翟亚克(金币+1): 谢谢参与
。 发自小木虫手机客户端
zusn16楼
2025-07-22 12:50
回复
bjdxyxy17楼
2025-07-22 12:57
回复
翟亚克(金币+1): 谢谢参与
。 发自小木虫手机客户端
gter_wang18楼
2025-07-22 13:26
回复
翟亚克(金币+1): 谢谢参与
fqcgfqcgfqcg19楼
2025-07-22 16:37
回复
翟亚克(金币+1): 谢谢参与
。 发自小木虫手机客户端
miaojiabing20楼
2025-07-22 16:41
回复
翟亚克(金币+1): 谢谢参与
庚辰辛丑21楼
2025-07-22 17:36
回复
翟亚克(金币+1): 谢谢参与
maoge201022楼
2025-07-22 18:43
回复
翟亚克(金币+1): 谢谢参与
m 发自小木虫手机客户端
XG-WUST23楼
2025-07-22 19:19
回复
翟亚克(金币+1): 谢谢参与
up 发自小木虫IOS客户端
psylhh24楼
2025-07-22 20:43
回复
翟亚克(金币+1): 谢谢参与
tableman25楼
2025-07-23 09:35
回复
翟亚克(金币+2): 谢谢参与
s9659z26楼
2025-07-23 09:37
回复
翟亚克(金币+2): 谢谢参与
美人智00827楼
2025-07-23 10:03
回复
翟亚克(金币+2): 谢谢参与
曾经沧海a28楼
2025-07-23 10:16
回复
翟亚克(金币+2): 谢谢参与
shenrenren29楼
2025-07-23 12:30
回复
翟亚克(金币+2): 谢谢参与
jjliouu30楼
2025-07-23 16:52
回复
翟亚克(金币+2): 谢谢参与
++
erjianxin31楼
2025-07-23 17:57
回复
翟亚克(金币+2): 谢谢参与
。。 发自小木虫IOS客户端
lymjjh32楼
2025-07-23 21:05
回复
翟亚克(金币+2): 谢谢参与
假大空33楼
2025-07-24 13:10
回复
翟亚克(金币+2): 谢谢参与
·
云梦轻舟34楼
2025-07-25 13:02
回复
翟亚克(金币+2): 谢谢参与
。 发自小木虫手机客户端
seaskyy36楼
2025-07-26 06:38
回复
翟亚克(金币+2): 谢谢参与
3
心月孤悬37楼
2025-07-26 07:43
回复
翟亚克(金币+2): 谢谢参与
梦书之城38楼
2025-07-26 07:58
回复
luciferosa39楼
2025-07-26 08:46
回复
翟亚克(金币+2): 谢谢参与
heyu013540楼
2025-07-28 14:20
回复
翟亚克(金币+2): 谢谢参与
LifePursuit41楼
2025-07-28 18:00
回复
翟亚克(金币+2): 谢谢参与
嗯 发自小木虫手机客户端
翟亚克44楼
2025-08-05 21:42
回复
超级老快45楼
2025-08-05 23:17
回复
翟亚克(金币+2): 谢谢参与
q 发自小木虫手机客户端
