Правильная структура данных для алгоритма расположения точек

python algorithm computer-science computational-geometry planar-graph

365 просмотра

2 ответа

708 Репутация автора

Я имею дело с проблемой программирования, в которой мне нужно найти регион, к которому относится данный пункт. Здесь есть несколько методов для решения этой проблемы.

Точка Расположение

Поэтому я решил использовать разложение плит: оно достаточно быстрое, более простое в реализации, и пространство для меня не является большой проблемой. Однако у меня возникли проблемы с тем, с чего начать. Вот пример разложения плиты из файла 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: я знаю, как найти, какие плиты лежат в основе. Я также знаю, как найти точку с помощью бинарного поиска внутри плит. Мне не хватает более глубоких знаний, а значит, и опыта. Например, как представлять регионы в первую очередь.

Заранее спасибо.

Автор: Max Paython Источник Размещён: 18.07.2016 02:52

Ответы (2)


0 плюса

1303 Репутация автора

Я бы посоветовал использовать ваши вершины только для справки. Используйте список ребер для представления графика и назначьте левую и правую области инцидента для каждого ребра. Теперь используйте эти края в разложении плит. Как только вы найдете свою плиту и свою часть плиты, вы также узнаете ее область, так как оба ребра рядом с вашей точкой привязки к ней.

Автор: gue Размещён: 19.07.2016 07:37

0 плюса

2203 Репутация автора

Если вы знаете, что ваши данные будут использоваться много раз для определения местоположения нескольких точек, то имеет смысл предварительно обработать исходный планарный график и разложить его на куски. Тогда проблема структуры данных, с которой вы столкнетесь, будет сведена к проблеме представления плит.

А что такое плита? Это на самом деле одномерная последовательность ребер. Итак, вы уменьшите исходную проблему до двух бинарных поисков - первый в массиве slabs, а второй - в массиве edge. Бинарный поиск в массиве ребер должен быть немного изменен - ​​вам нужно будет найти пару ребер, ограничивающих контрольную точку сверху и снизу (я имею в виду вашу картинку здесь) как можно ближе ,

И, конечно, вам нужно хранить ссылки на оригинальные метки лица где-нибудь в массиве ребер.

Автор: HEKTO Размещён: 01.08.2016 03:11
Вопросы из категории :
32x32