Алгоритм пересечения фигурв пространстве

Что за фигуры? Выпуклые?

Если выпуклые, то можешь заюзать Nef polyhedra из CGAL http://doc.cgal.org/latest/Nef_3/index.html#Chapter_3D_Boolean_Operations_on_...

А как заданны фигуры?

Если фигуры пересекаются, то и их проекции пересекаются. Обратное НЕ ВЕРНО! Проекции могу пересекаться, а фигуры - нет.

Так а он написал же не одна проекция, а

если все три проекции XY XZ YZ пересекаются, то и фигуры пересекаются

Вроде логично

только выпуклые, ок, добавил на почитать

ну точками, к примеру

Definition: A point set K⊆Rd is called a cone with apex 0, if K=R+K (i.e., ∀p∈K,∀λ>0:λp∈K) and it is called a cone with apex x, x∈Rd, if K=x+R+(K−x). A cone K is called a pyramid if K is a polyhedron.

не, ну это слишком сложно:)

Хотя та же логика подсказывает, что проекциями в ZX ZY XY не обойтись.

Вроде логично

нет, не логично. Нет такого критерия.

Как именно точками? Если это многоугольник на плоскости, то даны вершины ломаной его ограничивающей? Потому что алгоритм как раз и зависит от того, как с-но фигуры заданы.

Возьмём треугольник

(2, 0, 0) - (0, 2, 0) - (0, 0, 2)

(2, 0, 1) - (0, 2, 1) - (0, 0, 3)

A1 * x + B1 * y + C1 * z = D1
A2 * y + B2 * y + C2 * z = D2

SAT, Сумма(разность) Минковского, GJK

наверное так, ну в том плане что важна их последовательность? но разве для выпуклой фигуры важен порядок? в общем, если треугольник, то даны точки A(x,y,z), B(x,y,z), C(x, y, z)

У них там математическая строгость по всем фронтам, смотри исходники станет понятней.

Нет, не логично. Два треугольника:

• (0, 0, 1), (0, 1, 0), (1, 0, 0)
• (0, 0, 2), (0, 2, 0), (2, 0, 0)

Не пересекаются, но проекции первого находятся внутри проекций второго.

Если фигуры плоские, то необходимо и достаточно, что бы отрезок (ребро) одной фигуры имел хотя бы одну общую точку с другой фигурой. Проверять надо как вхождение фигуры 1 в 2, так и 2 в 1. Задача сводится к проверке пересечения отрезка и треугольника в пр-ве - любой многоугольник может быть представлен как совокупность треугольников, выпуклый многоугольник представляется так тривиальным образом.

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

1) найти линию пересечения плоскостей, 2) найти пересечения этой линии фигурами. 3) определить имеют ли эти пересечения общие точки

п1 - вспомни тригонометрию :) п2 - или триангулировать фигуры, или решать аналитически (если фигуры заданы функциями) п3 - совсем просто.

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

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

не понял, а зачем проверять пересечение рёбер фигуры 2 в фигуре 1?

Звучит просто и понятно, без всяких заумных разностей Минковского, да и по производительности вполне сносно. Если 1 ребро пересекается, то значит 1 общая точка, если 2 то фигуры пересекаются отрезком AB, где А и B - точки пересечения рёбер. Правильно я понял?

Затем, что ребра фигуры 1 могу не пересекать фигуру 2, а ребра фигуры 2 при этом будут пересекать фигуру 1.

Вариант с пересечением двух плоскостей и потом анализа пересечения с прямой м.б. и попроще.

яростно плюсую

Твой метод поиска пересечения мне нравится даже больше.

когда учился в универе писанул https://code.google.com/p/polypuch/ код там нормальный его и посмотри. структура проекта какашка конечно - с нее не ржать.

смотри

• svn/ trunk/ src/ libs/ Polygon/ Simple/ simple_have.cpp
• svn/ trunk/ src/ libs/ Polygon/ General/ general_have.cpp
• svn/ trunk/ src/ libs/ Polygon/ Convex/ convex_jarvis.cpp
• svn/ trunk/ src/ libs/ Polygon/ Convex/ convex_hoare.cpp
• svn/ trunk/ src/ libs/ Polygon/ Convex/ convex_have.cpp
• svn/ trunk/ src/ libs/ Polygon/ Convex/ convex_graham.cpp

если хочешь по серьезному подойти к этому вопросу : "Ф. Препарата, М. Шеймос - Вычислительная Геометрия" полностью задрачивай

ухты. эти чето новенькое!

найти пересечения этой линии фигурами.

здесь совсем не понятно. Предположим у меня есть уравнение прямой(образованной пересечением плоскостей) в виде (x-x1)/l = (y-y1)/m = (z-z1)/n, где (x1,y1,z1) - точка прямой. (l,m,n) - направляющий вектор. Их я знаю как найти. Что дальше?

плоскости пересекаются по прямой и общие точки могут быть только на этой прямой.

имея уравнение прямой, как определить общие точки этих фигур.

Теперь ищем отрезки - места пересечения фигур с этой линией (двухмерная задача).
двухмерная задача

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

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

имея уравнение прямой, как определить общие точки этих фигур

обходишь фигуру по кругу. в момент, когда ребро пересекает прямую, регистрируешь начало/конец отрезка. например, когда векторное произведение ( направляющего вектора прямой на радиус-вектор очередной вершины ) меняет направление на противоположное

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

Что-то не понятно как это работает.

текстом не напишешь, рисовать надо. гугли вычислительную геометрию (если термин не путаю).

У тебя от прямой остался только направляющий вектор? Но ведь при параллельном переносе в нормальной плоскости он не меняется в отличие от точки пересечения. Что-то тут не так.

да, верно. уточняю:

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

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

Пересечение любых из трёх проекций не гарантирует пересечение самих фигур