Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.141.202.187] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем привет!
У меня есть алгоритмы по определению попадания точки в многоугольник: алгоритм Weilerа, алгоритм суммы углов и т.д. (всего около десяти). Хотелось узнать, какой алгоритм работает быстрее. Может кто-нибудь занимался данным вопросом и подскажет какой алгоритм использовать. Мне нужен самый быстрый алгоритм. И еще - очень нужны два очень быстрых алгоритма: 1. Алгоритм определения пересекаются ли два многоугольника. 2. Алгоритм расчета площади многоугольника. Все многоугольники состоят из большого количества точек (порядка 500), внутри без дырок. Буду признателен за ответы. |
Сообщ.
#2
,
|
|
|
Ориентированная площадь многоугольника = 1/2*((x1-x2)(y1+y2)+(x2-x3)(y2+y3)+...+(xn-x1)(yn+y1))
|
Сообщ.
#3
,
|
|
|
Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого.
|
Сообщ.
#4
,
|
|
|
Цитата Jin X, 04.02.03, 23:59:54 Ориентированная площадь многоугольника = 1/2*((x1-x2)(y1+y2)+(x2-x3)(y2+y3)+...+(xn-x1)(yn+y1)) Спасибо за формулу. Проверил, работает. Одно уточнение: полученное значение берется по модулю. (Правда, возможно это входило в понятие "ориентированная площадь" ) |
Сообщ.
#5
,
|
|
|
Цитата GrAnd, 05.02.03, 08:12:04 Если использовать данный алгоритм, то проверки попадания вершин одного многоугольника в другой будет недостаточно. Например, имеем что многоугольник1 пересекает всего одним своим ребром многоугольник2 по двум ребрам. При этом ни одна точка м1 не лежит в м2. И необходимо проверять попадание точек м2 в м1. А это мне кажется будет тормозить, учитывая, что у меня много многоугольников, состоящих из большого кол-ва точек. Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого. Может есть более быстрый алгоритм? Ооооччччееень нужно. |
Сообщ.
#6
,
|
|
|
ну,я тоже так думал. тогда надо просто проверять попадает ли точка в отрезок (ребро). задать параметрически этот отрезок и проверить. времени нет объснять.
|
Сообщ.
#7
,
|
|
|
Цитата GrAnd @ Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого. Нет. Этот алгоритм только для частного случая. Даже если для каждой точки ОБОИХ многоугольников проверить. Это не будет работать для некоторых случаев...очень реальных случаев. Взять хотя бы два прямоугольника, пересекающихся в виде буквы "Х". Для этого случая не сработает. Нужно брать ребра одного многоугольника и искать пересечения с ребрами другого. И кстати еще отдельно обрабатывать случаи когда точка одного многоугольника лежит на ребре другого. |
Сообщ.
#8
,
|
|
|
Добрый день, Коллеги!
Прошу прислать ссылку или написать алгоритм/алгоритмы: есть N точек случайно разбросанных на плоскости, задаём многоугольник - замкнутый контур, причём он может быть как выпуклым, так и впуклым. Необходимо определить количество точек M из общего числа N, которые находятся внутри данного многоугольника. Спасибо! |
Сообщ.
#9
,
|
|
|
Для каждой точки определяешь попадание в контур по отдельности. Подсчитываешь количество попадающих.
Предварительно можно отсеять не попадающие в габарит (описывающий прямоугольник). |
Сообщ.
#10
,
|
|
|
Добрый день, Коллеги!
Необходима формула принадлежности точки многоугольнику...хот выпуклому хоть впуклому.....координаты точек не последовательны т.е. не идут друг за другом описывая многоугольник .....а в разнобой.....пробовал несколько алгоритмов... |
Сообщ.
#11
,
|
|
|
Формула принадлежности треугольнику - существует. Алгоритм разбиения многоугольника на треугольники существует. Поиск в помощь.
|
Сообщ.
#12
,
|
|
|
Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри.
|
Сообщ.
#13
,
|
|
|
Цитата OpenGL @ Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри. У меня не получилось по этому алгоритму....взятому из википедии....работало только на последовательных координатах |
Сообщ.
#14
,
|
|
|
cosmos
Вот ф-ция определения попадания точки в полигон, можно невыпуклый: Private Function PointInPolygon(ByVal X As Single, ByVal Y As Single) As Boolean Dim n1 As Long, n2 As Long, f As Boolean For n1 = 0 To vCnt - 1 n2 = (n1 + 1) Mod vCnt If (Y > V(n1).Y) Xor (Y > V(n2).Y) Then If X > V(n1).X + (V(n2).X - V(n1).X) * (Y - V(n1).Y) / (V(n2).Y - V(n1).Y) Then f = Not f End If End If Next n1 PointInPolygon = f End Function Это визуал бейсик. V() - массив векторов (вершин полигона), vCnt - кол-во вершин, остальное, думаю, понятно. |
Сообщ.
#15
,
|
|
|
А что делать, если (V(n2).Y - V(n1).Y)=0
и откуда, вообще, алгоритм и как он называется? |