Распознать кубик

[Igors]

Добрый день

Столкнулся с задачкой которая на первый взгляд кажется до смешного простой. Есть массив точек (x, y. z), надо определить есть ли такой кубик (строго говоря "параллелепипед", но "кубик" проще сказать) что все точки будут лежать на нем? Ну конечно если есть - найти все размеры сторон. Один из размеров может быть = 0 (вырожденный случай - плоский прямоугольник). Полагаем что кубик стоит "точно по осям" (не повернут в пространстве), хотя центр необязательно в точке (0, 0, 0)

А как бы Вы делали?

Спасибо

[ilyagoo]

точек-то сколько?

[Igors]

точек-то сколько?

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

[ilyagoo]

например, через 1,2,3 точки их можно построить "скок хош"))

[ilyagoo]

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

идеи-то есть какие?

[ufna]

первое, что пришло в голову

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

Либо вообще, гоним по всем точкам, проверяем лежит ли точка хотя бы на одной из полученных плоскостей. Если хоть одна не лежит на всех полученных плоскостях - то останавливаем. Это "в лоб".

[shirushizo]

1. Для начала, можно перебрать все сочетания по 3 из N (N*(N-1)*(N-2)/6) - все возможные плоскости.
2. Для каждой из плоскостей ищем точки, принадлежащие ей.
3. Все сочетаний по 4 точек лежащих на одной плоскости проверяем (M*(M-1)*(M-2)*(M-3)/24) - проверяем на прямоугольник. (Собственно - "вырожденный случай")
4. Для всех возможных пар прямоугольников, проверяешь лежат ли они на параллельных плоскостях.
5. Дальше стоит проверить равенство сторон прямоугольников, лежащих на параллельных плоскостях. Если они не равны, то это призма, иначе - параллелепипеды!
6. Ну и просто поржать - строим между ними одно из ребер. Если ребро перпендикулярно плоскости - это прямоугольный параллелепипед!

П.с: если "строго по осям", то после первого этапа можно отбросить плоскости, не параллельные плоскостям осей.

[Igors]

первое, что пришло в голову

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

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

Либо вообще, гоним по всем точкам, проверяем лежит ли точка хотя бы на одной из полученных плоскостей. Если хоть одна не лежит на всех полученных плоскостях - то останавливаем. Это "в лоб".

Да, с отсечкой все хорошо, но самостоятельного значения этот вариант не имеет.

Хмм... ну а как если кубик повернут в пространстве? Предполагаем что даны еще и полигоны. Найти куб и (любую) матрицу поворота. Или умеем только лазить по чужим огородам (движкам)? 

1. Для начала, можно перебрать все сочетания по 3 из N (N*(N-1)*(N-2)/6) - все возможные плоскости.

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

[ufna]

э.. ну проверить пирамида это или прямоугольник (в том числе и куб) - это уже на основании "если вариант найден".

что понимается под "самостоятельным значением"?


Если повернут в пространстве, поиск становится совершенно иным. А что значит "даны еще и полигоны"?

[m_ax]

Так чтож конкретно нужно: распознать куб или параллепипед?
Куб - эт частный случай параллепипеда.

[ufna]

Так чтож конкретно нужно: распознать куб или параллепипед?
Куб - эт частный случай параллепипеда.

да не суть важно, от общего идем к частностям, тут просто Igors в своем репертуаре



Для "повернутого куба" кстати аналогично - самый вариант "в лоб" это прогнать по всем треугольничкам, составить множества лежащих в одной плоскости (вычисляется элементарно). Таких множеств должно быть три, причем в каждом множестве всего две плоскости. Проверяем на перпендикулярность - вот и ответ. Матрицу поворота посчитать также элементарно.

[m_ax]

Так чтож конкретно нужно: распознать куб или параллепипед?
Куб - эт частный случай параллепипеда.

да не суть важно, от общего идем к частностям, тут просто Igors в своем репертуаре

Я это к тому, что куб распознать гораздо проще. Вот пример:
Упростим задачу: Нужно распознать квадрать от другой фигуры. Пусть также каждая вершина фигуры имеет три координаты (x, y, z).
Для распознания квадрата алгоритм прост:
1) Проверяем число вершин: если их 4 переходим к пункту 2
2) Берём произвольную точку (пусть A(x1, y1, z1) )
Строим 3 вектора AB, AC, AD.
3) Перемножаем векторно N1 = [AB, AC], N2 = [AC, AD].
4) Если вестора N1 и N2 коллинеарны и равны по модулю, и (AB, AD) = 0 или (AB, AC)=0 - это квадрат
ежели нет, то не факт что это параллепипед вообще.  

[m_ax]

Если ставится задача распознать именно куб, то решение достаточно простое:
1) выбирается произвольная точка.
2) Строится 7 векторов от этой точки до оставшихся вершин
3) Считается длина каждого вектора
4) Если это куб то должно быть: 3 длины должна совпадать и равны длинам рёбер куба, 3 другие длины должны совпадать и равны sqrt(2) * a ( a длина куба) и длина одного из векторов должна быть равна: угадайте чему))

[Igors]

э.. ну проверить пирамида это или прямоугольник (в том числе и куб) - это уже на основании "если вариант найден".

Хмм... не выглядит изящным, да и как это сделать?

Если повернут в пространстве, поиск становится совершенно иным. А что значит "даны еще и полигоны"?

Не думаю так. Лучше сначала найти матрицу поворота и помножить все точки на ей обратную - задача сводится к первоначальной.

Так чтож конкретно нужно: распознать куб или параллепипед?
Куб - эт частный случай параллепипеда.

да не суть важно, от общего идем к частностям, тут просто Igors в своем репертуаре

Прошу посмотреть на первый пост темы, там ясно сказано "параллелепипед" с вырожденным случаем - плоский прямоугольник. Предлагается использовать слово "куб" чтобы не ломать язык. В посте #2 однозначно поясняется что число точек может быть любым (а не только 8 ). Что неясно?   Я ж не виноват что Вы читаете невнимательно.  

Для "повернутого куба" кстати аналогично - самый вариант "в лоб" это прогнать по всем треугольничкам, составить множества лежащих в одной плоскости (вычисляется элементарно). Таких множеств должно быть три, причем в каждом множестве всего две плоскости. Проверяем на перпендикулярность - вот и ответ. Матрицу поворота посчитать также элементарно.

Во как - и то "элементарно" и это. Ну тогда прошу показать мне как найти матрицу поворота (это вроде проще). Конечно полагаем треугольники есть (нужны нормали)

[m_ax]

Зачем было тогда смущать народ словом кубик?

Первое что приходит в голову для распознавания параллепипеда:
1) Выбираем любые 3 точки. Как известно, через 3 точки мона провести плоскость. Поскольку в данной плоскости должен лежать параллеограмм, перебираем оставшиеся 5 точек и ищем среди них ту, которая должна лежать в четвёртой вершине. Если такой нет, то эт не параллепипед.
2) Если среди тех 5 точек такая точка находится, то у нас имеется плоскость, проходящая через известные нам 4 точки и остаётся ещё 4 точки.
3) Проверяем, проходит ли через них плоскость: если нет - то эт не параллеограмм.
4) Если да, находим вектор нормали и проверяем, коллинеарен ли он вектору нормали первой плоскости.
5) Если да... решение близко))