fbpx
维基百科

連結距離

二月 10, 2024

在计算几何中，兩點間的連結距離（link distance）是指多邊形內以兩點為端點的任意折線之最小線段數。 多邊形的最大連結距離稱為該多邊形的連結直徑（link diameter）。[1]

簡單多邊形的連結直徑可以在O(n log n)時間內完成計算。[2]

定義 编辑

多邊形內兩點的連結距離定義為：

  • 在多邊形P內部兩點x與y的連結距離可以表示為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）. 

延伸閱讀 编辑

  • Maheshwari, Anil; Sack, Jörg-Rüdiger; Djidjev, Hristo N., Link distance problems, Handbook of Computational Geometry, North-Holland, Amsterdam: 519–558, 2000, MR 1746684, doi:10.1016/B978-044482537-7/50013-9 

二月 10, 2024
連結距離, 在计算几何中, 兩點間的, link, distance, 是指多邊形內以兩點為端點的任意折線之最小線段數, 多邊形的最大稱為該多邊形的連結直徑, link, diameter, 簡單多邊形的連結直徑可以在o, 時間內完成計算, 目录, 定義, 例子, 參見, 參考文獻, 延伸閱讀定義, 编辑多邊形內兩點的定義為, 在多邊形p, 內部兩點x, 與y, 的可以表示為dl, 則多邊形p, 的dl, 為在點x, 與點y, 之間繪製保持在多邊形p, 內部的折線, 連續線段鏈, 且這些線段不與邊界相交, 也都不會. 在计算几何中 兩點間的連結距離 link distance 是指多邊形內以兩點為端點的任意折線之最小線段數 多邊形的最大連結距離稱為該多邊形的連結直徑 link diameter 1 簡單多邊形的連結直徑可以在O n log n 時間內完成計算 2 目录 1 定義 2 例子 3 參見 4 參考文獻 5 延伸閱讀定義 编辑多邊形內兩點的連結距離定義為 在多邊形P 內部兩點x 與y 的連結距離可以表示為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 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 Suri Subhash On some link distance problems in a simple polygon IEEE transactions on Robotics and Automation IEEE 1990 6 1 108 113 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 Aichholzer Oswin and Aurenhammer Franz and Hurtado Diaz Fernando Alfredo and Ramos Pedro A and Urrutia J Two convex polygons 25th European Workshop on Computational Geometry Universite Libre de Bruxelles 2009 117 120 2023 11 26 原始内容存档于2022 07 05 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 Bose Prosenjit and Toussaint Godfried Geometric and computational aspects of manufacturing processes Computers amp graphics Elsevier 1994 18 4 487 497 2023 11 26 原始内容存档于2023 11 26 延伸閱讀 编辑Maheshwari Anil Sack Jorg Rudiger Djidjev Hristo N Link distance problems Handbook of Computational Geometry North Holland Amsterdam 519 558 2000 MR 1746684 doi 10 1016 B978 044482537 7 50013 9 取自 https zh wikipedia org w index php title 連結距離 amp oldid 80498360, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。