![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Star-kernel.svg/langzh-hant-640px-Star-kernel.svg.png&w=640&q=50)
星狀多邊形
維基百科,自由的 encyclopedia
星狀多邊形(star-shaped polygon)是平面上屬於星形域的多邊形區域,即這個多邊形內部存在「可以看到整個多邊形邊界與整個多邊形內部所有區域[1]」的點。[2]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Star-kernel.svg/320px-Star-kernel.svg.png)
形式上,若多邊形P中存在一點z使得對於P中的每一點p與z連成的線段完全位於P內,則稱P為星狀多邊形。[3]所有的z(能夠看到整個多邊形邊界的點)形成的集合稱為星狀多邊形P的核(下稱「星狀核」)。
如果星狀多邊形是凸多邊形,則任意兩個點間的連結距離(能夠保持在內部連接內部兩點的任意折線的最小線段數)為1。 如果星狀多邊形不是凸多邊形,則這個星狀多邊形的核中的任兩點連結距離為1;如果星狀多邊形內兩點中有一點不在星狀核內,則這兩點的連結距離也為1,而如果星狀多邊形內兩點都在星狀核外,則這兩點的連結距離可能為1或2;因此對於任意星狀多邊形,最大的連結距離為2[4][5]。
例子
凸多邊形都屬於星狀多邊形,且其星狀核為自己本身。[註 1]
星形正多邊形的簡單化多邊形[註 2]都是星狀多邊形,其幾何中心總是位於星狀核內。
反平行四邊形和勒穆瓦訥六邊形(英語:Lemoine hexagon)也屬於星狀多邊形,其星狀核為一個點。[註 3]
可見性多邊形(英語:Visibility_polygon)也屬於星狀多邊形,因為根據其定義,其每個點都必須從中心可見。[7]
演算法
分辨一個多邊形是否為星狀多邊形並且找到星狀核中一點可以被制定為一個低維線性規劃問題,其可以在線性時間內完成星狀多邊形的判斷。[8]:16
多邊形的每條邊定義了一個有包含多邊形內部區域(對星狀多邊形而言可能是全部或局部)的半平面,該半平面的邊界位於包含該邊的直線上,且包含多邊形在該邊上任意鄰近點的點。 星狀多邊形的星狀核是其所有內部區域半平面的交集。而使用分治法可以在Θ(N log N)時間內找到任意一組N個半平面的交集。[3] 不過,如果僅只是要尋找星狀多邊形的星狀核的話,存在比上述更快的方法。 例如,李德財和佛朗哥·P·普雷帕拉塔(英語:Franco P. Preparata)在1979年提出了一種可以在線性時間內找到星狀多邊形的星狀核之演算法。[9]
相關概念
星狀多面體
星狀多面體(star-shaped polyhedron)是星狀多邊形在三維空間的推廣。 指一個多面體中至少包含一個點能從該點看到多面體所有區域和邊界以及多面體內部的其他所有點。[1][10]
能夠看到整個星狀多面體的區域同樣稱為該星狀多面體的核,也就是其星狀核。[10]
參見
- 單調多邊形(英語:Monotone polygon)
註釋
參考文獻
- 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).
- Ke, Yan, Polygon visibility algorithms for weak visibility and link distance problems, The Johns Hopkins University, 1990 [2023-11-26], (原始內容存檔於2023-11-26)
- Franco P. Preparata and Michael Ian Shamos. Computational Geometry – An Introduction. Springer-Verlag. 1985. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988.
- 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).
- 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.
- Branko Grunbaum and Geoffrey C. Shephard. Regular Polygons (PDF). Mathematics Magazine. 1977, 50: 227–247,51 [2023-11-27]. (原始內容存檔 (PDF)於2023-11-04).
- Arkin, E.; Mitchell, Joseph. An optimal visibility algorithm for a simple polygon with star-shaped holes (技術報告). Cornell University Operations Research and Industrial Engineering. 1987. 746.
- J. Matoušek; M. Sharir; E. Welzl. A Subexponential Bound for Linear Programming (PDF). Algorithmica. 1996, 16: 498-516 [2023-11-16]. (原始內容存檔 (PDF)於2023-04-23).
- Lee, D. T.; Preparata, F. P., An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM, July 1979, 26 (3): 415–421, S2CID 6156190, doi:10.1145/322139.322142, hdl:2142/74090
, (原始內容存檔於September 24, 2017)
- Gao, Mingcen and Cao, Thanh-Tung and Tan, Tiow-Seng and Huang, Zhiyong. Flip-flop: convex hull construction via star-shaped polyhedron in 3D. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 2013: 45–54 [2023-11-27]. (原始內容存檔於2023-12-03).