Хэширование, многоугольники относительно x, y местоположения

Question

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

Эти примеры хорошо работают, и вы хотите рассчитать их для каждого объекта.каждый раз, но я ищу способ «HASH» формы / области многоугольника относительно пространственного местоположения, а затем математика становится простой проверкой «HASH», чтобы найти, существует ли значение внутри или вне определенного »HASH ".

Я нашел несколько приличных базовых примеров:http://jsfromhell.com/math/is-point-in-poly,http://en.wikipedia.org/wiki/Point_in_polygon (алгоритм наведения лучей)

Answer 1

http://en.wikipedia.org/wiki/Geometric_hashing

Я думаю, это все хорошо объясняет.

Учитывая, что он действительно может использоваться только для определения схожести двух объектов (учитывая, что разность представляет собой простой набор преобразований), можно показать, что фактическая пространственная информация потеряна .

Поэтому ответ на ваш вопрос - нет.

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

Answer 2

Вы можете построить дерево, чтобы структурировать ваши полигоны или создать сетку, где вы можете хранить списки полигонов, которые пересекают ячейки.Это зависит от размера вашей проблемы и конкретных вещей.Основная идея состоит в том, чтобы работать только с полигонами, которые находятся вблизи точки.

Если вы имеете дело с геометрией Манхэттена, то вы можете рассмотреть возможность использования дерева интервалов,

см. Википедию: http://en.wikipedia.org/wiki/Interval_tree

и хорошая книга для подробностей:

Марк де Берг, Марк ван Кревельд, Марк Овермарс и Отфрид Шварцкопф.Вычислительная геометрия, второе пересмотренное издание.Springer-Verlag 2000. Раздел 10.1: Деревья интервалов, стр. 212–217.

Answer 3

Я думаю, что вопрос может быть немного прояснен, но для некоторых приложений простая ограничивающая рамка для каждого многоугольника может помочь вам быстро устранить некоторые из многоугольников, прежде чем приступить к точным вычислениям.