查看“︁折線”︁的源代码

[[Image:Chainline.svg|thumb|right|簡單折線]]
[[Image:Self crossed polygonal chain.svg|thumb|right|自相交折線]]
[[Image:Closed polygonal line.svg|thumb|right|封閉折線]]
'''折線'''又稱'''多邊形鏈'''（{{lang|en|polygonal chain}}）{{#tag:ref|多邊形鏈（polygonal chain）有時也稱為'''多邊曲線'''（polygonal curve<ref>{{citation
 |title=Computer Graphics: Theory and Practice
 |first1=Jonas |last1=Gomes
 |first2=Luiz |last2=Velho
 |first3=Mario |last3=Costa Sousa
 |publisher=CRC Press
 |year=2012
 |isbn=9781568815800
 |page=186
 |url=https://books.google.com/books?id=ID1tP9DfKgEC&pg=PA186
 }}.</ref>）、'''多邊路徑'''（polygonal path<ref>{{citation|title=Analysis for Applied Mathematics|volume=208|series=Graduate Texts in Mathematics|first=Ward|last=Cheney|publisher=Springer|year=2001|isbn=9780387952796|page=13|url=https://books.google.com/books?id=EHjTHmupFgMC&pg=PA13}}.</ref>）、'''折線'''（polyline<ref name="ecg">{{citation|title=Effective Computational Geometry for Curves and Surfaces|first1=Jean-Daniel|last1=Boissonnat|first2=Monique|last2=Teillaud|author2-link=Monique Teillaud|publisher=Springer|year=2006|isbn=9783540332596|page=34|url=https://books.google.com/books?id=XQpEAAAAQBAJ&pg=PA34}}.</ref>、broken line<ref>{{citation|last=Muggeo|first=Vito M. R.|date=May 2008|issue=1|journal=R News|pages=20–25|title=segmented: An R package to fit regression models with broken-line relationships|url=ftp://journal.r-project.org/pub/R/doc/Rnews/Rnews_2008-1-1.pdf#page=20|volume=8}}</ref><ref name="polyline terms.naer.edu.tw"/>）、'''分段線性曲線'''（piecewise linear curve<ref name="ecg"/>），或者在[[地理信息系统]]中稱為'''線串'''（linestring）或'''線性環'''（linear ring）<ref name="OGC">{{Citation |author=[[Open Geospatial Consortium]] |date=2011-05-28 |version=1.2.1 |editor-last=Herring |editor-first=John R. |title=OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture |publisher=Open Geospatial Consortium |url=http://www.opengeospatial.org/standards/sfa |access-date=2016-01-15 |archive-date=2017-01-29 |archive-url=https://web.archive.org/web/20170129153045/http://www.opengeospatial.org/standards/sfa |dead-url=no }}</ref>|group=註|name=Names}}或'''多段線'''（polyline）<ref name="polyline terms.naer.edu.tw">{{Cite web |title=折線 polyline |url=https://terms.naer.edu.tw/detail/14dcb3c56a9d089568731580acb1079f/?startswith=zh&seq=1 |website=雙語詞彙、學術名詞暨辭書資訊網 |publisher=[[國家教育研究院]] |accessdate=2023-12-03 | archive-date =2023-12-03 | archive-url =https://archive.today/20231203113029/https://terms.naer.edu.tw/detail/14dcb3c56a9d089568731580acb1079f/?startswith=zh&seq=1 | dead-url =no }}</ref>是指一系列相連的[[線段]]，通常是一些任意不同方向的[[線段|直線段]]首尾相連結所形成的線<ref>{{Cite web | url =https://dict.revised.moe.edu.tw/dictView.jsp?ID=114895&word=%E6%8A%98%E7%B7%9A | title =折線 | publisher =教育部重編國語辭典 | access-date =2023-11-17 | archive-date =2023-11-17 | archive-url =https://web.archive.org/web/20231117075523/https://dict.revised.moe.edu.tw/dictView.jsp?ID=114895&word=%E6%8A%98%E7%B7%9A | dead-url =no }}</ref>。
與[[多邊形]]不同，折線並不要求線的整體要頭尾封閉。
更正式地說，折線{{math|''P''}}是由一系列稱為其[[頂點 (幾何)|頂點]]的點<math>(A_1, A_2, \dots, A_n)</math>所決定的[[曲線]]，該曲線連續地由線段連接這些頂點所構成。

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

=== 封閉折線 ===
封閉折線是指第一個[[頂點 (幾何)|頂點]]與最後一個頂點重合，或者第一個頂點與最後一個頂點也相連的折線。<ref>{{citation|title=LEDA: A Platform for Combinatorial and Geometric Computing|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Stefan|last2=Näher|publisher=Cambridge University Press|year=1999|isbn=9780521563291|page=758|url=https://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA758}}.</ref>
平面的簡單封閉折線是簡單多邊形的邊界。
通常，「[[多邊形]]」這個術語就是指「封閉折線」，但在某些情況下還是會將封閉折線和多邊形兩個概念區分開來。

=== 單調折線 ===
如果存在一條直線L，且垂直於L的每條直線最多與該折線相交一次，則稱該折線是一個單調折線。每個非平凡的單調多邊形鏈都是非封閉的（開放的）。
相較之下，每個單調多邊形（封閉折線）都恰好可以分割成兩個單調折線。<ref>{{citation|title=Computational Geometry in C|series=Cambridge Tracts in Theoretical Computer Science|first=Joseph|last=O'Rourke|author-link=Joseph O'Rourke (professor)|publisher=Cambridge University Press|year=1998|isbn=9780521649766|page=45|url=https://books.google.com/books?id=gsv7HALW2jYC&pg=PA45}}.</ref>
分段線性函數的圖形相對於水平線形成單調折線。
一般的[[折線圖]]也都是相對於某座標軸的單調折線。

== 參數化 ==
[[Image:Monotone-subseq-17-5.svg|thumb|160px|在一個點的數量{{math|1=''n''=17}}之點集中，有一條由四個線段組成的同正負斜率之折線]]
折線的每個線段通常使用連續頂點間的線性插值來線性參數化。
在實際應用中，對於整條折線而言有兩種常見的參數化方式。
一種是：折線之線段鏈的每一段都可以被分配與第一個頂點對應索引的參數之單位區間；
另一種是：折線之線段鏈的每一段都可以被分配一個與該段的長度相對應的參數區間，使得該參數沿著整個折線之線段鏈統一對應於其曲線長。

== 與點集的關聯 ==
每個至少有{{math|''n''}}個點的點集都包含一條至少有<math>\lfloor\sqrt{n-1}\rfloor</math>條邊的斜率正負相同之折線路徑。
這是{{link-en|埃爾多斯-塞克雷斯定理|Erdős–Szekeres_theorem}}的推論。

== 應用 ==
折線通常可以用來近似更複雜的曲線。
在這種情況下，[[道格拉斯-普克算法|道格拉斯-普克演算法]]可以用於尋找具有最少線段但又足夠接近原始曲線的折線，作為該曲線精確的近似。<ref>{{citation|first=Urs|last=Ramer|title=An iterative procedure for the polygonal approximation of plane curves|journal=Computer Graphics and Image Processing|volume=1|issue=3|pages= 244–256 |year=1972|doi=10.1016/S0146-664X(72)80017-0}}.</ref><ref>{{citation|first1=David|last1=Douglas|first2=Thomas|last2=Peucker|title=Algorithms for the reduction of the number of points required to represent a digitized line or its caricature|journal=The Canadian Cartographer|volume=10|issue=2|pages=112–122|year=1973|doi=10.3138/FM57-6770-U75U-7727}}.</ref>

在{{link-en|圖繪製|graph drawing}}中，折線常用於表示[[圖 (數學)|圖]]的[[邊 (圖論)|邊]]，在繪圖樣式中，將邊繪製為直線段可能會導致交叉、邊與頂點碰撞或其他不希望出現的特徵。
在這種情況下，通常希望用盡可能少的線段和彎曲來繪製[[圖 (數學)|圖]]的[[邊 (圖論)|邊]]，以減少繪圖中的視覺混亂；
最小化彎曲次數的問題稱為{{link-en|彎曲最小化問題|Bend minimization}}。<ref>{{citation
 | last = Tamassia | first = Roberto | author-link = Roberto Tamassia
 | doi = 10.1137/0216030
 | issue = 3
 | journal = SIAM Journal on Computing
 | pages = 421–444
 | title = On embedding a graph in the grid with the minimum number of bends
 | volume = 16
 | year = 1987}}.</ref>

折線也是[[计算几何]]的一種基本資料類型。
例如，[[李德財]]和{{link-en|佛朗哥·P·普雷帕拉塔|Franco_P._Preparata|普雷帕拉塔}}的點定位演算法就是透過將任意曲面細分分解為單調折線的有序序列來進行操作，以達到可以透過二分搜尋來解決點位置查詢問題的目標；
此方法後來經過改進，使得點定位問題的時間複雜度得到最佳化。<ref>{{citation
 | author1-link = Herbert Edelsbrunner|first1=Herbert|last1=Edelsbrunner|author2-link=Leonidas J. Guibas|first2=Leonidas J.|last2=Guibas|author3-link=Jorge Stolfi|first3=Jorge|last3=Stolfi
 | title = Optimal point location in a monotone subdivision
 | journal = [[SIAM Journal on Computing]]
 | volume = 15
 | issue = 2
 | date = 1986
 | pages = 317–340
 | doi = 10.1137/0215023}}.</ref>

== 參見 ==
*[[鏈 (代數拓撲)]]：單純形的形式組合，在一維情況下包括折線（多邊形鏈）
*[[貝茲樣條]]
*[[連結距離]]
*[[分段回归]]
*[[道路 (图论)]]
*{{link-en|螺旋折線|Spirangle}}
*[[导线测量]]
*[[折線圖]]

== 註釋 ==
{{Reflist|group=註}}

== 參考文獻 ==
{{Reflist|2}}

{{Authority control}}

[[Category:多邊形]]