Разминка для мозгов: пересечение параллелепидедов в пространстве

Разминка для мозгов: пересечение параллелепидедов в пространстве

Предлагаю для тренировки следующий вариант разминки для мозгов:

Есть два прямоугольных параллелепипеда, для каждого из которых известны координаты четырех вершин (x, y, z).

Нужно проверить, пересекаются ли эти параллелепипеды в пространстве. Можно использовать любые возможности стандартной библиотеки, в т. ч. из C++ 11.

Объект параллелепипеда рекомендуется описывать классом. Например:

struct point {
    int x;
    int y;
    int z;
};

class box
{
public:
    box(point p1, point p2, point p3, point p4) { /* ... */ }
    bool intersects(const box &box2) { /* ... */ } // проверка на пересечение
};

Может я чего-то не понимаю, но мне кажется, что для задания параллелепипеда достаточно двух точек. И вся проверка заключается в том, чтобы проверить пересечение хотя бы в одной из плоскостей xOy, xOz, yOz? Так?

Нет, нужно как минимум 3 точки, чтобы однозначно определить положение параллелепипеда.
Проверить нужно, что один параллелепипед пересекает другой :-)

Интересно... В первом сообщении selevit предполагал использовать четыре точки для задания параллелепипеда. Потом согласился на то, что хватит и трёх.

Во-первых, давайте уточним: параллелепипед прямоугольный или произвольный?

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

В случае, когда ориентация прямоугольного параллелепипеда относительно осей произвольна, то он однозначно определяется всё-таки по четырём точкам: три точки задают плоскость одной из граней, а четвёртая — задаёт плоскость, параллельную первой и проходящая через эту точку. Причём если эти известные точки являются именно вершинами, то на них налагаются дополнительные условия.

Если же параллелепипед не прямоугольный, то всё будет ещё сложнее.

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

Так что не всё так однозначно. Даже на уровне условий задачи.

PS. Боюсь, что задачи из области аналитической геометрии школьникам будут просто не по зубам ((

Нет, нужно как минимум 3 точки

Почему? (Да, да мне лень гуглить)

Проверить нужно, что один параллелепипед пересекает другой

Ну да, я вроде и написал:

проверка заключается в том, чтобы проверить пересечение хотя бы в одной из плоскостей xOy, xOz, yOz?

PS. Боюсь, что задачи из области аналитической геометрии школьникам будут просто не по зубам ((

Почему? Тут же вроде не очень сложно...

Имелся ввиду прямоугольный параллелепипед. В пространстве он может находиться в произвольном положении.

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

По-моему, очевидно, что да. Разве это какой-то частный случай пересечения?
Да, по поводу трех точек, я погорячился, отвечая в попыхах.

Боюсь, что задачи из области аналитической геометрии школьникам будут просто не по зубам.

Эту задачу можно решить, руководствуясь здравым смыслом (без знания формализованного решения). Основная масса людей на этом сайте студенты, а не школьники, поэтому не вижу смысла подстраиваться под школьную программу ;)

Другое дело, если бы речь шла о пересечении объемых эллипсов или граненых сфер. Но это уже совсем другая история.

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

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

Пожалуйста, оформляйте исходный код в соответствии с правилами разметки. Для того, чтобы вставить код в комментарий, скопируйте его в текстовое поле ниже, после чего выделите то, что скопировали и нажмите кнопку «код» в панели инструментов. Иначе ваш код может принять нечитаемый вид.

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Предпросмотр сообщения

Ваше сообщение пусто.