ฉันได้เขียนแอป GUI ที่ใช้ win32 api ซึ่งใช้คุณสมบัติ GDI+ เช่น DrawCurve() และ DrawLine()
แอปนี้วาดเส้นและเส้นโค้งที่แสดงถึงมัลติกราฟ
โครงสร้างข้อมูลสำหรับ Edge เป็นเพียงโครงสร้างของห้า int (x1, y1, x2, y2 และรหัส)
หากมีขอบเพียงด้านเดียวระหว่างจุดยอดสองจุด ส่วนของเส้นตรงจะถูกวาดโดยใช้ DrawLine() หากมีขอบมากกว่าหนึ่งเส้น เส้นโค้งจะถูกวาดโดยใช้ DrawCurve() -- ในที่นี้ ฉันกระจายขอบเส้นตรงรอบจุดกึ่งกลางของจุดยอดทั้งสอง ทำให้เป็นเส้นโค้ง จุดที่มีหน่วยพิกเซลนอกเหนือจากนั้นจะถูกคำนวณโดยใช้สมการเส้นปกติ หากมีการเพิ่มขอบมากขึ้น จะเลือกพิกเซลสองหน่วยพิกเซลนอกเหนือจากจุดกึ่งกลาง จากนั้นครั้งถัดไปจะเป็น 3 หน่วยพิกเซล และอื่นๆ
ตอนนี้ฉันมีคำถามสองข้อในการตรวจจับการคลิกที่ขอบ
ในการค้นหาขอบเส้นตรง เพื่อลดเวลาในการค้นหา ฉันควรทำอย่างไร
การตรวจสอบว่าพิกเซลที่คลิกนั้นอยู่บนส่วนของเส้นนั้นค่อนข้างง่าย แต่การเปรียบเทียบขอบทั้งหมดจะไม่มีประสิทธิภาพหากจำนวนขอบมีขนาดใหญ่ ดูเหมือนว่าเป็นไปได้ที่จะทำใน O(log n) โดยที่ n คือจำนวนขอบ
แก้ไข: ณ จุดนี้ขอบ (คลาส Edge) จะถูกเก็บไว้ใน std::map ที่แมป edge id (int)' ไปยังวัตถุ Edge และฉันกำลังพิจารณาที่จะประกาศคอนเทนเนอร์อื่นที่แมปพิกเซลกับ edge id's
ฉันกำลังพิจารณาใช้แผนผังการค้นหาแบบไบนารี แต่อะไรจะเป็นกุญแจสำคัญได้ หรือฉันควรใช้เพียงอาร์เรย์พิกเซล 2D?ฉันสามารถรับอาร์เรย์ของคะแนนที่ใช้โดย DrawCurve() ได้หรือไม่ หากเป็นไปไม่ได้ ฉันควรคำนวณคาร์ดินัลสไปลน์ใหม่ รับอาร์เรย์ของจุด และตรวจสอบว่าจุดที่ผู้ใช้คลิกตรงกับจุดใดๆ ในอาร์เรย์นั้นหรือไม่