|
|
|
|
Канал Игры Мечты: «3D математика» |
|
|
|
DIMOSUS.X
 996 EGP
       
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
   |
|
Есть плоскость, в этой плоскости есть окружность. Так же есть объект состоящий из отрезков, образующих замкнутую фигуру. Как проверить что окружность находится внутри фигуры, если нет пересечений отрезков составляющих фигуру с окружностью?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Поторопился с вопросом, нужно было немного глубже копнуть гуглом.
Кому интересно: окружность будет находится внутри фигуры, если центр окружности находится внутри фигуры и нет пересечений окружности с фигурой.
Для проверки нахождения точки внутри фигуры нужно взять произвольный луч из этой точки и посчитать количество пересечений с фигурой. Если нечет — точка внутри фигуры.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
 979 EGP
   
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Для проверки нахождения точки внутри фигуры нужно взять произвольный луч из этой точки и посчитать количество пересечений с фигурой. Если нечет — точка внутри фигуры.
|
По этому вопросу есть куча способов, и у каждого из них есть свои недостатки.
В данном способе если луч пройдет ровно через вершину ломаной фигуры, то расчет даст четное число.
добавлено спустя 5 минут:
| DIMOSUS.X : |
|
Кому интересно: окружность будет находится внутри фигуры, если центр окружности находится внутри фигуры и нет пересечений окружности с фигурой.
|
В это условие попадает окружность, которая полностью захватывает фигуру, а центр её находится внутри фигуры.
добавлено спустя 19 минут:
Я бы определял способ из конкретной задачи. В большинстве игровых случаев был бы практичен следующий вариант.
A1 A2 .. An - вершины фигуры
O - центр окружности
R - радиус
1. Определяем нахождение центра окружности - внутри фигуры или нет. Делаем это методом площадей.
Если OA1A2 + OA2A3 + ... + OAn-1An + OAnA1 равно площади фигуры (которую можно посчитать методом трапеций 2S = sum( (Xi+Xi+1)*(Yi-Yi+1) ) ) - то точка внутри или на границе.
Примечание: если фигура впуклая, то будут отрицательные составляющие OAiAi+1.
Тут все считается быстро - O(N), отсутствие тяжелых операций (sqrt, sin, ..). И после этого прохода большинство окружностей отпадает.
2. Если центр внутри, то определяем расстояние от центра до ближайшей точки фигуры. Здесь у нас есть множество отрезков AiAi+1. Т.е. поиск расстояния от отрезка до точки и сравнение с R.
Тут O(N), один sqrt на отрезок.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (23:21 13-01-2011), всего редактировалось 8 раз(а) |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Прохождение луча через вершину крайне маловероятно. Но да же если такой случай будет иметь место на одном шаге, то вероятность повтора на следующем будет крайнемаловероятно в квадрате. В моем случае (физику считаю) этот не смертельно.
Нахождение фигуры внутри окружности у меня отсеивается отдельно 
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Прохождение луча через вершину крайне маловероятно.
|
Видимо искать в программе маловероятные баги доставляет особое удовольствие (;
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Тут в первую очередь встает вопрос производительности. Если использовать метод луча, то за одну секунду можно проверить 500 000 четырехугольников (эксперементальные данные).
Учитывая большое число отдельных физических миров, которые нужно постоянно обновлять, то приходится жертвовать.
Думаю не смертельно, если иногда колизия будет обнаружена на кадр позже.
Возможно для уменьшения вероятности добавлю второй луч - это всеже более производительный метод, хоть и не дающий абсолютной гарантии.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
Чем он более производителен?
добавлено спустя 5 минут:
И даже если так (в чем я очень сомневаюсь), то все равно смысла в некорректной программе не вижу. Некорректную программу можно ещё более быструю написать.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (09:20 13-01-2011), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Оснавные вычисления в методе луча проходят в проверке пересечения отрезков, а там алгоритм весьма простой и используются только * / + -
Если возможная некоректность не видна не вооруженным глазом, то какая разница? (кроме выйгрыша в производительности)
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Оснавные вычисления в методе луча проходят в проверке пересечения отрезков, а там алгоритм весьма простой и используются только * / + -
|
Для обработки вертикальных отрезков нужно ещё ветвеление.
Кстати, плюс один из частных случаев, не обрабатывающихся в методе луча - когда луч проходит ровно через одну из сторон-отрезков фигур. В результате получаем деление на ноль или бесконечное число отрезков.
В моем описанном алгоритме тоже самое - такие же операции + - * /.
Кстати, это:
| Minx : |
|
Тут O(N), один sqrt на отрезок.
|
необязательно. Оптимизируется сравнением квадратов расстояний, т.е. без корня.
Кстати, обращаю внимание, что до второго этапа алгоритм доходит не всегда. А когда доходит, то не всегда обрабатывает все N, - останов в случае выполнения первого условия непопадания в R.
| DIMOSUS.X : |
|
Если возможная некоректность не видна не вооруженным глазом, то какая разница? (кроме выйгрыша в производительности)
|
Есть или нет выйгрыш в производительности - вопрос ещё открытый.
Вопрос не в том, что некорректность не видна невооруженным глазом. А в том, что если такое произойдет, то программа поведет себя непредсказуемым образом. В результате это может быть незаметно, а может быть access violation с падением приложения.
В результате чтобы приложение работало корректно - нужно вводить дополнительные проверки (если прохождение через вершину, то... если прохождение через сторону, то ...), и даже в этом случае нет гарантии успешного завершения (результата работы алгоритма, у которого на выходе четкое true/false).
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (11:36 13-01-2011), всего редактировалось 2 раз(а) |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
На счет луча совподающего с сегментом фигуры - тут спорно.
Я проверяю пересечение отрезка и луча, итог функции булевый. Как тут может получится бесконечное число отрезков?
Будет как минимум два пересечения - с концами сегментов, соединенных с совпавшим.
У тебя есть твой алгоритм в коде? Если да, можешь испытать его на производительность?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Я проверяю пересечение отрезка и луча, итог функции булевый. Как тут может получится бесконечное число отрезков?
|
Луч проходит ровно сквозь отрезок (сторону фигуры). Число точек пересечения - бесконечное, в решении алгоритма - совпадение двух прямых.
| DIMOSUS.X : |
|
У тебя есть твой алгоритм в коде? Если да, можешь испытать его на производительность?
|
Уже же его описал. Там все просто. По элементам алгоритм кодил в свое время (площадь методом трапеций, принадлежность фигуре через площади, расстояние от точки до прямой).
А на производительность нужно тестить в конкретной реализации и для конкретных данных.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (12:46 13-01-2011), всего редактировалось 3 раз(а) |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
При поиске пересечений отрезка и луча я не ищу точки пересечения - только сам факт пересечения. Там у меня специальный упрощенный алгоритм(не мой), если интересно - выложу.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
При поиске пересечений отрезка и луча я не ищу точки пересечения - только сам факт пересечения.
|
Факт пересечения отрезка переводит решение задачи в неопределенность, т.к. после того, как отрезок закончился, луч может как проходить через фигуру, так и быть вне фигуры.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Не понял...
Я ведь поочередно проверяю все отрезки фигуры и считаю количество пересечений с одним и тем же лучем.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
Два пересечения с разными по четности ответами, а точка внутри.
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (14:59 13-01-2011), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Но если добавить второй луч, с углом поворота в 1 градус относительно первого и проверить пересечения и для него, то вероятность ошибки сократится до фантастически малой.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
Зачем создавать костыли, если есть варианты реализации без ошибок?
добавлено спустя 1 минуту:
И интересно, что будет делать алгоритм, если один луч скажет чет, а другой - нечет. Кому верить?
Третий луч запускать? (;
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (15:07 13-01-2011), всего редактировалось 2 раз(а) |
|
|
|
DIMOSUS.X
996 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
По тому что эти костылы будут быстрее полноценного, но неповоротливого алгоритма.
Если хоть один из них не чет, значит точка внутри.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
979 EGP
Рейтинг канала: 6(328)
Репутация: 136
Сообщения: 10528
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
Луч корректно используется тогда, когда например известно, что фигура - выпуклый многоугольник, у которого все отрезки имеют положительную длину и все они не лежат на одной прямой (нет подряд идущих друг за другом отрезков на одной прямой). В этом случае запускаем луч через центр любого из отрезков (с проверкой, чтобы отрезок не лежал на прямой луча, иначе брать следующий) и смотрим результат (1 пересечение - внутри, 2 или более - снаружи).
добавлено спустя 1 минуту:
| DIMOSUS.X : |
|
По тому что эти костылы будут быстрее полноценного, но неповоротливого алгоритма
|
Пока что никаких предпосылок того, что площади работают медленнее - нет.
Костыли пока что удобнее только в случае, если тебе лень реализовывать корректный вариант.
| DIMOSUS.X : |
|
Если хоть один из них не чет, значит точка внутри.
|
Это уже баг.
добавлено спустя 1 минуту:
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (15:16 13-01-2011), всего редактировалось 3 раз(а) |
|
|
|
Guest
 2075 EGP
        
Рейтинг канала: 5(167)
Репутация: 376
Сообщения: 27975
Откуда: Моск.
Зарегистрирован: 12.10.2004
|
|
| DIMOSUS.X : |
|
Но если добавить второй луч, с углом поворота в 1 градус относительно первого
|
Так и представляется почти гладкий меш, и две сотни лучей для проверки 
Исчезающе малая ошибка - это всё равно ошибка, полностью поддерживаю Минкса. Костыли в результате могут привести к более длительному вычислению, а ловить баг в них будет настолько же сложно, насколько будет мала вероятность ошибки...
_________________
Трещит земля как пустой орех
Как щепка трещит броня |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «3D математика» |
|
|
