Devion
Game Dev

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

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

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
1
Показать
27
1
Показать
alexprey, я сейчас ее и юзаю (точнее ее часть). Это очень не дешево для поиска простой точки. Слишком жирно имхо.
Да и я написал что пробовал искать среднее (видимо некорректно описал). Это не работает, так как многоугольник самый что ни на есть произвольный.
1
Показать
29
1
Показать
Devion, думаю стоит описать как часто меняются точки и их координаты
1
Показать
27
1
Показать
alexprey, очень часто. Я потому и прошу максимально дешевое решение для гарантированного поиска точки. Наверняка ведь что-то такое есть. Может что-то минимаксное.
1
Показать
29
1
Показать
Devion, часто строятся произвольные многоугольники и нужно найти точку вхождения... хмм как то странно. А мб правило какое нибудь простое для построения? так проще будет сориентироваться
хммм, пробовал находить проекцию?
есть ли вероятность перекрученного многоугольника?
ох, короче засада(
1
Показать
27
1
Показать
Ну окей, объясню задачу
Есть многоугольник, полученный как часть взаимодействия двух других многоугольников.
Нужно найти, к каким многоугольникам причастен текущий и для этого я ищу внутреннюю точку (так как грани сами часто взаимодействуют и с тем и с другим и это не вариант). Найти принадлежность точки внутреннего многоугольника к внешнему многоугольнику достаточное условие и к тому же довольно простое.
alexprey:
есть ли вероятность перекрученного многоугольника?
есть, но перекрученный многоугольник я деформирую чуть раньше (так, чтобы отсеклась часть, наложенная на самого себя). Если же перекручивание порождает несколько фигур, то я разбиваю многоугольник на них. То есть в итоге мы так или иначе работаем с обычным многоугольником.
Загруженные файлы
1
Показать
9
1
Показать
А как ты будешь проверять это условие, взяв точку внутри наугад?
0
Показать
27
0
Показать
GeneralElConsul, ну просто
  1. Берем любую точку внутреннего многоугольника
  2. Находим, принадлежит ли эта точка указанному внешнему многоугольнику методом трассировки луча
  3. Если точка принадлежит указанному внешнему многоугольнику, значит внутренний многоугольник находится в этом внешнем.
3
Показать
20
3
Показать
Ой. Я, кажется, решил :)
Находим крайнюю точку(min|max координата), берем её соседние две. Имеем три точки, треугольник. Его центр масс - искомая точка.
0
Показать
27
0
Показать
Mihahail:
берем её соседние две
Вот тут не понял. Типа (min.x, max.y)?
0
Показать
20
0
Показать
Я фигню написал. Прошу прощения, прошу забыть :)
Точнее не фигню, эта идея выше - всего лишь часть правильного метода.
Devion, я имел ввиду две смежные точки. Есть крайняя вершина А, а есть её смежные вершины В и С.
Я думал центр масс треугольника АВС подойдёт.
Контрпример легко придумать: вогнутый четырёхугольник.
Модифицировал слегка.
Рассуждения вообще вот такие: единственный быстрый способ не оказаться за многоугольником - выбрать крайнюю точку А и две смежных с ней В и С. Тогда внутри полученного угла ищем ближайшую к А точку D(которая может совпадать с В и С), проводим окружность с центром в А и радиусом AD. Любая точка внутри полученного сектора круга(серая область на рисунке) - подходит.
Хотя мб попробовать брать треугольник АPQ, где P и Q - точки на смежных А рёбрах, лежащие очень близко к А..? Ну, чтобы не тратиться на поиск ближайшей точки.
Загруженные файлы
0
Показать
14
0
Показать
Devion, в чем проблема хранить породившие многоугольники?
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.