Локалізація точки
З Вікіпедії, безкоштовно encyclopedia
Локалізація точки є однією з фундаментальних задач обчислювальної геометрії. Вона знаходить застосування в галузях, що оперують геометричною інформацією: комп'ютерна графіка, геоінформаційні системи (ГІС), планування руху і системи автоматизованого проектування (САПР).
У найзагальнішому вигляді, завдання полягає в тому, щоб для заданого розбиття простору на області (вони не перетинаються), визначити область, якій належить точка запиту. Приклад застосування: після кожного клацання мишею на екрані монітору, проблема локалізації точки повинна бути вирішена для того, щоб визначити, яка область екрана комп'ютера знаходиться під вказівником миші.
Простим, але важливим випадком є задача про належність точки многокутнику. У цьому випадку, ми повинні визначити, знаходиться точка всередині, зовні чи на межі заданого полігону.
У багатьох застосунках, потрібно визначити місце розташування декількох різних точок відносно одного й того ж розбиття простору. Для ефективного вирішення цієї проблеми корисно створити структуру даних, яка, розрахована на масові запити і швидко визначає, яка область містить точку запиту.