Devion
Game Dev

Найти точку, гарантированно принадлежащую многоугольнику

Добавлен
Сап, как найти точку, которая гарантированно принадлежит многоугольнику? Нужен простой способ без дальнейших перепроверок.
Пробовал юзать среднее число от внутреннего угла <180 , однако оказывается это не всегда верно (если одна нога длинная, то там в общем все не ок). В общем-то теперь дополнительно проверяю пересечение еще.
Естественно такой способ полная хрень.
Возможно, вы знаете какую-нибудь простую внятную формулу, находящую какую-то стопудово внутреннюю точку (играющую определенную роль мб в каком-то другом алгоритме). В общем любое решение, любая точка гарантировано внутри прямоугольника, которую можно найти быстро без проверки линий на пересечение. Ваши варианты?
точки на гранях в оборот не берем
6 июл 2015
  • Размещен: 06.07.2015 08:11:13
  • Создан: 06.07.2015 08:11:13
  • Обновлен: 06.07.2015 08:11:13
7 497
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
27
9 лет назад
0
хм, надо подумать могу ли я их заранее "узнать". Хороший совет.
Mihahail, хорошее решение. Если не получится заранее определить многоугольник (там, где я их формировал) то наверное так и сделаю.
0
20
9 лет назад
0
Хм, если брать задачу в комментах, а не сабжевую, то я ничего не буду рекомендовать, ибо не знаю, что именно разрабатывается. Полную бы задачу услышать, но уповаю на то, что иного выхода, кроме того, что в посте - нет :)
Этот комментарий удален
0
29
9 лет назад
0
Ну что в итоге то? Решение нашли?
0
27
9 лет назад
0
alexprey, Пока нет. Отложил задачу до понедельника.
Mihahail:
Хотя мб попробовать брать треугольник АPQ, где P и Q - точки на смежных А рёбрах, лежащие очень близко к А..? Ну, чтобы не тратиться на поиск ближайшей точки.
Такой способ не подходит, ибо угол, слишком близко к A может все попортить
На другой случай который ты предложил я таки смог найти контрпример где опять же нужно проверять пересечения.
Причем соль в том что такую картину можно сделать даже на выпуклом углу (от смежной точки можно создать пересечение отделяющее от ближайшей D)
Загруженные файлы
0
20
9 лет назад
Отредактирован Mihahail
0
Хм, ты прав.
Хотя, похоже, что это возможно лишь в тупом угле. Тогда можно просто искать острый.. Хотя не факт, что он есть:)
Можно попробовать проверять каждую грань на пересечение с отрезком AD(в моих обозначениях), но это вроде как долго. Ещё можно искать не крайнюю точку, а крайнее ребро, но пока это у меня поток мысли, без идей.
Узнал, что проверить принадлежность точки невыпуклому многоугольнику можно за линейное(aka полиноминальное) время. habrahabr.ru/post/161237
А вики утверждает следующее:
Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N-угольника эта задача может быть решена за время O(log2 N) с использованием O(N) памяти и O(N log N) времени на предобработку.
Но хз, можно ли вычислить нужную точку за полиноминальное время.
Можно попробовать придумать стохастический алгоритм, если проверка реально быстра.
Если придумается решение, то нужно обязательно на хабр запостить.
0
27
9 лет назад
0
Mihahail:
Если придумается решение, то нужно обязательно на хабр запостить.
Зачем? :)
0
20
9 лет назад
Отредактирован Mihahail
0
Ну, там вроде любят такое.. Решение и оптимизация сложной алгоритмической задачи, как-никак :)
На самом деле, можно было не страдать фигней и пулять произвольным лучом в этот многоугольник, считать его число пересечений с гранями, и брать любую точку меджду первым и вторым пересечением.
Но я так понимаю, классическое решение недостаточно быстрое?
0
27
9 лет назад
0
Mihahail, вот именно. Оно требует перебрать все пересечения на предмет наименьших, а там же еще и вычисление точки выходит, что не быстро. Даже по триангуляции быстрее перебрать, там хотя бы просто факт непересечения нужен, а не точка.
2
24
9 лет назад
2
Devion,
  1. можешь подробнее объяснить чем принципиально не подходят точки на гранях и вершины?
  2. какая вычислительная сложность сейчас у твоего алгоритма? не факт, что найдется идеальное решение, а вот более дешевое можно и поискать, но для этого нужен критерий сравнения.
0
20
9 лет назад
Отредактирован Mihahail
0
Уповая на то, что арифметика(+, -, *) быстрая, буду считать только if'ы/сравнение и деление, как самые затратные операции.
Поиск грани, пересекающей (пусть вертикальную)прямую, имеет линейную сложность(2*N проверок). Координаты точки пересечения, если известно, что оно есть - определяются сразу по формуле, тут 1 деление(т.к. прямая вертикальная).
После каждого пересечения для поиска минимакса делаются ещё от одной до двух проверок. Пересечений не более N-1, значит, не более 2*(N-1) дополнительных проверок.
Итого около 4*N операций.
Куда ещё лучше-то?
И плюсую prog у, особенно за второй вопрос.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.