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

[brigval]

Есть две произвольные плоские фигуры, контур каждой из которых состоит из прямых отрезков и дуг. Известны все необходимые координаты концов отрезков и дуг и параметры дуг.
Задача. Как узнать, пересекаются ли эти две фигуры. Есть ли хотя бы одна общая точка. Нужен только факт пересечния/непересечения.
Буду благодарен за любую полезную информацию или ссылку.

[FireFenix]

Для простых отрезков - форум или интернет
Для дуг - наверное что-то такое тоже есть или же нада выводить

[Qwertiy]

Пересечение фигур не равносильно пересечению их границ. Есть ещё случай вложенности. Причём для невыпуклых фигур проверка вложенности заметно усложняется.

Предлагаю каждую фигуру разделить на множество выпуклых фигур, а для которых потом попарно проверить пересечение.

[Хакер]

Пересечение фигур не равносильно пересечению их границ.

Пример не пересекающихся фигур с пересекающимися границами приведи.

[Qwertiy]

Пример не пересекающихся фигур с пересекающимися границами приведи.

Я не говорил, что такое возможно. Я сказал "не равносильно", уточнив при этом, что есть случаи, когда границы не пересекаются, а фигуры пересекаются.
Пересечение границ в любом случае даёт пересечение фигур, т. к. граница - это часть фигуры (незамкнутые фигуры в тут не рассматриваются).

[Хакер]

что есть случаи, когда границы не пересекаются, а фигуры пересекаются.

Ну тогда пример вот этого.

[Qwertiy]

что есть случаи, когда границы не пересекаются, а фигуры пересекаются.

Ну тогда пример вот этого.

Вот

Inside.png (9.14 Кб) Просмотров: 10756

[iGrok]

И где там "пересекающиеся" фигуры?
Одна в другой - да. Но они же не пересекаются. ,-)

[Хакер]

Да нет, с точки зрения математики это пересекающиеся фигуры, потому что есть непустое множество точек, принадлежащее обеим фигурам.

Алгоритм архипростой:
(Обозначим фигуры за A и B)

• Проверяем пересечение контура A с контуром B. Если контуры пересекаются, то и фигуры пересекаются. Ответ дан.
• Если контуры не пересекаются, берём произвольные точки X и Y, такие, что и , и строим произвольные лучи, исходящие из этих точек. Считаем количество пересечений контура B с X-лучём и контура A с Y-лучём. Если хоть в одном случае получилось нечётное число, значит фигуры пересекаются.

Лучше проще всего брать горизонтальные или вертикальные.

[Хакер]

Кому-то будет подарок:

intersect_demo_nointersect.png (8.92 Кб) Просмотров: 10730

intersect_demo_partial.png (11.04 Кб) Просмотров: 10730

Смотреть надо модуль modAlgo, там сам алгоритм — определение пересечения, всё остальное — обвес для возможности рисовать фигуры в окне. Алгоритм устойчив к самопересекающимся многоугольникам.

[brigval]

Кому-то будет подарок:

intersect_demo_nointersect.png

intersect_demo_partial.png

intersect_demo_ainb.png

intersect_demo_bina.png

Смотреть надо модуль modAlgo, там сам алгоритм — определение пересечения, всё остальное — обвес для возможности рисовать фигуры в окне. Алгоритм устойчив к самопересекающимся многоугольникам.

Большое спасибо. К сожалению, там не учтены границы, включающие дуги. Но все-равно очень интересно. Поизучаю.

[Хакер]

Дуги чем представлены?
Как я должен учитывать это, если ты ничего не сказал? Это кривые Безье? Если да, то какой степени? Или может быть это NURBS-кривые? Или дуги, являющиеся дугами окружности с заданным радиусом и центром?

В любом случае это решается просто тем, что код, определяющий пересечений граней меняется на код, определяющий пересечение кривых.

[Proxy]

В любом случае это решается просто тем, что код, определяющий пересечений граней меняется на код, определяющий пересечение кривых.

Или представить дуги как ломаные перед проверкой пересечений.

[Хакер]

Или представить дуги как ломаные перед проверкой пересечений.

Это ужасный путь. Он не только ошибко-опасный (неточный), но ещё и очень малопроизводительный, потому что будет много отрезков, и все возможные пары нужно проверить на пересечение.

[ger_kar]

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

Это кривые Безье? Если да, то какой степени? Или может быть это NURBS-кривые? Или дуги, являющиеся дугами окружности с заданным радиусом и центром?

Из этого я например понял только про окружности с радиусом и центром и про дуги им соответствующие. Нет я конечно знаю, что такое кривая Безье, точнее как она выглядит на практике, потому как она часто применяется в графических редакторах, в том эе Photoshop и Corel , но какими она обладает математическими свойствами даже не представляю, а про NURBS-кривые, я вообще первый раз слышу .

[brigval]

Дуги чем представлены?
Как я должен учитывать это, если ты ничего не сказал? Это кривые Безье?

Вообще-то, в первом посте я написал про дуги. Обычные дуги (часть окружности)

В любом случае это решается просто тем, что код, определяющий пересечений граней меняется на код, определяющий пересечение кривых.

К сожалению, не удется уделить побольше времени на эту задачу. Могу только постепенно ею заниматься. В принципе, идея понятна. Думаю, что с реализацией разберусь. Большое спасибо за информацию.

[Proxy]

Это ужасный путь. Он не только ошибко-опасный (неточный), но ещё и очень малопроизводительный, потому что будет много отрезков, и все возможные пары нужно проверить на пересечение.

Пригодность зависит от цели, на него возложенные...

[Хакер]

Если ты разобьёшь две кривых на 50 частей каждую, тебе потребуется сделать 50×50 проверок на пересечение отрезков. А если не разобьёшь — один раз решить не очень сложную систему уравнений.

[Proxy]

Если ты разобьёшь две кривых на 50 частей каждую, тебе потребуется сделать 50×50 проверок на пересечение отрезков. А если не разобьёшь — один раз решить не очень сложную систему уравнений.

А если дуга - исключительная ситуация в модели и её достаточно разбить всего на 3-4 отрезка (смотря какая ситуация), то не к чему нагружать collision detection избыточным кодом. Вспомни тот же GTA 3, там каждый автомобиль когда-то для проверки пересечения представлялся как 30-40 треугольников. И хватало.

[Хакер]

А если дуга - исключительная ситуация в модели и её достаточно разбить всего на 3-4 отрезка (смотря какая ситуация)

Даже если ты разобьёшь на 3—4. Будет 9—16 раз решаться СЛАУ. А так один раз уравнение. С дугами окружности вообще простота.

[Proxy]

С дугами окружности вообще простота.

Вообще кривая Безье гораздо универсальнее.

Будет 9—16 раз решаться СЛАУ.

Если код при этом будет на кучу строк короче, то выбор очевиден. Это если рассматривать отдельно пересечения отрезков, пересечения отрезков с дугами и пересечение дуг, в противном случае о производительности и мечтать не придётся.

[brigval]

Это ужасный путь. Он не только ошибко-опасный (неточный), но ещё и очень малопроизводительный, потому что будет много отрезков, и все возможные пары нужно проверить на пересечение.

Пригодность зависит от цели, на него возложенные...

В данном случае, извините, Хакер прав. Если угол одной фигуры попадет на часть дуги, ограниченной апроксимирующей хордой, пересечение не будет найдено. Сколь бы малой хорда не была.
Просто, в данном случае нужно узнать факт реального пересечения/непресечения.
Да и фигур "одна" может быть несколько десятков, а фигур "вторая" может быть до нескольких десятков тысяч.

[Хакер]

Вообще кривая Безье гораздо универсальнее.

Нет, ими, например, нельзя «выразить» те же дуги окружности

[Proxy]

Нет, ими, например, нельзя «выразить» те же дуги окружности

Т.е. нельзя? Окружность представляется как фигура, состоящая из 2-х (или при желании большего числа) кривых Безье, каждая из которых является дугой.

[Хакер]

Напиши координаты «контрольных точек» Безье-сплайна для окружности радиусом R в центре с (0; 0).

[Proxy]

опорные:
(-R,0)
(R,0)
Направляющие:
(-R,R)
(R,R)
ещё пара направляющих:
(-R,-R)
(R,-R)

[Хакер]

Вот я когда увидел твои опорные точки, устно определил, что вершина такого кубического Безье-сплайна пройдёт в от центра на окружности.

Предлагаю тебе в уме посчитать, какие координаты будет иметь точка сплайна с параметром t = 0.5, глядя вот на эту анимацию:




P.S. Ну и напоследок: представить дугу окружности с помощью сплайна Безье невозможно, это математически достоверный факт.

[Proxy]

Вот я когда увидел твои опорные точки, устно определил, что вершина такого кубического Безье-сплайна пройдёт в Математическая формула: \frac{3}{4}R от центра на окружности.

неправильно я написал...

опорные:
(-R;0)
(R;0)
Направляющие:
(-R; 1,(3)4 * R)
(R; 1,(3)4 * R)
ещё пара направляющих:
(-R; -1,(3)4 * R)
(R; -1,(3)4 * R)

P.S. Ну и напоследок: представить дугу окружности с помощью сплайна Безье невозможно, это математически достоверный факт.

Увеличиваем число "контрольных точек" — сумма квадратов разности с Sin; Cos падает. С определённым числом точек можно достигнуть необходимой точности. Сумма квадратов разности асимптотически приближается к абсцисс с увеличением числа точек (график суммы квадратов разности от числа точек).

[Debugger]

Это аппроксимация. Можно любую кривую аппроксимировать, например, ломаной. А вот выразить - нельзя.

[Proxy]

Это аппроксимация. Можно любую кривую аппроксимировать, например, ломаной. А вот выразить - нельзя.

Аппроксимации достаточно почти для любой задачи. И способов очень много, можно хоть до разложения в ряд Тейлора дойти.
Ну а насчёт "выразить" я действительно погорячился.