รูปหลายเหลี่ยมทางเดียว
รูปหลายเหลี่ยมทางเดียว (อังกฤษ: monotone polygon) คือรูปหลายเหลี่ยม P บนระนาบ ซึ่งเมื่อกำหนดเส้นตรง L ขึ้นมาเส้นหนึ่ง เส้นตรงทุกเส้นที่ตั้งฉากกับ L จะลากตัดผ่านเส้นขอบของรูปหลายเหลี่ยม P อย่างมากที่สุดเพียงสองครั้ง [1] สำหรับจุดประสงค์ในทางปฏิบัติหลายอย่าง นิยามนี้อาจขยายออกไป ให้สามารถยอมรับกรณีที่เส้นขอบของ P บางเส้นตั้งฉากกับ L
สมบัติ แก้
สมมติให้เส้นตรง L ทับกันสนิทกับแกน x จุดยอดที่อยู่ทางซ้ายสุดหรือขวาสุดของรูปหลายเหลี่ยมทางเดียว จะสามารถแบ่งเส้นขอบของรูปออกเป็นสายโซ่หลายเหลี่ยม (polygonal chain) สองรูป ซึ่งจุดยอดบนลูกโซ่หลายเหลี่ยมจะเรียงตัวในลำดับธรรมชาติ นั่นคือพิกัด x ของจุดยอดจะมีค่าเพิ่มหรือลดไปในทางเดียว ไม่เพิ่มลดสลับไปมา สมบัตินี้จึงอาจใช้เป็นนิยามของรูปหลายเหลี่ยมทางเดียวก็ได้
รูปหลายเหลี่ยมนูนทุกรูปเป็นรูปหลายเหลี่ยมทางเดียว ซึ่งสามารถพิสูจน์ได้จากเส้นตรงใดๆ ที่ตัดผ่าน
การค้นหาจุดตัดของเส้นตรงกับรูปหลายเหลี่ยมทางเดียว เพื่อที่จะหาว่าจุดยอดใดอยู่ทางซ้ายสุดหรือขวาสุด อาจต้องใช้เวลาคำนวณเป็นเวลาลอการิทึม หลังจากประมวลผลก่อนเป็นเวลาเชิงเส้นไปแล้ว [1] รูปหลายเหลี่ยมทางเดียวอาจแบ่งออกเป็นรูปสามเหลี่ยมได้โดยง่ายในเวลาเชิงเส้น [2]
อ้างอิง แก้
- ↑ 1.0 1.1 Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
- ↑ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301
 | บทความเรขาคณิตนี้ยังเป็นโครง คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล |