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

[Mikle]

ttiger
Деления на 0 не произойдёт - не пропустит строка:

If (Y > V(n1).Y) Xor (Y > V(n2).Y) Then

Алгоритм мой. Просто нахожу количество пересечений луча из точки в бесконечность с полигоном.

[prografix]

Эта реализация алгоритма ненадёжна, т.к. она не различает случаи прохождения луча через вершину, когда смежные рёбра по одну сторону от луча и по разные. А вообще алгоритм известный. Его называют "метод луча".

Добавлено 04.03.11, 11:10
В книге Ласло "Вычислительная геометрия и ..." есть правильная реализация.

[Mikle]

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

[Mishamp]

Сообщ. #1 от 4.02.03,

давненнько

прочел
и от что скажу
когда я учился в универе у нас бил предмет
називался: "Вичислительная геометрия и компютерная графика"

так от ето наука занимаитса именнто такими типами задач
(подроздел: Здадача локализации точки)
там есть много разних способов

так от простейший для програмирование
и ктому же занимает всего лиш O(N) процесорного времени
ето алгоритм:
1) взять точку вне полигона
2) провести отрезок между искомои точкой и точкои вне полигона
3) подсчитать количество пересечений между полигоном и отрезком

если количество пересичение являетса четним числом тогда точка внутри полигона
если количество пересичение являетса нечетним числом тогда точка вне полигона
пример


(предупреждаю если канешно погигон рисовать методом Even-Odd но не методом Winding
тогда нужно считать пересечение +1 -1 по направлению векторов)

(можно канешно и за O(Log(n) времени - если полигон будет разбит на триугольники методом триангуляции, и проитись дерево разбиение и тогда только проверять входит ти в оответствующии треугольник и не надо будет проверят в других областях)


что касательно песечении отрезков нужно
предварительно проверять на пересичение прямоугольников влежащиг в отрезок
ето всего лиш условие такого вида:
(ln1.x1<=ln2.x2)&&(ln1.y1<=ln2.y2)&&(ln1.x2>=ln2.x1)&&(ln1.y2>=ln2.y1)
с точки зрение програмирование ето очень бистро, и в тоже время отсекаетса очень много отрезков полигона


дальше чтоби проверить пересикаютса ли сами отрезки нужно взяти их вектора отрезков
dx1 = ln1x2 - ln1x1; dy1 = ln1y2 - ln1y1;
dx2 = ln2x2 - ln2x1; dy2 = ln2y2 - ln2y1;

тогда параметрами точки пересичение будет значение t1 и t2:

dotvect = dx1*dy2 - dx2*dy1;
t1 = ( dy2 * ln1x1 - dx2 * ln1y1 + dx2 * ln2x1 - dy2 * ln2x1)/ dotvect;
t2 = -(-dy1 * ln1x1 + dx1 * ln1y1 - dx1 * ln2x1 + dy1 * ln2x1)/dotvect;

тепер анализируем:
если 0<= t1 <= 1 и 0<= t2 <= 1 - отрески пересикаютса иначе пересикаютса сами линии но не отрезки на них
если t1 = 1 или t1 = 0 значит пересечение отрезков на краю (так же и t2 = 0 или t2 = 1)
если (dx1 = 0 и dy1 = 0 ) - значит на входе первии отрезок не отрезок а точка (получаетса исчем пересечение отрезка и точки)
также и (dx2 = 0 и dy2 = 0 ) - значит на входе первии отрезок не отрезок а точка (получаетса исчем пересечение отрезка и точки)
если dotvect = 0 - тогда вектори паралельние соответствено невозможно наити пересечение паралельних отрезков
точку пересичение если нужно тогда можена посчетать : x = ln1x1 + dx1*t1; x = ln1y1 + dy1*t1; (или x = ln2x1 + dx2*t2; x = ln2y1 + dy2*t2; )

трудности обично бивают имено с етим анализом - гдето вискакивент 0 и происходит деление на нуль



что касательно провертить два полигона пересикаютсаа ли
ну ету задачу я всегда решал "в лоб" - проверял каждую линию с каждой не забивая про проверку прямуугольников
хотя и степень проверки получаетса O(N^2) но даже если 1000 точек проблем у мене не визивало ... поскольку нинешние процесори довольно шустрие и даже 1000 точек справитса в секунду... поскольку бистро исчетса пересикание (ктомуже если находит дальше искать ненадо)

Добавлено 04.03.11, 12:56
прошу просчение
питался много полностю раскрить суть и приношу извеннение за опечатки

Цитата

точку пересичение если нужно тогда можена посчетать : x = ln1x1 + dx1*t1; x = ln1y1 + dy1*t1; (или x = ln2x1 + dx2*t2; x = ln2y1 + dy2*t2; )

x = ln1x1 + dx1*t1; y = ln1y1 + dy1*t1; (или x = ln2x1 + dx2*t2; y = ln2y1 + dy2*t2; )

Добавлено 04.03.11, 13:26
цитата с другого форума

Цитата Sergeyev

Цитата Adopt

Планарный граф

Возник вопрос по графам:
Каким образом можно построить планарный граф по заранее известному количеству вершин, ребер?

Первое что на ум пришло - добавлять поочередно ребра туда, где не будет образовываться недопустимых подграфов, граф содержащий которые непланарный.
Не пробовали?
Другое дело что результат такого процесса все равно надо будет отобразить планарно, сразу планарную укладку так не получить...

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

[prografix]

Цитата Mikle @ 04.03.11, 11:14

Различает.

Да, похоже, что так. Сразу я как-то не разглядел.

[amk]

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

[andriano]

Цитата malefik @ 03.02.10, 11:46

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

Если точки идут не последовательно, то это не многоугольник.
Для точек идущих в произвольном порядке может существовать выпуклая оболочка. Других способов однозначно построить многоугольник из набора точек в произвольном порядке, насколько мне известно не существует.
Но выпуклая оболочка может быть ТОЛЬКО выпуклой. Что противоречит условию.
Т.о. задача некорректно сформулирована - содержит внутренние противоречия.

[amk]

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