รูปหลายเหลี่ยมทางเดียว

รูปหลายเหลี่ยมทางเดียว (อังกฤษ: monotone polygon) คือรูปหลายเหลี่ยม P บนระนาบ ซึ่งเมื่อกำหนดเส้นตรง L ขึ้นมาเส้นหนึ่ง เส้นตรงทุกเส้นที่ตั้งฉากกับ L จะลากตัดผ่านเส้นขอบของรูปหลายเหลี่ยม P อย่างมากที่สุดเพียงสองครั้ง สำหรับจุดประสงค์ในทางปฏิบัติหลายอย่าง นิยามนี้อาจขยายออกไป ให้สามารถยอมรับกรณีที่เส้นขอบของ P บางเส้นตั้งฉากกับ L

สมบัติ

 

เส้นสีเขียวแสดงส่วนที่ตัดหนึ่งครั้ง เส้นสีน้ำเงินตัดสองครั้ง เส้นสีแดงตัดสามครั้งหรือมากกว่า เฉพาะสองรูปบนจึงเป็นรูปหลายเหลี่ยมทางเดียว ในขณะที่อีกสองรูปล่างไม่ใช่

สมมติให้เส้นตรง L ทับกันสนิทกับแกน x จุดยอดที่อยู่ทางซ้ายสุดหรือขวาสุดของรูปหลายเหลี่ยมทางเดียว จะสามารถแบ่งเส้นขอบของรูปออกเป็นสายโซ่หลายเหลี่ยม (polygonal chain) สองรูป ซึ่งจุดยอดบนลูกโซ่หลายเหลี่ยมจะเรียงตัวในลำดับธรรมชาติ นั่นคือพิกัด x ของจุดยอดจะมีค่าเพิ่มหรือลดไปในทางเดียว ไม่เพิ่มลดสลับไปมา สมบัตินี้จึงอาจใช้เป็นนิยามของรูปหลายเหลี่ยมทางเดียวก็ได้

รูปหลายเหลี่ยมนูนทุกรูปเป็นรูปหลายเหลี่ยมทางเดียว ซึ่งสามารถพิสูจน์ได้จากเส้นตรงใดๆ ที่ตัดผ่าน

การค้นหาจุดตัดของเส้นตรงกับรูปหลายเหลี่ยมทางเดียว เพื่อที่จะหาว่าจุดยอดใดอยู่ทางซ้ายสุดหรือขวาสุด อาจต้องใช้เวลาคำนวณเป็นเวลาลอการิทึม หลังจากประมวลผลก่อนเป็นเวลาเชิงเส้นไปแล้ว รูปหลายเหลี่ยมทางเดียวอาจแบ่งออกเป็นรูปสามเหลี่ยมได้โดยง่ายในเวลาเชิงเส้น

อ้างอิง

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.
2. 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