ฉันได้ค้นคว้าอัลกอริธึมหลายอย่างเพื่อพิจารณาว่าจุดนั้นอยู่ในตัวถังนูนหรือไม่ แต่ดูเหมือนจะไม่พบอัลกอริธึมใด ๆ ที่สามารถทำกลอุบายในเวลา O (logn) ได้ และฉันก็ไม่สามารถคิดขึ้นมาเองได้ [] เป็นอาร์เรย์ที่มีจุดยอดของตัวเรือนูน ฉันสามารถประมวลผลอาเรย์นี้ล่วงหน้าได้หรือไม่ เพื่อให้สามารถตรวจสอบได้ว่าจุดใหม่อยู่ภายในตัวเรือนูนในเวลา O(logn) หรือไม่
ตรวจสอบว่าจุดอยู่ในตัวเรือนูนในเวลา O(log n) หรือไม่ [ซ้ำกัน]
comment
คุณอาจต้องการถามคำถามนี้ในไซต์คณิตศาสตร์ ดูเหมือนว่าคุณจะสนใจอัลกอริทึมมากกว่าการใช้งาน
- person Tim Biegeleisen schedule 02.03.2015
คำตอบ (1)
ดูเหมือนว่าคุณสามารถ
- จัดเรียงจุดยอดใน
a[]ตามมุมเชิงขั้วสัมพันธ์กับจุดยอดจุดใดจุดหนึ่ง (เรียกว่า A) O(N log N) เช่นการคำนวณตัวเรือแบบนูน - อ่านจุด กำหนดมุมเชิงขั้วของมัน โอ(1)
- ค้นหาจุดยอดข้างเคียงสองจุด หนึ่งในนั้นควรมีมุมเชิงขั้วน้อยกว่าจุดจากขั้นตอนที่ 2 และอีกจุดหนึ่งควรมีมุมที่ใหญ่กว่า (B และ C) O(log N) การค้นหาแบบไบนารี
- จากนั้นเรขาคณิตอย่างง่าย: วาดรูปสามเหลี่ยมระหว่างจุดจาก A, B, C และตรวจสอบว่าจุดจากขั้นตอนที่ 2 อยู่ข้างในหรือไม่ โอ(1)
person
Everv0id
schedule
02.03.2015
พอยต์คืออะไร 1, 2 และ 3 ในกรณีนี้คือจุด 1 จุดที่กำลังทดสอบ และจุด จุด 2 และ 3 ตรงตามเงื่อนไขในขั้นตอนที่ 3 หรือไม่
- person Andrew Brick; 02.03.2015
คุณช่วยอธิบายวิธีการทำขั้นตอนที่ 3 ในเวลา O (เข้าสู่ระบบ) ได้ไหม
- person Andrew Brick; 02.03.2015
ไม่ ขออภัยสำหรับคำย่อของฉัน :) pt.1 คือรายการที่ 1 (เรียงลำดับ) pt.2 คือรายการที่ 2 (จุดอ่าน) ฯลฯ
- person Everv0id; 02.03.2015
อ๋อ เข้าใจแล้ว แต่ยังเป็นไปได้ที่จุดจะไม่อยู่บนเส้นเชื่อมจุดข้างเคียงแต่ยังอยู่ในตัวเรือนูน
- person Andrew Brick; 02.03.2015
ดูเหมือนว่าฉันเข้าใจผิดปัญหาของคุณ คุณหมายถึงว่าจุดสามารถอยู่ภายในตัวเรือนูนได้ใช่หรือไม่?
- person Everv0id; 02.03.2015
ใช่ ฉันกำลังตรวจสอบว่ามันอยู่ภายในตัวเรือนูนหรือไม่ ไม่ใช่แค่บนขอบตัวเรือนูนเท่านั้น
- person Andrew Brick; 02.03.2015
ในขั้นตอนที่ 4 คุณกำลังตรวจสอบเพื่อดูว่าสามเหลี่ยมนั้นอยู่ในเซตนูนหรือไม่ แต่ฉันไม่คิดว่าสามารถทำได้ในเวลา O(1) มีวิธีที่จะทำในเวลา O(logn) หรือไม่
- person Andrew Brick; 02.03.2015
ไม่. ในขั้นตอนที่สี่ เรามีจุด A, B, C อยู่แล้ว หากจุดที่เราตรวจสอบอยู่นอกสามเหลี่ยม ABC นั่นหมายความว่าจุดนั้นอยู่นอกตัวเรือนูนทั้งหมด
- person Everv0id; 02.03.2015
ขออภัยสำหรับคำถามกองโต แต่ฉันมีอีกหนึ่งคำถามที่จะถาม มุมเชิงขั้วของจุดยอดคือมุมที่เวกเตอร์ไปจากจุดกำเนิดไปยังจุดยอดที่สร้างด้วยแกน x แต่ฉันไม่เคยเห็นมุมเชิงขั้วของจุดยอดที่สัมพันธ์กับจุดยอดอื่น (จุด A ในกรณีของเรา) นี่จะเป็นมุมระหว่างเวกเตอร์จากจุดกำเนิดถึงจุด กับเวกเตอร์จากจุดกำเนิดถึงจุด A หรือเปล่า
- person Andrew Brick; 02.03.2015
ตามหลักการแล้ว จุด (x1, y1) จะน้อยกว่าจุด (x2, y2) ก็ต่อเมื่อความชัน (y1 − y0) / (x1 − x0) น้อยกว่าความชัน (y2 − y0) / (x2 − x0) จากที่นั่น: coursera.cs.princeton.edu/algs4/assignments/collinear.html
- person Everv0id; 02.03.2015
คุณสามารถทำได้ง่ายๆ ใน Log(h) โดยใช้อัลกอริทึมของฉันโดยใช้ผลลัพธ์ควอแดรนท์กลาง ดู: codeproject.com/Articles/ 775753/ และ/หรือ (ล่าสุด) : codeproject.com/Articles/1210225/
- person Eric Ouellet; 22.11.2017
