#3 22.02.07 00:08
Re: Алгоритм определения положения точки отн-но n-угольника
проведи отрезок от точки до самого края поля в любую сторону
если количество пересечений со сторонам чётно то точка не внутри, иначе внутри
Offline
#6 22.02.07 09:49
Re: Алгоритм определения положения точки отн-но n-угольника
Простым перебором всех троек точек, принадлежащих многоугольнику, бъёшь его на треугольники. Далее определяешь, принадлежит ли точка хотя бы одному треугольнику (сумма площадей треугольников, составленных из тройки точек: две от треугольника, третья - твоя, с какой-то погрешностью равна площади саммого этого треугольника). Правда, такой метод сгодиться только для невыпуклых многоугольников.... но всегда можно модифицировать... :)
Offline
#8 22.02.07 13:46
Re: Алгоритм определения положения точки отн-но n-угольника
1. узлы многоугольника задаются последовательно
2. составляешь уравнения прямых проходящих через соседние узлы
3. вычисляешь точки пересечения всех прямых с прямыми y=yA и x=xA (см. рис.)
4. считаешь количество точек слева, справа, выше и ниже заданной точки
5. если хотябы с одной из сторон число точек нечетно, то точка лежит в пределах полигона
Исправлено Jaguar (22.02.07 13:49)
Offline
#10 22.02.07 14:49
#11 22.02.07 15:35
#12 22.02.07 16:57
#13 22.02.07 17:26
Re: Алгоритм определения положения точки отн-но n-угольника
Jaguar написал(а):
1. узлы многоугольника задаются последовательно
2. составляешь уравнения прямых проходящих через соседние узлы
3. вычисляешь точки пересечения всех прямых с прямыми y=yA и x=xA (см. рис.)
4. считаешь количество точек слева, справа, выше и ниже заданной точки
5. если хотябы с одной из сторон число точек нечетно, то точка лежит в пределах полигона
тока не прямых, а отрезков ;-)))
как вариант: а если анализировать пересечения только для одного отрезка, соединяющего точку А и точку на границеи проходящий через центр тяжести многоугольника? так не проще?
Offline
#14 22.02.07 17:28
Re: Алгоритм определения положения точки отн-но n-угольника
В комп. графике много алгоритмов всяких, если не изменяет память то есть алгоритм Кируса-Бэка.
Метода: ftp://217.71.141.40/upload/metods_comp_graph.doc
Offline
#15 22.02.07 19:19
#16 23.02.07 13:34
Re: Алгоритм определения положения точки отн-но n-угольника
s050103613 написал(а):
проведи отрезок от точки до самого края поля в любую сторону
если количество пересечений со сторонам чётно то точка не внутри, иначе внутри
Это классический алгоритм. Один из самых простых и верный - лучше использовать именно его
Offline
#17 23.02.07 14:49
Re: Алгоритм определения положения точки отн-но n-угольника
s050103613 написал(а):
проведи отрезок от точки до самого края поля в любую сторону
если количество пересечений со сторонам чётно то точка не внутри, иначе внутри
надо учитывать что пересечет не линию многоугольника а вершину
Offline
