Devion
Game Dev

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

Добавлен
Сап, как найти точку, которая гарантированно принадлежит многоугольнику? Нужен простой способ без дальнейших перепроверок.
Пробовал юзать среднее число от внутреннего угла <180 , однако оказывается это не всегда верно (если одна нога длинная, то там в общем все не ок). В общем-то теперь дополнительно проверяю пересечение еще.
Естественно такой способ полная хрень.
Возможно, вы знаете какую-нибудь простую внятную формулу, находящую какую-то стопудово внутреннюю точку (играющую определенную роль мб в каком-то другом алгоритме). В общем любое решение, любая точка гарантировано внутри прямоугольника, которую можно найти быстро без проверки линий на пересечение. Ваши варианты?
точки на гранях в оборот не берем
6 июл 2015
7 551
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
Показать
20
0
Показать
Уповая на то, что арифметика(+, -, *) быстрая, буду считать только if'ы/сравнение и деление, как самые затратные операции.
Поиск грани, пересекающей (пусть вертикальную)прямую, имеет линейную сложность(2*N проверок). Координаты точки пересечения, если известно, что оно есть - определяются сразу по формуле, тут 1 деление(т.к. прямая вертикальная).
После каждого пересечения для поиска минимакса делаются ещё от одной до двух проверок. Пересечений не более N-1, значит, не более 2*(N-1) дополнительных проверок.
Итого около 4*N операций.
Куда ещё лучше-то?
И плюсую prog у, особенно за второй вопрос.
0
Показать
27
0
Показать
от N*3 до (N^2)*3 при разных случаях
На самом деле я еще вчера нашел решение как подошел снова к задачке, и оно оказалось простое.
Дело в том что действительно подходят точки на гранях. Однако не все.
Почему не подходит просто грань - я затем, как писал выше юзаю проверку на принадлежность этой фигуры друому многоугольнику. Такая проверка строится проведением линии и пересчитыванием граней (например четное, нечетное). Поэтому некоторые грани будут считаться точкой вне препятствия, а некоторые - внутри.
Например, если алгоритм проверки проверяет стороны от точки вправо - то только правые ребра будут детектить принадлежность препятствию, а левые наоборот. (точнее не правые/левые, а "слева направо" относительно горизонтального луча, это немного другое). Эта неоднозначность в выборе направления проверки и заставляла искать решение получше.
Однако в сути при обходе справа можно взять правую грань, причем сделать это можно достаточно быстро, если все многоугольники развернуты по часовой стрелке - это будет первая сторона, у которой p1.y > p2.y. Даже если не развернуты то ориентацию тоже можно быстро просчитать через сумму углов многоугольника.
А вообще нет, я не прав. Ребро таки нельзя. Почему? Да потому что флоат, потому что погрешность - и пересечение существует лишь иногда, нестабильно. Таки нужно искать точку внутри :С
Загруженные файлы
0
Показать
20
0
Показать
Давай ты задачу целиком изложишь, а мы тут подумаем на досуге.
Или коммерческая тайна?
Я из всех твоих комментов что-то не смог восстановить =(
0
Показать
24
0
Показать
В принципе, можно попробовать построить диаграмму Вороного или применить триангуляцию Делоне и поискать в них интересные точки. Причем для первого варианта может оказаться достаточным сделать всего несколько итераций чтобы выйти на нужную точку, не завершая строительство диаграммы.
0
Показать
38
0
Показать
У меня вот вопрос, зачем? В какой библиотеке, 2016 год на носу, не хватает такой функции? Или велосипед? Это всё давно на уровне хардвейра решается, пользуйтесь dx и туда не надо лезть =)
Если что гуглить рейтрейсинг
0
Показать
1
0
Показать
Спасибо за совет про рейтрейсинг)
Чтобы оставить комментарий, пожалуйста, войдите на сайт.