เรขาคณิตเชิงคำนวณใน Python: จากทฤษฎีสู่แอปพลิเคชัน

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

1. ว้าว ฟังดูซับซ้อน
2. อ๋อ ตัวเรือนูน

ในโพสต์นี้ ฉันต้องการให้ความกระจ่างเกี่ยวกับเรขาคณิตเชิงคำนวณ โดยเริ่มจากภาพรวมคร่าวๆ ของตัวแบบก่อนที่จะเข้าสู่คำแนะนำเชิงปฏิบัติโดยอิงจากประสบการณ์ของฉันเอง (ข้ามไปข้างหน้าหากคุณมีการจัดการที่ดีในหัวข้อนี้)

เอะอะทั้งหมดเกี่ยวกับอะไร?

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

น่าสนใจตามทฤษฎี…

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

ตัวอย่างเช่น พิจารณาปัญหา Art Gallery: เราเป็นเจ้าของอาร์ตแกลเลอรี่และต้องการติดตั้งกล้องวงจรปิดเพื่อปกป้องงานศิลปะของเรา แต่เราอยู่ภายใต้งบประมาณที่จำกัด ดังนั้นเราจึงต้องการใช้กล้องให้น้อยที่สุด เราต้องการกล้องกี่ตัว?

เมื่อเราแปลสิ่งนี้เป็นสัญกรณ์เรขาคณิตเชิงคำนวณ 'แผนผังชั้น' ของแกลเลอรีเป็นเพียงรูปหลายเหลี่ยมธรรมดา และด้วยจาระบีที่ข้อศอก เราสามารถพิสูจน์ได้ว่ากล้อง n/3 ตัวนั้นเพียงพอสำหรับรูปหลายเหลี่ยมบน n จุดยอดเสมอ ไม่ว่ามันจะเลอะเทอะแค่ไหนก็ตาม ตัวพิสูจน์ใช้กราฟคู่ ทฤษฎีกราฟ สามเหลี่ยม และอื่นๆ

ในที่นี้ เราเห็นเทคนิคการพิสูจน์ที่ชาญฉลาดและผลลัพธ์ที่น่าสงสัยมากจนเป็นที่ชื่นชมในตัวเอง แต่ถ้าความเกี่ยวข้องทางทฤษฎีไม่เพียงพอสำหรับคุณ...

และที่สำคัญในทางปฏิบัติ

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

ทำไมมันยากจัง?

ลองใช้ปัญหาเรขาคณิตเชิงคำนวณที่ค่อนข้างตรงไปตรงมา: เมื่อพิจารณาจุดและรูปหลายเหลี่ยมแล้ว จุดจะอยู่ภายในรูปหลายเหลี่ยมหรือไม่ (สิ่งนี้เรียกว่าปัญหา point-in-polygon หรือ PIP)

PIP แสดงให้เห็นได้อย่างยอดเยี่ยมว่าเหตุใดเรขาคณิตเชิงคำนวณจึงสามารถ (หลอกลวง) ได้ยาก สำหรับสายตามนุษย์ นี่ไม่ใช่คำถามที่ยาก เราเห็นไดอะแกรมต่อไปนี้ และเห็น ได้ ชัดว่าจุดนั้นอยู่ในรูปหลายเหลี่ยม:

แม้แต่สำหรับรูปหลายเหลี่ยมที่ค่อนข้างซับซ้อน คำตอบก็ไม่ได้หนีเรานานกว่าหนึ่งหรือสองวินาที แต่เมื่อเราป้อนปัญหานี้ไปยังคอมพิวเตอร์ อาจเห็นสิ่งต่อไปนี้:

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

สิ่งที่ใช้สัญชาตญาณสำหรับสมองของมนุษย์ไม่ได้แปลเป็นภาษาคอมพิวเตอร์อย่างง่ายดาย

ในทางนามธรรมมากขึ้น (และไม่สนใจความจำเป็นในการแสดงสิ่งเหล่านี้ในโค้ด) ปัญหาที่เราเห็นในระเบียบวินัยนี้ยากมากที่จะเข้มงวด ('ทำให้เข้มงวด') ในอัลกอริธึมการคำนวณทางเรขาคณิต เราจะอธิบายสถานการณ์ point-in-polygon โดยไม่ใช้ภาษาซ้ำซากเช่น 'จุดอยู่ภายในรูปหลายเหลี่ยมหากอยู่ภายในรูปหลายเหลี่ยม' ได้อย่างไร คุณสมบัติเหล่านี้หลายอย่างเป็นพื้นฐานและเป็นพื้นฐานจนยากที่จะกำหนดอย่างเป็นรูปธรรม

ยากแต่ไม่ใช่เป็นไปไม่ได้ ตัวอย่างเช่น คุณอาจปรับ point-in-polygon ให้เข้มงวดด้วยคำจำกัดความต่อไปนี้:

• จุดอยู่ภายในรูปหลายเหลี่ยมถ้า รังสีอนันต์ที่เริ่มต้นที่จุดตัดกับขอบรูปหลายเหลี่ยมจำนวนคี่ (เรียกว่ากฎคู่คี่)
• จุดอยู่ภายในรูปหลายเหลี่ยมหาก มีจำนวนคดเคี้ยวที่ไม่ใช่ศูนย์ (กำหนดเป็นจำนวนครั้งที่เส้นโค้งที่กำหนดรูปหลายเหลี่ยมเคลื่อนที่รอบจุด)

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

แนะนำ CCW

ตอนนี้เราเข้าใจถึงความสำคัญและความยากของปัญหาเรขาคณิตเชิงคำนวณแล้ว ถึงเวลาที่จะทำให้มือของเราเปียก

ที่กระดูกสันหลังของตัวแบบคือการดำเนินการดึกดำบรรพ์ที่ทรงพลังอย่างหลอกลวง: ทวนเข็มนาฬิกา หรือเรียกสั้นๆ ว่า 'CCW' (ฉันจะเตือนคุณตอนนี้: CCW จะปรากฏขึ้นอีกครั้งและอีกครั้ง)

CCW รับสามจุด A, B และ C เป็นอาร์กิวเมนต์และถามว่า: สามจุดเหล่านี้ประกอบเป็นการหมุนทวนเข็มนาฬิกา (เทียบกับการหมุนตามเข็มนาฬิกา) หรือไม่? กล่าวอีกนัยหนึ่งคือ A -> B -> C เป็นมุมทวนเข็มนาฬิกาหรือไม่

ตัวอย่างเช่น จุด สีเขียว คือ CCW ในขณะที่จุด สีแดง ไม่ใช่:

ทำไม CCW ถึงมีความสำคัญ

CCW ให้การดำเนินการ ดั้งเดิม แก่เราซึ่งเราสามารถสร้างขึ้นได้ มันทำให้เรามีที่ที่จะเริ่มปรับแก้และแก้ปัญหาเรขาคณิตเชิงคำนวณ

เพื่อให้คุณเข้าใจถึงพลังของมัน ลองพิจารณาสองตัวอย่าง

การกำหนดนูน

อย่างแรก: จากรูปหลายเหลี่ยม คุณสามารถระบุได้ไหมว่าเป็นรูปหลายเหลี่ยมนูนหรือไม่ ความนูนเป็นคุณสมบัติล้ำค่า: การรู้ว่ารูปหลายเหลี่ยมของคุณนูนมักจะช่วยให้คุณปรับปรุงประสิทธิภาพตามลำดับความสำคัญได้ จากตัวอย่างที่เป็นรูปธรรม: มีอัลกอริธึม PIP ที่ค่อนข้างตรงไปตรงมาซึ่งทำงานในเวลาบันทึก (n) สำหรับรูปหลายเหลี่ยมนูน แต่ล้มเหลวสำหรับรูปหลายเหลี่ยมเว้าจำนวนมาก

ตามสัญชาตญาณ ช่องว่างนี้เหมาะสม: รูปร่างนูนนั้น 'ดี' ในขณะที่รูปร่างเว้าสามารถมีขอบคมที่ยื่นเข้าและออกได้—แต่ไม่ทำตามกฎเดียวกัน

อัลกอริธึมเชิงเรขาคณิตเชิงคำนวณที่เรียบง่าย (แต่ไม่ชัดเจน) สำหรับกำหนดความนูนคือการตรวจสอบว่าจุดยอดสามจุดต่อเนื่องกันทุกจุดเป็น CCW ใช้โค้ดเรขาคณิตของ Python เพียงไม่กี่บรรทัด (สมมติว่ามีการจัด points ในลำดับทวนเข็มนาฬิกา—หาก points อยู่ในลำดับตามเข็มนาฬิกา คุณจะต้องให้ triplets ทั้งหมดเป็นตามเข็มนาฬิกา):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

ลองทำสิ่งนี้บนกระดาษพร้อมตัวอย่างบางส่วน คุณสามารถใช้ผลลัพธ์นี้เพื่อ กำหนด ความนูนได้ (เพื่อให้เข้าใจง่ายขึ้น โปรดทราบว่าเส้นโค้ง CCW จาก A -> B -> C จะสัมพันธ์กับมุมที่น้อยกว่า 180 ซึ่งเป็นวิธีที่สอนกันอย่างแพร่หลายในการกำหนดความนูน)

แยกเส้น

ตัวอย่างที่สอง ให้พิจารณาจุดตัดของส่วนของเส้นตรง ซึ่งสามารถแก้ไขได้โดยใช้ CCW เพียงอย่างเดียว:

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

ทำไมถึงเป็นเช่นนี้? จุดตัดของส่วนของเส้นตรงยังสามารถใช้วลีดังนี้: เมื่อให้ส่วนที่มีจุดปลาย A และ B จุดปลาย C และ D ของส่วนอื่นอยู่ด้านเดียวกันของ AB หรือไม่ กล่าวอีกนัยหนึ่ง หากทางเลี้ยวจาก A -> B -> C และ A -> B -> D ไปในทิศทางเดียวกัน ส่วนนั้นจะไม่สามารถตัดกัน เมื่อเราใช้ภาษาประเภทนี้จะเห็นได้ชัดว่าปัญหาดังกล่าวอยู่ที่ขนมปังและเนยของ CCW

คำจำกัดความที่เข้มงวด

ตอนนี้เราได้ทราบถึงความสำคัญของ CCW แล้ว เรามาดูกันว่าคำนวณอย่างไร ให้คะแนน A, B และ C:

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

เพื่อให้เข้าใจว่าคำจำกัดความนี้มาจากไหน ให้พิจารณาเวกเตอร์ AB และ BC ถ้าเราหาผลคูณไขว้ของมัน AB x BC นี่จะเป็นเวกเตอร์ตามแนวแกน z แต่ในทิศทางใด (เช่น +z หรือ -z)? ผลปรากฏว่า ถ้าผลคูณเป็นบวก การหมุนทวนเข็มนาฬิกา มิฉะนั้นจะเป็นตามเข็มนาฬิกา

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

ดำน้ำของฉันสู่เรขาคณิตเชิงคำนวณและการเขียนโปรแกรมโดยใช้ Python

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

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

อัลกอริทึมของ Kirkpatrick

แก่นแท้ของงานของฉันคือการนำอัลกอริทึมของ Kirkpatrick ไปใช้เพื่อกำหนดตำแหน่งจุด ข้อความแจ้งปัญหาจะมีลักษณะดังนี้: เมื่อพิจารณาจากการแบ่งส่วนระนาบ (กลุ่มของรูปหลายเหลี่ยมที่ไม่ทับซ้อนกันในระนาบ) และจุด P ซึ่งรูปหลายเหลี่ยมใดมี P ลองนึกถึงรูปหลายเหลี่ยมแบบ point-in-polygon บนสเตียรอยด์—แทนที่จะเป็นรูปหลายเหลี่ยมเพียงรูปเดียว คุณมีระนาบที่เต็มไปด้วยพวกมัน

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

แม้ว่าฉันจะไม่พูดถึงอัลกอริทึมในเชิงลึก แต่คุณสามารถเรียนรู้เพิ่มเติมได้ที่นี่

ขั้นต่ำ Bounding Triangle

ในงานย่อย ฉันยังใช้อัลกอริธึมของ O'Rourke เพื่อคำนวณสามเหลี่ยมล้อมรอบ/ขอบเขตขั้นต่ำ (นั่นคือ การหาสามเหลี่ยมที่เล็กที่สุดที่ล้อมรอบชุดจุดนูน) ในเวลาเชิงเส้น

หมายเหตุ: การคำนวณสามเหลี่ยมขอบเขตต่ำสุดไม่ได้ช่วยหรือทำร้ายประสิทธิภาพเชิงซีมโทติกของอัลกอริทึมของ Kirkpatrick เนื่องจากการคำนวณนั้นเป็นแบบเวลาเชิงเส้น—แต่มีประโยชน์สำหรับวัตถุประสงค์ด้านสุนทรียศาสตร์

คำแนะนำในทางปฏิบัติ การใช้งาน และข้อกังวล

ส่วนก่อนหน้านี้เน้นว่าเหตุใดเรขาคณิตเชิงคำนวณจึงยากที่จะให้เหตุผลอย่างจริงจัง

ในทางปฏิบัติ เราต้องจัดการกับข้อกังวลใหม่ๆ ทั้งหมด

จำ CCW? เพื่อเป็นการต่อเนื่องที่ดี เรามาดูคุณสมบัติที่ยอดเยี่ยมอีกประการหนึ่งของมันกัน: มันปกป้องเราจากอันตรายของข้อผิดพลาดทศนิยม

ข้อผิดพลาดทศนิยม: ทำไม CCW ถึงเป็น King

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

ทำไม? มุมไม่เป็นระเบียบ มุมนั้น “สกปรก” เมื่อคุณต้องคำนวณมุม คุณต้องหารหรือใช้ค่าประมาณ (เช่น อะไรก็ตามที่เกี่ยวข้องกับ Pi) หรือฟังก์ชันตรีโกณมิติ

เมื่อคุณต้องคำนวณมุม ในโค้ด คุณ จะ ต้องประมาณค่าประมาณทุกครั้ง คุณจะปิดด้วยระดับความแม่นยำจุดลอยตัวเล็กน้อย—ซึ่งสำคัญเมื่อคุณกำลังทดสอบความเท่าเทียมกัน คุณอาจแก้จุดหนึ่งในระนาบได้สองวิธีที่แตกต่างกัน และแน่นอน คาดหวังว่า p1.x == p2.x and p1.y == p2.y แต่ในความเป็นจริง การตรวจสอบนี้ มักจะ ล้มเหลว นอกจากนี้ (และค่อนข้างชัดเจน) จุดเหล่านี้จะมีแฮชต่างกัน

ที่เลวร้ายกว่านั้น ระดับความผิดพลาดของคุณจะเพิ่มขึ้นเมื่อความแตกต่างเล็กๆ น้อยๆ ของคุณแพร่กระจายผ่านการคำนวณของคุณ (สำหรับตัวอย่างทางวิทยาศาสตร์เพิ่มเติม บทความนี้จะกล่าวถึงสิ่งที่อาจผิดพลาดได้เมื่อคำนวณเปลือกนูนหรือสามเหลี่ยมเดเลาเนย์)

แล้วเราจะทำอะไรกับเรื่องนี้ได้บ้าง?

เกือบเท่ากับ

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

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

อันที่จริงรหัสนี้จะพิมพ์ว่า “Error!” ประมาณ 70% ของเวลา (เชิงประจักษ์) เราสามารถจัดการกับข้อกังวลนี้ได้โดยผ่อนปรนมากขึ้นเล็กน้อยกับคำจำกัดความของความเท่าเทียมกันของเรา นั่นคือโดยการเสียสละระดับของความถูกต้อง

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

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

ในทางปฏิบัติ สิ่งนี้มีประโยชน์มาก น้อยครั้งมากถ้าเคย คุณจะคำนวณจุดสองจุดที่ต่างกันน้อยกว่า 1e-5 ซึ่งจริงๆ แล้วหมายถึงจุดที่แตกต่างกัน ฉันขอแนะนำอย่างยิ่งให้ใช้การแทนที่ประเภทนี้ สามารถใช้วิธีการที่คล้ายกันสำหรับเส้นได้ เช่น

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

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

CCW คือ King

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

นี่เป็นตัวอย่างที่เป็นรูปธรรม สมมติว่าคุณมีรูปหลายเหลี่ยมนูน P จุดยอด v และจุดบางจุด u นอกรูปหลายเหลี่ยม คุณจะทราบได้อย่างไรว่าเส้น uv ตัดกับ P ด้านบนหรือด้านล่าง v หรือไม่เลย ในเวลาคงที่?

วิธีแก้ปัญหาด้วยกำลังเดรัจฉาน (นอกเหนือจากเวลาเชิงเส้น แทนที่จะเป็นค่าคงที่) อาจมีปัญหาเนื่องจากคุณจะต้องคำนวณจุดตัดของเส้นตรงบางจุด

วิธีการแบบคงที่ครั้งเดียวที่ฉันเคยเห็นเกี่ยวข้องกับ:

• การคำนวณบางมุมโดยใช้ arctan2
• แปลงมุมเหล่านี้เป็นองศาโดยคูณด้วย 180/Pi
• การตรวจสอบความสัมพันธ์ระหว่างมุมต่างๆ เหล่านี้

โชคดีที่ผู้เขียนใช้เทคนิค almostEqual ด้านบนเพื่อทำให้ข้อผิดพลาดจุดทศนิยมเป็นไปอย่างราบรื่น

ในความคิดของฉัน จะดีกว่าที่จะหลีกเลี่ยงปัญหาข้อผิดพลาดทศนิยมโดยสิ้นเชิง หากคุณใช้เวลาสักครู่เพื่อดูปัญหาบนกระดาษ คุณจะได้รับวิธีแก้ไขโดยอิงตาม CCW ทั้งหมด สัญชาตญาณ: ถ้าจุดยอดที่อยู่ติดกับ v อยู่ด้านเดียวกันของ uv แล้วเส้นจะไม่ตัดกัน มิฉะนั้น ให้ดูว่า u และ v อยู่ด้านเดียวกันของเส้นตรงระหว่างจุดยอดที่อยู่ติดกันหรือไม่ และเปรียบเทียบความสูงของจุดทั้งสอง โดยขึ้นอยู่กับผลลัพธ์

นี่คือรหัส Python สำหรับการทดสอบทางแยกด้านบน v (ทางแยกด้านล่างเพียงแค่กลับทิศทางของการเปรียบเทียบ):

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

วิธีแก้ปัญหาไม่ชัดเจนในทันทีด้วยตาเปล่า แต่เป็น ภาษา ของอัลกอริธึมเรขาคณิตเชิงคำนวณ 'ด้านเดียวกันของเส้นตรง' เป็นองค์ประกอบคลาสสิกของอัลกอริธึมที่เชื่อถือได้นั้น

ทำแล้วดีกว่าสมบูรณ์แบบ

ในวรรณคดีเรขาคณิตเชิงคำนวณ มักจะมีการใช้เวทมนตร์คาถาที่เกี่ยวข้องกับการปฏิบัติการที่ดูเหมือนง่าย ๆ อยู่พอสมควร สิ่งนี้ให้ทางเลือกแก่คุณ: คุณสามารถทำสิ่งที่ยากได้ ตามบทความที่กำหนดวิธีแก้ปัญหาขั้นสูงอย่างเหลือเชื่อสำหรับปัญหาที่ไม่ซับซ้อน — หรือคุณสามารถทำสิ่งต่าง ๆ ด้วยวิธีง่าย ๆ โดยใช้กำลังเดรัจฉานเล็กน้อย

อีกครั้ง ฉันจะใช้ตัวอย่าง: สุ่มตัวอย่างจุดภายในแบบสุ่มจากรูปหลายเหลี่ยมตามอำเภอใจ กล่าวอีกนัยหนึ่ง ฉันให้รูปหลายเหลี่ยมง่ายๆ แก่คุณ และคุณให้จุดสุ่มภายในรูปนั้น (กระจายอย่างสม่ำเสมอทั่วทั้งรูปหลายเหลี่ยม)

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

ตัวอย่างเช่น เราอาจพลาดสองครั้งและพบตัวอย่างที่ถูกต้องในจุดที่สามเท่านั้น:

นี่คือรหัส:

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

สิ่งนี้เรียกว่า การสุ่มตัวอย่างการปฏิเสธ : สุ่มคะแนนจนกว่าจะตรงตามเกณฑ์ของคุณ แม้ว่าอาจต้องใช้ตัวอย่างหลายตัวอย่างเพื่อหาจุดที่ตรงกับเกณฑ์ของคุณ แต่ในทางปฏิบัติ ความแตกต่างนั้นไม่สำคัญ สำหรับชุดทดสอบของคุณ แล้วทำไมต้องทำงานหนักขึ้นอีก? สรุป อย่ากลัวที่จะเลือกทางสกปรก เมื่อมีโอกาส

ยังไงก็ตาม: หากคุณต้องการอัลกอริทึม ที่แน่นอน สำหรับการสุ่มตัวอย่าง มีอัลกอริทึมที่ชาญฉลาดที่ฉันใช้ด้านล่างนี้ สาระสำคัญของมัน:

1. หารูปหลายเหลี่ยมของคุณเป็นสามเหลี่ยม (เช่น แบ่งเป็นสามเหลี่ยม)
2. เลือกสามเหลี่ยมที่มีความน่าจะเป็นเป็นสัดส่วนกับพื้นที่ของมัน
3. ใช้จุดสุ่มจากภายในสามเหลี่ยมที่เลือก (การดำเนินการแบบเวลาคงที่)

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

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

หวังว่าความพยายามพิเศษจะเห็นได้ชัดจากรหัส โปรดจำไว้ว่า: ตามที่ Facebook พูดไว้ว่า "ทำดีกว่าสมบูรณ์แบบ" เช่นเดียวกับปัญหาเรขาคณิตเชิงคำนวณ

การทดสอบด้วยภาพและอัตโนมัติ

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

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

การยืนยันว่าสมการนี้ดำเนินการอย่างถูกต้องนั้นเป็นเรื่องยากมากที่จะตรวจสอบผ่านโค้ด แต่จะชัดเจนในทันทีต่อสายตามนุษย์ หมายเหตุ: ฉันขอแนะนำให้ใช้ Matplotlib เพื่อช่วยในการทดสอบภาพของคุณ — มีคำแนะนำที่ดีที่นี่

ต่อมา เราจะต้องตรวจสอบว่าอัลกอริทึมระบุตำแหน่งอย่างถูกต้องหรือไม่ วิธีการสุ่มแบบอัตโนมัติคือการสร้างจุดภายในจำนวนมากสำหรับรูปหลายเหลี่ยมทุกอัน และตรวจสอบให้แน่ใจว่าเราส่งคืนรูปหลายเหลี่ยมที่ต้องการ ในรหัส:

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

จากนั้นเราสามารถใช้เมธอด runLocator กับชุดของรูปหลายเหลี่ยมชุดต่างๆ ได้ ทำให้เรามีชุดทดสอบที่หลากหลาย

โซลูชั่นโอเพ่นซอร์ส

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

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

• poly2tri: ไลบรารีที่ยอดเยี่ยมสำหรับการหารูปหลายเหลี่ยมที่รวดเร็ว ยังรองรับ (และมักจะมีความสำคัญ) รูปหลายเหลี่ยมที่มี รู อยู่ในนั้น เขียนด้วยภาษา C ++ poly2tri ยังมีการโยง Python และง่ายต่อการเริ่มต้นและใช้งาน ดูวิธี triangulate ของฉันด้านบนเพื่อดูการเรียกใช้ฟังก์ชัน
• scipy.spatial: รวมฟังก์ชันสำหรับการคำนวณเปลือกนูน สามเหลี่ยม Delaunay และอื่นๆ รวดเร็ว (เช่นเคย) เชื่อถือได้ ฯลฯ หมายเหตุ: ฉันพบว่ามีประโยชน์ในการใช้ประเภทข้อมูล Point ของตัวเองด้วยวิธี toNumpy : def np(self): return [self.x, self.y] จากนั้นฉันสามารถเรียกวิธีการ scipy.spatial ได้อย่างง่ายดายเช่น: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points))
• OpenCV: ไลบรารีคอมพิวเตอร์วิทัศน์โอเพนซอร์สมีโมดูลเรขาคณิตเชิงคำนวณแบบสแตนด์อโลนที่ดี โดยเฉพาะอย่างยิ่ง ฉันใช้ฟังก์ชันสามเหลี่ยมปิดขั้นต่ำของมันชั่วขณะหนึ่งก่อนจะใช้งานเอง

บทสรุป

ฉันหวังว่าโพสต์นี้จะทำให้คุณได้ลิ้มรสความงามของเรขาคณิตเชิงคำนวณในฐานะนักพัฒนา Python ซึ่งเป็นหัวข้อที่เต็มไปด้วยปัญหาที่น่าสนใจและแอปพลิเคชันที่น่าสนใจไม่แพ้กัน

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

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมหรือมีคำถามใดๆ เกี่ยวกับฉัน สามารถติดต่อฉันได้ที่ [email protected]