fbpx
维基百科

折線

一月 14, 2024

折線又稱多邊形鏈（polygonal chain）[註 1]或多段線（polyline）[5]是指一系列相連的線段，通常是一些任意不同方向的直線段首尾相連結所形成的線[7]。 與多邊形不同，折線並不要求線的整體要頭尾封閉。 更正式地說，折線P是由一系列稱為其頂點的點所決定的曲線，該曲線連續地由線段連接這些頂點所構成。

簡單折線
自相交折線
封閉折線

變體 编辑

簡單折線 编辑

簡單折線是指該折線的線段連續相交，且僅有在線段的端點相交，沒有在別處有相交（即非自相交的折線）。

封閉折線 编辑

封閉折線是指第一個頂點與最後一個頂點重合，或者第一個頂點與最後一個頂點也相連的折線。[8] 平面的簡單封閉折線是簡單多邊形的邊界。 通常，「多邊形」這個術語就是指「封閉折線」，但在某些情況下還是會將封閉折線和多邊形兩個概念區分開來。

單調折線 编辑

如果存在一條直線L，且垂直於L的每條直線最多與該折線相交一次，則稱該折線是一個單調折線。每個非平凡的單調多邊形鏈都是非封閉的（開放的）。 相較之下，每個單調多邊形（封閉折線）都恰好可以分割成兩個單調折線。[9] 分段線性函數的圖形相對於水平線形成單調折線。 一般的折線圖也都是相對於某座標軸的單調折線。

參數化 编辑

 
在一個點的數量n=17之點集中，有一條由四個線段組成的同正負斜率之折線

折線的每個線段通常使用連續頂點間的線性插值來線性參數化。 在實際應用中，對於整條折線而言有兩種常見的參數化方式。 一種是：折線之線段鏈的每一段都可以被分配與第一個頂點對應索引的參數之單位區間； 另一種是：折線之線段鏈的每一段都可以被分配一個與該段的長度相對應的參數區間，使得該參數沿著整個折線之線段鏈統一對應於其曲線長。

與點集的關聯 编辑

每個至少有n個點的點集都包含一條至少有 條邊的斜率正負相同之折線路徑。 這是埃爾多斯-塞克雷斯定理（英语：Erdős–Szekeres_theorem）的推論。

應用 编辑

折線通常可以用來近似更複雜的曲線。 在這種情況下，道格拉斯-普克演算法可以用於尋找具有最少線段但又足夠接近原始曲線的折線，作為該曲線精確的近似。[10][11]

在圖繪製（英语：graph drawing）中，折線常用於表示圖的邊，在繪圖樣式中，將邊繪製為直線段可能會導致交叉、邊與頂點碰撞或其他不希望出現的特徵。 在這種情況下，通常希望用盡可能少的線段和彎曲來繪製圖的邊，以減少繪圖中的視覺混亂； 最小化彎曲次數的問題稱為彎曲最小化問題（英语：Bend minimization）。[12]

折線也是计算几何的一種基本資料類型。 例如，李德財和普雷帕拉塔（英语：Franco_P._Preparata）的點定位演算法就是透過將任意曲面細分分解為單調折線的有序序列來進行操作，以達到可以透過二分搜尋來解決點位置查詢問題的目標； 此方法後來經過改進，使得點定位問題的時間複雜度得到最佳化。[13]

參見 编辑

註釋 编辑

  1. ^ 多邊形鏈（polygonal chain）有時也稱為多邊曲線（polygonal curve[1]）、多邊路徑（polygonal path[2]）、折線（polyline[3]、broken line[4][5]）、分段線性曲線（piecewise linear curve[3]），或者在地理信息系统中稱為線串（linestring）或線性環（linear ring）[6]

參考文獻 编辑

  1. ^ Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario, Computer Graphics: Theory and Practice, CRC Press: 186, 2012, ISBN 9781568815800 .
  2. ^ Cheney, Ward, Analysis for Applied Mathematics, Graduate Texts in Mathematics 208, Springer: 13, 2001, ISBN 9780387952796 .
  3. ^ 3.0 3.1 Boissonnat, Jean-Daniel; Teillaud, Monique, Effective Computational Geometry for Curves and Surfaces, Springer: 34, 2006, ISBN 9783540332596 .
  4. ^ Muggeo, Vito M. R., segmented: An R package to fit regression models with broken-line relationships (PDF), R News, May 2008, 8 (1): 20–25 
  5. ^ 5.0 5.1 折線 polyline. 雙語詞彙、學術名詞暨辭書資訊網. 國家教育研究院. [2023-12-03]. （原始内容存档于2023-12-03）. 
  6. ^ Open Geospatial Consortium, Herring, John R. , 编, OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture, 1.2.1, Open Geospatial Consortium, 2011-05-28 [2016-01-15], （原始内容于2017-01-29） 
  7. ^ 折線. 教育部重編國語辭典. [2023-11-17]. （原始内容于2023-11-17）. 
  8. ^ Mehlhorn, Kurt; Näher, Stefan, LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press: 758, 1999, ISBN 9780521563291 .
  9. ^ O'Rourke, Joseph, Computational Geometry in C, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press: 45, 1998, ISBN 9780521649766 .
  10. ^ Ramer, Urs, An iterative procedure for the polygonal approximation of plane curves, Computer Graphics and Image Processing, 1972, 1 (3): 244–256, doi:10.1016/S0146-664X(72)80017-0 .
  11. ^ Douglas, David; Peucker, Thomas, Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, The Canadian Cartographer, 1973, 10 (2): 112–122, doi:10.3138/FM57-6770-U75U-7727 .
  12. ^ Tamassia, Roberto, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, 1987, 16 (3): 421–444, doi:10.1137/0216030 .
  13. ^ Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge, Optimal point location in a monotone subdivision, SIAM Journal on Computing, 1986, 15 (2): 317–340, doi:10.1137/0215023 .

一月 14, 2024
折線, 又稱多邊形鏈, polygonal, chain, 或多段線, polyline, 是指一系列相連的線段, 通常是一些任意不同方向的直線段首尾相連結所形成的線, 與多邊形不同, 並不要求線的整體要頭尾封閉, 更正式地說, 是由一系列稱為其頂點的點, displaystyle, dots, 所決定的曲線, 該曲線連續地由線段連接這些頂點所構成, 簡單自相交封閉, 目录, 變體, 簡單, 封閉, 單調, 參數化, 與點集的關聯, 應用, 參見, 註釋, 參考文獻變體, 编辑簡單, 编辑, 簡單是指該的線段連續相. 折線又稱多邊形鏈 polygonal chain 註 1 或多段線 polyline 5 是指一系列相連的線段 通常是一些任意不同方向的直線段首尾相連結所形成的線 7 與多邊形不同 折線並不要求線的整體要頭尾封閉 更正式地說 折線P 是由一系列稱為其頂點的點 A 1 A 2 A n displaystyle A 1 A 2 dots A n 所決定的曲線 該曲線連續地由線段連接這些頂點所構成 簡單折線自相交折線封閉折線 目录 1 變體 1 1 簡單折線 1 2 封閉折線 1 3 單調折線 2 參數化 3 與點集的關聯 4 應用 5 參見 6 註釋 7 參考文獻變體 编辑簡單折線 编辑 簡單折線是指該折線的線段連續相交 且僅有在線段的端點相交 沒有在別處有相交 即非自相交的折線 封閉折線 编辑 封閉折線是指第一個頂點與最後一個頂點重合 或者第一個頂點與最後一個頂點也相連的折線 8 平面的簡單封閉折線是簡單多邊形的邊界 通常 多邊形 這個術語就是指 封閉折線 但在某些情況下還是會將封閉折線和多邊形兩個概念區分開來 單調折線 编辑 如果存在一條直線L 且垂直於L的每條直線最多與該折線相交一次 則稱該折線是一個單調折線 每個非平凡的單調多邊形鏈都是非封閉的 開放的 相較之下 每個單調多邊形 封閉折線 都恰好可以分割成兩個單調折線 9 分段線性函數的圖形相對於水平線形成單調折線 一般的折線圖也都是相對於某座標軸的單調折線 參數化 编辑 nbsp 在一個點的數量n 17 之點集中 有一條由四個線段組成的同正負斜率之折線折線的每個線段通常使用連續頂點間的線性插值來線性參數化 在實際應用中 對於整條折線而言有兩種常見的參數化方式 一種是 折線之線段鏈的每一段都可以被分配與第一個頂點對應索引的參數之單位區間 另一種是 折線之線段鏈的每一段都可以被分配一個與該段的長度相對應的參數區間 使得該參數沿著整個折線之線段鏈統一對應於其曲線長 與點集的關聯 编辑每個至少有n 個點的點集都包含一條至少有 n 1 displaystyle lfloor sqrt n 1 rfloor nbsp 條邊的斜率正負相同之折線路徑 這是埃爾多斯 塞克雷斯定理 英语 Erdos Szekeres theorem 的推論 應用 编辑折線通常可以用來近似更複雜的曲線 在這種情況下 道格拉斯 普克演算法可以用於尋找具有最少線段但又足夠接近原始曲線的折線 作為該曲線精確的近似 10 11 在圖繪製 英语 graph drawing 中 折線常用於表示圖的邊 在繪圖樣式中 將邊繪製為直線段可能會導致交叉 邊與頂點碰撞或其他不希望出現的特徵 在這種情況下 通常希望用盡可能少的線段和彎曲來繪製圖的邊 以減少繪圖中的視覺混亂 最小化彎曲次數的問題稱為彎曲最小化問題 英语 Bend minimization 12 折線也是计算几何的一種基本資料類型 例如 李德財和普雷帕拉塔 英语 Franco P Preparata 的點定位演算法就是透過將任意曲面細分分解為單調折線的有序序列來進行操作 以達到可以透過二分搜尋來解決點位置查詢問題的目標 此方法後來經過改進 使得點定位問題的時間複雜度得到最佳化 13 參見 编辑鏈 代數拓撲 單純形的形式組合 在一維情況下包括折線 多邊形鏈 貝茲樣條 連結距離 分段回归 道路 图论 螺旋折線 英语 Spirangle 导线测量 折線圖註釋 编辑 多邊形鏈 polygonal chain 有時也稱為多邊曲線 polygonal curve 1 多邊路徑 polygonal path 2 折線 polyline 3 broken line 4 5 分段線性曲線 piecewise linear curve 3 或者在地理信息系统中稱為線串 linestring 或線性環 linear ring 6 參考文獻 编辑 Gomes Jonas Velho Luiz Costa Sousa Mario Computer Graphics Theory and Practice CRC Press 186 2012 ISBN 9781568815800 Cheney Ward Analysis for Applied Mathematics Graduate Texts in Mathematics 208 Springer 13 2001 ISBN 9780387952796 3 0 3 1 Boissonnat Jean Daniel Teillaud Monique Effective Computational Geometry for Curves and Surfaces Springer 34 2006 ISBN 9783540332596 Muggeo Vito M R segmented An R package to fit regression models with broken line relationships PDF R News May 2008 8 1 20 25 5 0 5 1 折線 polyline 雙語詞彙 學術名詞暨辭書資訊網 國家教育研究院 2023 12 03 原始内容存档于2023 12 03 Open Geospatial Consortium Herring John R 编 OpenGIS Implementation Standard for Geographic information Simple feature access Part 1 Common architecture 1 2 1 Open Geospatial Consortium 2011 05 28 2016 01 15 原始内容存档于2017 01 29 折線 教育部重編國語辭典 2023 11 17 原始内容存档于2023 11 17 Mehlhorn Kurt Naher Stefan LEDA A Platform for Combinatorial and Geometric Computing Cambridge University Press 758 1999 ISBN 9780521563291 O Rourke Joseph Computational Geometry in C Cambridge Tracts in Theoretical Computer Science Cambridge University Press 45 1998 ISBN 9780521649766 Ramer Urs An iterative procedure for the polygonal approximation of plane curves Computer Graphics and Image Processing 1972 1 3 244 256 doi 10 1016 S0146 664X 72 80017 0 Douglas David Peucker Thomas Algorithms for the reduction of the number of points required to represent a digitized line or its caricature The Canadian Cartographer 1973 10 2 112 122 doi 10 3138 FM57 6770 U75U 7727 Tamassia Roberto On embedding a graph in the grid with the minimum number of bends SIAM Journal on Computing 1987 16 3 421 444 doi 10 1137 0216030 Edelsbrunner Herbert Guibas Leonidas J Stolfi Jorge Optimal point location in a monotone subdivision SIAM Journal on Computing 1986 15 2 317 340 doi 10 1137 0215023 取自 https zh wikipedia org w index php title 折線 amp oldid 80437626, 维基百科，wiki，书籍，书籍，图书馆，

文章

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