跳转到内容

连结距离

维基百科,自由的百科全书

计算几何中,两间的连结距离(link distance)是指多边形内以两为端点的任意折线之最小线段数。 多边形的最大连结距离称为该多边形的连结直径(link diameter)。[1]

简单多边形的连结直径可以在O(n log n)时间内完成计算。[2]

定义

多边形内两连结距离定义为:

  • 在多边形P内部两xy的连结距离可以表示为dL(x,y)[1]
  • 则多边形P的连结距离dL(x,y)为在点x与点y之间绘制保持在多边形P内部的折线(连续线段链),且这些线段不与边界相交[1],也都不会超出多边形P的范围,即不跑到多边形P的外部;在满足这个条件下,能以最少线段构成折线连接这两点的折线线段数量即为dL(x,y)[1]
  • 也就是说,如果两点之间能完全在多边形内部以一条直线段连接,则该两点的连结距离为1。[1]

例如:

  • 凸多边形的任两点连结距离必定为1,因为凸多边形内任两点都可以直接被单一线段连接[1](连结距离考虑的是最小数量)
  • 马蹄形则有可能出现3或以上的连结距离,因为若选取的两点位于马蹄形的极端两侧,则需要例如ㄇ字形的折线来连接两点。

多边形连结直径定义为:

  • 在多边形内任取两点评估其连结距离,其连结距离的最大值即为多边形的连结直径。[3]
  • 两点是任取两点,因此需要考虑到极端情况。

例子

若多边形的连结直径为1,则他是凸多边形,反之亦然。每个星状多边形的的连结直径最多为2[4][5]:在星状多边形中可以透过在其星状核内部弯曲一次来完成两点连接。然而连结直径为2的多边形并不一定都是星状多边形,因为也存在有孔洞的多边形,其连结直径为2。此外,亦存在连结直径4或5或以上的几何图形。[6]

参见

参考文献

  1. ^ 1.0 1.1 1.2 1.3 1.4 1.5 Bose, Prosenjit and Toussaint, Godfried. Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications. Proceedings of CG International'96 (IEEE). 1996: 102–111. 
  2. ^ Suri, Subhash. On some link distance problems in a simple polygon. IEEE transactions on Robotics and Automation (IEEE). 1990, 6 (1): 108–113. 
  3. ^ Alsuwaiyel, Muhammed H and Lee, DT. Minimal link visibility paths inside a simple polygon. Computational Geometry (Elsevier). 1993, 3 (1): 1–25 [2023-11-26]. (原始内容存档于2023-11-27). 
  4. ^ Aichholzer, Oswin and Aurenhammer, Franz and Hurtado Díaz, Fernando Alfredo and Ramos, Pedro A and Urrutia, J. Two-convex polygons. 25th European Workshop on Computational Geometry (Université Libre de Bruxelles). 2009: 117–120 [2023-11-26]. (原始内容存档于2022-07-05). 
  5. ^ R. MajdNia. Extentions of algorithms for minimum bends geometric embedding of trees onto the points inside polygons (Master thesis论文). Computer engineering and IT dep., Amirkabir University of Tech. 2012-02. 
  6. ^ Bose, Prosenjit and Toussaint, Godfried. Geometric and computational aspects of manufacturing processes. Computers & graphics (Elsevier). 1994, 18 (4): 487–497 [2023-11-26]. (原始内容存档于2023-11-26). 

延伸阅读