Попадает ли точка в многоугольник?

Всем привет!

У меня есть алгоритмы по определению попадания точки в многоугольник: алгоритм Weilerа, алгоритм суммы углов и т.д. (всего около десяти). Хотелось узнать, какой алгоритм работает быстрее. Может кто-нибудь занимался данным вопросом и подскажет какой алгоритм использовать. Мне нужен самый быстрый алгоритм.

И еще - очень нужны два очень быстрых алгоритма:
1. Алгоритм определения пересекаются ли два многоугольника.
2. Алгоритм расчета площади многоугольника.
Все многоугольники состоят из большого количества точек (порядка 500), внутри без дырок.
Буду признателен за ответы.

Ориентированная площадь многоугольника = 1/2*((x1-x2)(y1+y2)+(x2-x3)(y2+y3)+...+(xn-x1)(yn+y1))

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

Цитата Jin X, 04.02.03, 23:59:54

Ориентированная площадь многоугольника = 1/2*((x1-x2)(y1+y2)+(x2-x3)(y2+y3)+...+(xn-x1)(yn+y1))

Спасибо за формулу. Проверил, работает. Одно уточнение: полученное значение берется по модулю. (Правда, возможно это входило в понятие "ориентированная площадь" )

Цитата GrAnd, 05.02.03, 08:12:04

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

Если использовать данный алгоритм, то проверки попадания вершин одного многоугольника в другой будет недостаточно. Например, имеем что многоугольник1 пересекает всего одним своим ребром многоугольник2 по двум ребрам. При этом ни одна точка м1 не лежит в м2. И необходимо проверять попадание точек м2 в м1. А это мне кажется будет тормозить, учитывая, что у меня много многоугольников, состоящих из большого кол-ва точек.
Может есть более быстрый алгоритм? Ооооччччееень нужно.

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

Цитата GrAnd @ 05.02.03, 05:12

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

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

Добрый день, Коллеги!

Прошу прислать ссылку или написать алгоритм/алгоритмы: есть N точек случайно разбросанных на плоскости, задаём многоугольник - замкнутый контур, причём он может быть как выпуклым, так и впуклым. Необходимо определить количество точек M из общего числа N, которые находятся внутри данного многоугольника.


Спасибо!

Для каждой точки определяешь попадание в контур по отдельности. Подсчитываешь количество попадающих.
Предварительно можно отсеять не попадающие в габарит (описывающий прямоугольник).

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

Формула принадлежности треугольнику - существует. Алгоритм разбиения многоугольника на треугольники существует. Поиск в помощь.

Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри.

Цитата OpenGL @ 03.02.10, 13:26

Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри.

У меня не получилось по этому алгоритму....взятому из википедии....работало только на последовательных координатах

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 - кол-во вершин, остальное, думаю, понятно.

А что делать, если (V(n2).Y - V(n1).Y)=0
и откуда, вообще, алгоритм и как он называется?