?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
проверка пересечения: сведение к меньшим размерностям
nyaload
_winnie
Для объектов A и B со связной границей утверждение "А пересекается с B" эквивалентно "границы А и B пересекаются || A вложен в B || B вложен в А"

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

А и B должны быть со связной границей ( это ограничение самое важное при прикладном применении ). А так же замкнутыми, непустыми, и должны существовать точки вне A и B ( A|B не должно покрывать целиком всё пространство ).

Для полосок на торе, шайб-колец в 2d, отрезков на одномерной прямой, утверждение не сработает, так как их граница не связна.
Условие что есть точки вне A и B тоже необходимо, иначе можно привести антипример A={(x,y)|x2+y2 <= 2}, B={(x,y)|x2+y2 >= 1} или арбуз упакованный в два презерватива.

Кстати, теорему придумал сам, но наверное тоже баян, так как учебников по топологии не читал.


  • 1
Для (замкнутых, ограниченных и связных) объектов

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

Несвязные объекты - это несколько штук связных, можно попарно всё проверить, тут всё просто :)

Гораздо хуже когда поверхности с дырками, на это даже ассерт не поставишь, так как это часто вполне осмысленно.


Несвязные объекты - это несколько штук связных, можно попарно всё проверить, тут всё просто :)

Ну конечно, просто нужно о такой возможности помнить. Если объект - какая-то разновидность polygon soup, то его связность еще поди проверь, тем более дели его на связные компоненты.

Твой принцип можно отважно закодить для многоугольников/гранников, обложить тестами даже, а данную коварную подставу так и не заметить.

Кстати, довёл условия утверждения до ума.
Не связность объекта, а связность границы.
Не ограниченность, а наличие точек вне А и B.

>Если объект - какая-то разновидность polygon soup, то его связность еще поди проверь, тем более дели его на связные компоненты.
итерация по всем ребрам, disjoint set треугольников?

Edited at 2010-10-28 09:34 pm (UTC)

>А и B должны быть со связной границей (это ограничение самое важное...)
>Для полоски на торе... не сработает, так как граница не связна.

А для полоски на ленте Мёбиуса? (Граница связна!) ;)

>Условие ограниченности объектов тоже необходимо, иначе можно привести антипример A={(x,y)|x2+y2 <= 2}, B={(x,y)|x2+y2 >= 1}

А если то же самое на сфере? Предположим, A — часть планеты южнее 50° северной широты, а B — симметричная часть.

Edited at 2010-10-28 05:51 pm (UTC)

Я ещё не доказал своё утверждение.

Самая трудная часть - это доказать что если два объекта пересекаются и не вложены друг в друга, то у них пересекаются границы.

Примерная путь к доказательству у меня такой: возьмём точку X на (границе A)-B.
Возмём точку Y на ((границе A) & B). Соединим X и Y, это возможно так как граница A - связанная. Так как один конец в A, а другой в B, то путь из X в Y где-то проткнёт границу B, это и будет точка пересечения.



Вот в моментах "возьмём точку на границе вне B и внутри B" у меня проблема, на этом я построил все антипримеры.

Условие ограниченности довольно "хромое", без него я могу приводить антипримеры, но оно не сработает в пространстве который открытый шар или в твоём случае со сферой.

Я пытаюсь как сформулировать "ограниченность" правильно, но не выходит %) Либо как правильно выкинуть сферы и открытые шары, либо как сформулировать что бы работало и на них.


Edited at 2010-10-28 06:17 pm (UTC)

Во, кажется придумал.

Надо сделать условие "А и B не покрывают целиком всё пространство".

Тогда можно взять точку X' из A/B, соединить путём с X'' в дополнениии (A|B). Пересечение Y с границей A пути из А до дополнения A|B будет вне B.

Затем взять взять точку Y' в A&B, соединить с точкой Y'' в B/A. Пересечение X с границей A будет внутри B.

Путь из X в Y по границе A где-то проткнёт границу B.





Edited at 2010-10-28 06:36 pm (UTC)

Хммм, что-то неясно почему обязательно есть путь из X' в X'' который протыкает именно (границу A)/B, а не просто (границу A).

А, надо разобрать два случая.
Случай путь из X'' в X' протыкает границу A/B(уже разобрал), и случай когда путь из X'' в X' протыкает границу B/A (точка X). Тогда пусть путь из X' в X где-то в точке Y протыкает границу A (т.к. X' в A, X вне A), и тут пригождается связность границы B. Путь из X в Y по границе B где-то протыкает границу A.

Про мебиус не понял, во-первых не могу представить себе сразу два множества на листе мебиуса, во-вторых при условии которое я придумал в предыдущем коменте вроде всё в порядке.

Можно кстати ещё упростить, убрав условие про то что A и B не должны покрывать множество целиком, оставив только замкнутость и связность границы. И добавив что A и B не пустые.

(АB ≠ Ø) <=> (A' ⊆ B || B' ⊆ A || A'B' ≠ Ø) & A≠Ø & B≠Ø
где A', B' - границы A, B.
Изначально было
(АB ≠ Ø) <=> (A ⊆ B || B ⊆ A || A'B' ≠ Ø) плюс добавленное через некоторое время условие что A∪B ≠ Ω


Edited at 2010-10-28 09:57 pm (UTC)

>Можно кстати ещё упростить, убрав условие про то что A и B не должны покрывать множество целиком, оставив только замкнутость и связность границы. И добавив что A и B не пустые.

Ну и как это согласуется с двумя презервативами, натянутыми на арбуз? Границы замкнуты, связны, ограничены; множества непусты, ограничены.

Алсо, граница множества A часто обозначается так: ∂A. Ну и чтоб два раза не вставать, накопипащу-ка я сюда из charmap'а ещё полезных в дискуссии символов: ∧ ∨ ∩ ∪ ⇔

А вообще, в поисках контрпримеров и узких можно ещё присмотреться к двум направлениям:
1) Всякие хитрые поверхности типа бутылки Клейна (при разрезании которой, в частности, может получиться лист Мёбиуса).
2) Фракталы. Там доказательства типа «будем двигаться вдоль границы в поисках точки перевала» прокатывают со скрипом.

>Ну и как это согласуется с двумя презервативами, натянутыми на арбуз? Границы замкнуты, связны, ограничены; множества непусты, ограничены.
Я заменил (A ⊆ B) на (A' ⊆ B). Границы-резинки вложены :)

Вторую формулировка выводится из первой (доказанной). По первой, если два множества пересекаются, то либо одно множество внутри другого, либо пересекаются границы. Если я убираю требование "A∪B ≠ Ω", то из пересечения следует либо точно такое же свойство пересечения границ, либо что A ⊆ B и следовательно ∂A ⊆ B, либо что B ⊆ A и ∂B ⊆ A.
Либо новая возможность что A∪B = Ω, значит Ω-A вложено в B, значит ∂(Ω-A) вложена в B, значит и ∂A=∂(Ω-A) вложена в B.
Стрелочка следствия обратную сторону тривиальна.
Ничего нового содержательного топологичного, просто игра на уровне A+(Ω-A) = Ω

> 1) Всякие хитрые поверхности типа бутылки Клейна
Вроде бы пофиг, я не использую то что может сломаться на бутылке клейна.
> 2) Фракталы. Там доказательства типа «будем двигаться вдоль границы в поисках точки перевала» прокатывают со скрипом.
Связность я понимаю как то, что есть непрерывное отображение отрезка в путь (возможно бесконечной длины, для фракталов). Если фракт настолько хитрый, что у него нет связной границы, то хрен с ним. Для снежинки Коха тривиально доказать что граница связна. Точка разрыва бинарной функции внутри-невнутри будет как раз точкой протыкания границы.

Edited at 2010-10-28 11:19 pm (UTC)

  • 1