Войти
ПрограммированиеФорумФизика

Принадлежит ли точка территории?

#0
2:51, 17 сен. 2006

Задача больше математическая.
Есть стандартная  координатная плоскость (x,y)
Есть участок ( к примеру пятиугольник) , описанный массивом координат - вершин  записаные в порядке соединения отрезками, последняя вершина соеденятся с первой.

Задача. Имея координаты посторонней точки узнать - принадлежит ли заданная точка известнму нам участку. ТОесть находиться ли данная точка в пределах участка или за его пределами.
Дайте пожалуйста алгоритм или хотябы куда смотреть.


#1
3:28, 17 сен. 2006

пускаешь из этой точки луч (лучше, есс-но, вертикальный или горизонтальный - это ускорит рассчеты) и смотришь, сколько пересечений с многоугольником получилось (ищешь пересечения с каждым отрезком, попадания в точки соединения отрезков считаешь одним пересечением, не двумя): если нечетное, то внутри - если четное, то снаружи

не забудь только перед этим проверить, не лежит ли она на каком-то отрезке - ибо это третий отдельный случай
хотя определить это будет проще из найденных точек пересечения: если среди них будет точка с нулевыми координатами (от начала луча), значит лежит на многоугольнике

еще про численно-стабильные вычисления почитай, без них могут возникнуть проблемы при появлении маленьких расстояний из-за погрешностей

#2
10:57, 17 сен. 2006

Ещё можно пустить из точки вектора во все вершины участка, найти углы между соседними векторами (скалярным произведением), если сумма всех углов будет ~360 градусов - точка внутри.

З. Ы.
Ещё можно попрбовать через векторное произведение, но это надо думать :)

#3
11:44, 17 сен. 2006

Что тут думать. Множить векторно вектора ребер (для пятиугольника AB, BC, CD, DE, EA) на вектор, образованный началом ребра и точкой O (AO, BO, CO, DO, EO)
Если точка внутри, то направление векторного произведения (в данном случае просто знак Z-координаты) будет для всех вершин одно.

#4
12:35, 17 сен. 2006

DimanX
Достаточно интересный способ. Но вершин может оказаться около 10 000. А главное - быстродействие.
Rageous
Идея ясна способ не подходит. Будет на громадной территории (земли) будет несколько больших и десяток мелких территорий. Задача заключается в определении на каком участке сейчас находимся.
Если территория задается квадратами - то это елементарщина типа меньше но больше.
А задача поменялась и теперь площадки задаются вершинами.
Так что пуск вектора не подходит.
Mirage

Просто не понял о чем ты сказал -- образование немножно не то. Щас полезу читать - вспоминать школу

#5
12:49, 17 сен. 2006

Мда. А если территория просто ВПУКЛАЯ?

#6
14:10, 17 сен. 2006

CrazyMan
>Задача заключается в определении на каком участке сейчас находимся.
Можно использовать порталы:
1) в начале находимя в участке номер 0 (например)
2) если при движении не пересекаем границу участка, то значит остались в нем же
3) если пересекли границу, то попадаем в новый участок, номер нового участка хранится в ребре границы.

Тонда не надо проверять все участки, только ребра текущего участка (если в нем очень много ребер, можно дробить его на сектора меньшего размера).

#7
14:32, 17 сен. 2006

CrazyMan: Если "впуклая", то способ с векторными произведениями все равно не подходит. Тогда см. способ предложенный Rageous - он универсален.
Дальше - оптимизации, если будет тормозить. Что при десятках территорий не факт.

#8
14:36, 17 сен. 2006

CrazyMan
Все таки не понятно почему способ с подсчетом числа пересечений луча из искомой точки в бесконечность с ребрами не подходит.
Если территории статичны или изменяются сравнительно редко можно отрезки засунуть в какую-нибудь partitioning structure, например квадродерево или БСП и делать трассировку уже через это дерево будет быстро.
Наконец можно просто нарисовать все эти территории видеокартой и посмотреть что в интересующей точке. Правда если территории такие замороченные потребуется тесселяция и полигонов будет довольно много.

#9
15:19, 17 сен. 2006

Реализация будет производиться на очень ограниченном скриптовом языке где слава богу есть поддержка хотя бы математических функций...
Способ с векторами - буду изучать и думать...

#10
14:00, 18 сен. 2006

CrazyMan, чего-то ты не воткнул в мой способ ^_^

ПрограммированиеФорумФизика

Тема в архиве.