跳至內容

連結距離

維基百科,自由的百科全書

計算幾何中,兩間的連結距離(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). 

延伸閱讀