Я имею дело с проблемой программирования, в которой мне нужно найти область, к которой принадлежит данная точка. Здесь есть несколько методов для решения этой проблемы.
Поэтому я решил использовать разбиение на плиты. Это достаточно быстро, проще в реализации, и пространство для меня не представляет большой проблемы. Однако у меня возникли проблемы с тем, с чего начать. Вот пример разложения плиты из pdf-файла, созданного Калифорнийским университетом в Санта-Барбаре.
Я храню геометрическую форму в словаре узлов, как неориентированный граф (с использованием координат).
defaultdict(<type 'list'>, {(4.0, 5.0): [(1.0, 2.0), (2.0, 3.0), (3.0, 5.0)],
(1.0, 2.0): [(2.0, 3.0), (2.0, 4.0), (3.0, 5.0), (4.0, 5.0)],
(2.0, 3.0): [(1.0, 2.0), (2.0, 4.0), (4.0, 5.0)],
(2.0, 4.0): [(1.0, 2.0), (2.0, 3.0), (3.0, 5.0)],
(3.0, 5.0): [(1.0, 2.0), (2.0, 4.0), (4.0, 5.0)]})
Вот так. (Все еще не знаете, будет ли список ребер лучше?)
Теперь я знаю, как решить проблему, однако мне трудно решить, какой способ реализовать, потому что входные данные будут очень сложной геометрической формой, а поиск точки будет затратным по ресурсам процессора.
Я решил хранить каждую точку (отсортированную по координатам x) в отсортированном списке (используя деление пополам). Для приобретения плит. Однако я не смог найти способ найти, как плиты пересекаются с краями области, или как разделить плиту, как показано на рисунке. На самом деле я нашел способ, но он не казался мне осуществимым. Я мог бы проверить края, которые начинаются слева от плиты и заканчиваются справа от нее. Это означает, что край пересекает плиту. Это нормально, однако для этого мне пришлось бы проверять почти половину вершин каждый раз, когда задается новый узел и увеличиваются области. Итак, этот метод показался мне неудачным. Существует также проблема с знанием того, к какому региону принадлежит регион в плите. Учитывая, что мы делаем все это, чтобы не проверять все регионы один за другим для повышения скорости.
Если бы вы могли дать мне несколько идей по этому вопросу, мне не нужен код. Мне просто нужен совет от опытных пользователей здесь. Я застрял, потому что я не уверен, как это реализовать, и я не хочу начать с неправильного пути и переписать его целиком. (Уверяю вас, это не домашнее задание.)
Примечание 1: я не был уверен в структуре данных, должен ли я создавать структуру для регионов? Или для точек? или края? Или мне нужна структура для создания дерева поиска? Что я должен хранить в этой структуре?
Примечание 2: я знаю, как определить, на каких плитах лежит точка. Я также знаю, как найти точку с бинарным поиском внутри плит. Мне не хватает более концептуальных знаний, следовательно, опыта. Например, как представлять регионы в первую очередь.
Заранее спасибо.
