На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS RSS
>  Форум на Исходниках.RU
       Программирование
         Алгоритмы
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, esperanto
   Новое голосование

> Попадает ли точка в многоугольник?
cosmos
Сообщ. #1, 04.02.03, 11:19
Unregistered

Всем привет!

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

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

Законченный оптимист
*******
Профиль · PM

Поощрения: 23 Dgm
Рейтинг (т): 94

Ориентированная площадь многоугольника = 1/2*((x1-x2)(y1+y2)+(x2-x3)(y2+y3)+...+(xn-x1)(yn+y1))
___________
Жизнь дается один раз, и этим шансом надо воспользоваться по максимуму. © Ричард Брэнсон
GrAnd
Сообщ. #3, 05.02.03, 05:12

Profi
*****
Профиль · PM

Рейтинг (т): 15

Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого.
___________
Подпись была выключена в связи с наложенным наказанием.
Да ну и фиг с ней
cosmos
Сообщ. #4, 05.02.03, 11:40
Unregistered

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

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

Цитата (GrAnd, 05.02.03, 08:12:04)
Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого.
Если использовать данный алгоритм, то проверки попадания вершин одного многоугольника в другой будет недостаточно. Например, имеем что многоугольник1 пересекает всего одним своим ребром многоугольник2 по двум ребрам. При этом ни одна точка м1 не лежит в м2. И необходимо проверять попадание точек м2 в м1. А это мне кажется будет тормозить, учитывая, что у меня много многоугольников, состоящих из большого кол-ва точек.
Может есть более быстрый алгоритм? Ооооччччееень нужно.
experimenter
Сообщ. #6, 05.02.03, 11:57

Master
******
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 26

ну,я тоже так думал. тогда надо просто проверять попадает ли точка в отрезок (ребро). задать параметрически этот отрезок и проверить. времени нет объснять.
___________
Trying is the first step towards failure.
Danil
Сообщ. #7, 17.04.07, 09:15
Unregistered

Цитата (GrAnd @ 05.02.03, 05:12)
Что касается пересечения многоугольников, то для одного из многоугольников достаточно перебрать все точки его вершин и посмотреть лежит ли какая из них внутри другого.

Нет. Этот алгоритм только для частного случая. Даже если для каждой точки ОБОИХ многоугольников проверить. Это не будет работать для некоторых случаев...очень реальных случаев. Взять хотя бы два прямоугольника, пересекающихся в виде буквы "Х". Для этого случая не сработает.
Нужно брать ребра одного многоугольника и искать пересечения с ребрами другого. И кстати еще отдельно обрабатывать случаи когда точка одного многоугольника лежит на ребре другого.
StigMaster
Сообщ. #8, 03.02.10, 10:06
Newbie
Профиль · PM

Рейтинг (т): 0

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

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


Спасибо!
Guru Akina
Сообщ. #9, 03.02.10, 11:18
Guru
*******
Профиль · PM

Поощрения: 35 Dgm
Рейтинг (т): 410

Для каждой точки определяешь попадание в контур по отдельности. Подсчитываешь количество попадающих.
Предварительно можно отсеять не попадающие в габарит (описывающий прямоугольник).
___________
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
malefik
Сообщ. #10, 03.02.10, 11:46
Junior
*
Профиль · PM

Рейтинг (т): нет

Добрый день, Коллеги!
Необходима формула принадлежности точки многоугольнику...хот выпуклому хоть впуклому.....координаты точек не последовательны т.е. не идут друг за другом описывая многоугольник .....а в разнобой.....пробовал несколько алгоритмов...
Guru Akina
Сообщ. #11, 03.02.10, 11:50
Guru
*******
Профиль · PM

Поощрения: 35 Dgm
Рейтинг (т): 410

Формула принадлежности треугольнику - существует. Алгоритм разбиения многоугольника на треугольники существует. Поиск в помощь.
___________
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Profi OpenGL (Online)
Сообщ. #12, 03.02.10, 13:26

Profi
*****
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 67

Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри.
___________
Подпись была включена в связи с окончанием срока наказания
malefik
Сообщ. #13, 03.02.10, 15:46
Junior
*
Профиль · PM

Рейтинг (т): нет

Цитата (OpenGL @ 03.02.10, 13:26)
Формула, как я понимаю, это алгоритм определения? тогда один из самых простых алгоритмов - пускаешь луч из своей точки, если он пересекает границу четное число раз, то точка снаружи, иначе внутри.

У меня не получилось по этому алгоритму....взятому из википедии....работало только на последовательных координатах
Senior Member Mikle
Сообщ. #14, 03.02.10, 16:49

Senior Member
****
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 60

cosmos
Вот ф-ция определения попадания точки в полигон, можно невыпуклый:
ExpandedWrap disabled
    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 - кол-во вершин, остальное, думаю, понятно.
ttiger
Сообщ. #15, 03.03.11, 22:56

Profi
*****
Профиль · PM

Рейтинг (т): 14

А что делать, если (V(n2).Y - V(n1).Y)=0
и откуда, вообще, алгоритм и как он называется?
___________
Цитата (Коцмас(Вуйко, который тролит из Лондона) @ 22.01.14, 16:43)
Мы защищаем Киев, если ты не понял.
Senior Member Mikle
Сообщ. #16, 04.03.11, 06:58

Senior Member
****
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 60

ttiger
Деления на 0 не произойдёт - не пропустит строка:
ExpandedWrap disabled
    If (Y > V(n1).Y) Xor (Y > V(n2).Y) Then

Алгоритм мой. Просто нахожу количество пересечений луча из точки в бесконечность с полигоном.
prografix
Сообщ. #17, 04.03.11, 11:05
Full Member
***
Профиль · PM

Рейтинг (т): 19

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

Добавлено 04.03.11, 11:10
В книге Ласло "Вычислительная геометрия и ..." есть правильная реализация.
Senior Member Mikle
Сообщ. #18, 04.03.11, 11:14

Senior Member
****
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 60

prografix
Различает. Она не различает только попадания самой точки на границу полигона, но даже тут она ведёт себя по-своему правильно - если мы разделим плоскость на полигоны со смежными сторонами, то никогда не получится, что точка попадёт сразу в два полигона, или не попадёт ни в один.
Mishamp
Сообщ. #19, 04.03.11, 12:49
Member
**
Профиль · PM

Рейтинг (т): 11

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

давненнько

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

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

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

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

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

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


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

дальше чтоби проверить пересикаютса ли сами отрезки нужно взяти их вектора отрезков
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)
Планарный граф

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


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




:scratch: мне кажетса любой ритерии должен бить тотже
граф который построиш будет планарным... следовательно ето необходимое требование
(достаточное ли - незнаю нужно подумать :scratch:)
prografix
Сообщ. #20, 04.03.11, 15:06
Full Member
***
Профиль · PM

Рейтинг (т): 19

Цитата (Mikle @ 04.03.11, 11:14)
Различает.

Да, похоже, что так. Сразу я как-то не разглядел.
amk (Online)
Сообщ. #21, 04.03.11, 16:13

Guru
*******
Профиль · PM

Поощрения: 4 Dgm
Рейтинг (т): 230

Проходя через вершину точка считается пересекающейся только с теми сторонами, которые лежат ниже луча (вроде так). Поэтому, если луч только касается угла, получается или 0 или 2 точки пересечения.
___________
Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
andriano
Сообщ. #22, 04.03.11, 18:31
Profi
*****
Профиль · PM

Поощрения: 6 Dgm
Рейтинг (т): 56

Цитата (malefik @ 03.02.10, 11:46)
Добрый день, Коллеги!
Необходима формула принадлежности точки многоугольнику...хот выпуклому хоть впуклому.....координаты точек не последовательны т.е. не идут друг за другом описывая многоугольник .....а в разнобой.....пробовал несколько алгоритмов...

Если точки идут не последовательно, то это не многоугольник.
Для точек идущих в произвольном порядке может существовать выпуклая оболочка. Других способов однозначно построить многоугольник из набора точек в произвольном порядке, насколько мне известно не существует.
Но выпуклая оболочка может быть ТОЛЬКО выпуклой. Что противоречит условию.
Т.о. задача некорректно сформулирована - содержит внутренние противоречия.
amk (Online)
Сообщ. #23, 06.03.11, 12:28

Guru
*******
Профиль · PM

Поощрения: 4 Dgm
Рейтинг (т): 230

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

> Форум на Исходниках.RU · Алгоритмы

Новое голосование


[ Script Execution time: 0,2013 ]   [ 15 queries used ]   [ Generated: 20.04.14, 15:52 GMT ]  

Rambler's Top100