Russian Qt Forum

Добрый день

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

да не суть важно, от общего идем к частностям, тут просто 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 - это квадрат
ежели нет, то не факт что это параллепипед вообще.  

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

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

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

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

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

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

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

А Вам задачу решить нужно, или красиво решить? :) Решать "изящно" на Ваш вкус нет ни времени ни желания, честно :)

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


Не думаю. Основания для определения такой матрицы? Может быть и есть, но "проще" они точно не будут, имхо.


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

Вот уж не предполагал что здесь нужна память  :) Теряюсь в догадках что то за "угол поворота" и причем здесь тригонометрия? Ладно, давайте определимся с матрицей вращения

C++ (Qt)
struct CRotMatrix {
 float m[3][3];
};
 

Правило преобразования "строка (вектора) на столбец (матрицы)".

C++ (Qt)
void Transform( float vec[3], const CRotMatrix & M )
{
 float x = vec[0], y = vec[1], z = vec[2];
 vec[0] = x * M.m[0][0] + y * M.m[1][0] + z * M.m[2][0];
 vec[1] = x * M.m[0][1] + y * M.m[1][1] + z * M.m[2][1];
 vec[2] = x * M.m[0][2] + y * M.m[1][2] + z * M.m[2][2];
}
 

Даны все точки и полигоны (пусть только треугольники). Находим матрицу поворота (ведь это "элементарно"  :))

Igors, уж извините, но код и прочие мат. выкладки делайте сами, задача то 1 курс любого матфака по курсу геометрия :) Только надо идти не от матрицы (это конечный продукт на основе трех углов), а от поиска этих самых углов. Успехов :)

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

"Матфаков" не кончал, но матрицу построю. Хотите покажу как? (только чур не злиться  :))

Ой мама, чего ж так сложно? Кто такая "выпуклая оболочка", bound box что ли? Непрямоугольный найти не требуется - просто кубик с масштабам по осям.

Igors,

ну покажите как из сиих данных построите матрицу поворота, всем же интересно чем топик закончится :)



А вот это :7: как говорится, или  :o

Да всё просто, млин))

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

Мне бы ваши проблемы ;D

Если грани параллельны плоскостям OXY OXZ OYZ, то ufna уже дал решение выше. А если "масштабы по осям" это какой-то другой зверь, то лучше расшифруйте.

Вы кажется условия не поняли. Даны не 8 вершин пп, а 1024 точки лежащие на его гранях..

Берете первый треугольник, вычисляете перпендикуляр к нему (N0), нормируете и записываете как первую строку матрицы поворота. Просматриваете оставшиеся треугольники, для каждого вычисляете перпендикуляр N Находите угол между N0 и N (достаточно косинус dotProduct). Варианты

- угол = 0. Это та же грань куба, пропускаем.
- угол = 180. Это противоположная грань, пропускаем.
- угол != 90. Это вообще не куб, возвращаем false
- наконец угол = 90, выходим из цикла

Тогда записываем N как 2-ю строку матрицы и вычисляем 3-ю как векторное двух первых. Матрица поворота готова, если теперь помножить на нее все точки, то повернутая фигура встанет "по осям". Ну правда это для куба с центром в (0, 0, 0) но учесть сдвиг - неудобно и рассказывать.

Давно замечал - OpenGL и все такое - ничему хорошему не научит  :)

Не всегда, они могут лежать на 1 прямой. Любая (или все) из граней может быть сколь угодно деталированы (т.е. точек любое число). А для только 8 точек незачем прилагать столько усилий - проще выписать др. 8 из bound box и сравнить с имеющимися.

Да уж  :)

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

Я не правильно понял условие задачи.  >:(
Я имел в виду: провирить являются ли заданные 8 вершин - вершинами параллеограмма.

Тогда положение меняется))

Igors,

это нахождение матрицы поворота для параллелипида (причем далеко не оптимальное в общем случае), а в случае сабжевой задачи будет false в общем случае. Так что я как бы не понял Вы о чем вообще? :)


Еще раз  :o Плоскость провести можно ВСЕГДА, вопрос ее единственности :)

могу уточнить еще раз :)

а) строим bounding box в соответствии с осями
б) гоним по всем точкам на предмет их принадлежности боксу

Что тут расплывчато?

Так сам парралепипед задан? Или есть только туева хуча точек и больше ничего?

Если второе могу предложить оч быстрый и простой метод:

C++ (Qt)
bool isParallepipet(const vector<Point3D> &/*data*/) {
    return (rand() > RAND_MAX/2);
}
 

 8)

Слишком большая вероятность  ;D

А можно без понтов?  :)  А то сейчас попрошу найти плоскость по 3 точкам - опять поплывете

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

[/quote]Да так и делал. Ну все прекрасно для определения "это НЕ кубик", но есть довольно много объемных фигур для которых также все точки лежат на bound box. Плюс получается очень коряво для вырожденного случая (плоский прямоугольник). Ну допустим мы запомнили напр так: точка 1 лежит на 3 гранях, точка 2 - только на одной и.т.п. - и что с того? Определение "лежит ли на грани" тоже не так уж ясно. Нужно брать какой-то epsilon (а не просто ==), тогда получается точка может лежать на 2 противоположных гранях и.т,п. Словом, четкого алгоритма нет.

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

??? Местами напоминает Монте-Карло, но неясно что Вы хотели этим сказать  :)

Igors, отвечайте, пожалуйста, за свои слова. А лучше - плавайте дальше сами. Особенно после:


Мне Вам доказывать ничего не интересно :)


Всем мира.


P.S. - кстати, "для сферы" есть давно уже созданные алгоритмы. Наверное "там же" будут более общие решения.

например?!


Так всегда с флоатами, ufna-то тут причём? ;)

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

только суть не в этом, а в том, что Igors подменяет постоянно задачи, либо не умеет их формулировать :)

ни про одну из них нельзя сказать "все точки лежат на bounding box". Это вообще-то свойство параллелепипедов. Напрашиваются "параллелепипед с дыркой", "параллелепипед с двумя дырками", "параллелепипед с дыркой в форме сердечка" и так далее..

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

Товарищи, я что-то не воткну... надо найти все возможные кубы для N точек или куб включающий все точки? Я телепатию со среды не включал

всё на самом деле просто если куб гарантированно строится вдоль осей.

определим понятия
плоскость, параллельная плоскости YZ (через оси Y, Z и точку начала координат) и пересекающая ось X  в её отрицательной части (ну представим что у нас начало координат где-то внутри куба для простоты определений). назовём -X. аналогично определим грани +X, -+Y, -+Z.
аналогично, точка, самая дальняя по -X оси это точка -х, аналогично точки +x, -+y, -+z
рандомную плоскость, не палельную хоть одной оси назовём плоскостью ЙУХ.

куб (на самом деле для начала параллелепипед, так как куб - это частный случай)
1. находим точку -x. это точка обязана лежать на грани -X.
2. так же находим грани +X, -+Y, -+Z
3. после этого пробегаем циклом по всем точкам легко определяя - принадлежит ли координата точки одной из 6и плоскостей.
4. логично, если есть точки, которые НЕ принадлежат какой-то грани - то построение через эти точки параллелепипеда ориентированного по осям координат - невозможно.
5. проверка параллелепипеда на куб проста.

сфера - примитивное.
если точки гарантированно расположены "равномерно" по поверхности (т.е. есть противоположные), то уже точки +-X могут дать диаметр сферы, а значит и её радиус и её центр.
прогон всех точек по полученому уравнению сферы даст ответ
но если точки "сбились" в один маленький участок поверхности сферы, то это уже не прокатит, и поэтому сделаем более гарантированную формулу =)
1. берём любые три точки, и через них строим окружность.
полученная окружность будет рандомной секущей сферу.
теперь берём любую точку (т.4) и проверяем её на принадлежность к этой ОКРУЖНОСТИ.
если она НЕ принадлежит, то находим на окружности самую приближённую (т.5) и самую удалённую (т.6) точки окружности по соотношению с т.4.
окружность построенная по т.4.5.6 будет диаметрально секущей для сферы и её радиус и центр будут радиусом и центром окружности для проверки всех точек.


цилиндр - решается только если находятся 4 точки плоскости ЙУХ. тогда по ним находим уравнение секущего эллипса, у него находим +-x/y/z, выясняем что из них (+-X/Y/Z) - квадрат, их (квадратные плоскости) принимаем за крышки, проверяем точки крышек.
имея точки центров крышек, и их радиусы - легко проверить любую точку на принадлежность секущей окружности цилиндра
иначе - не знаю как =)

конус - не догоняю пока =)

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

Для кубика сделал так:

Вычисляется bound box и затем

Test1: по bound box выписываем 8 "угловых" точек и проверяем имеет ли модель все 8. Если нет - это не куб

Test2: все точки должны лежать на гранях куба. Напр

C++ (Qt)
if (point[i].x - bound_box.min.x < eps)  // точка на левой грани ?
 

И так 6 раз для каждой точки

Test3: подсчитываем площадь всех полигонов, она должна быть = площади поверхности куба (с погрешностью 1%)

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

Мдааа...  не так просто как казалось  :)

"Ну Вы блин даете"  :)  Почему бы не использовать свойство сферы "все точки равноудалены от центра" (ну и центр есть также и центр bound box). Казалось бы куда уж проще, но и здесь есть подводные камни:

- сфера (напр "меридианная") может быть построена со значительной погрешностью (примерно 5%)
- простейший куб (8 точек) будет "опознан" как сфера (в самом деле - ведь все точки равноудалены). Надо проверить "число точек достаточно велико" (напр 16)

1.
"Куб включающий все точки" называется "bound(ing) box" и может быть найден для любого массива точек линейным просмотром на минимум/максимум (x, y, z).

2. По поводу "параллелепипед": в любой 3D программе это называется простым словом "Cube" и всем понятно что размеры по осям могут быть различны. Поэтому нет нужды затруднять себя написанием длинного слова.

3. Не стоит бояться что фигура "повернута", Ее всегда можно развернуть по осям подобрав матрицу поворота

В английском языке слово "параллелепипед" не что инное, как "cuboid". Им проще  =)

зачем морочите-то народ? :) http://en.wikipedia.org/wiki/Parallelepiped (http://en.wikipedia.org/wiki/Parallelepiped)

Как легко постить когда это не требует никаких усилий  :)
А может разомнемся с цилиндром? (это слово однозначное). Или это уже сложно?  :)

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

Действительно доставляет. С цилиндром проще (уже сделал). Ну да ладно - не надо так не надо  :)

как сделал?

Нахожу "caps" (крышечки) для каждой из граней

- отбираю все точки принадлежащие грани
- проверяю что они находятся от центра на расстоянии не больше радиуса (он известен из того же bound box)
- нахожу все точки на расстоянии равном радиусу (их должно быть N >= 5)
- нахожу площадь всех полигонов все точки которых принадлежат основанию и сравниваю ee с площадью N-угольника основания

После того как caps найдены, проверяю оставшиеся точки на равноудаленность от оси цилиндра. Конус - почти то же самое.

В задаче разговор был про прямоугольный параллелепипед, а писать было лень, и нечего к словам придираться Ваша любимая википедия (http://en.wikipedia.org/wiki/Cuboid)  :P

Простите за тупость, а зачем?)

Требуется чтобы фигура была "solid", т.е имеющая объем. А напр. "кусок трубы" имеет в основании "окружность" или "кольцо" (а не круг) и поэтому не должен опознаваться как цилиндр

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

Почему - может. Напр. caps цилиндра может иметь любую деталировку (равномерную или нет), но площадь-то остается постоянной.

ну вот если у нас все точки представляют из себя сектор одного капса, и сектор другого капса - это легко может быть цилиндр, но про сравнение площадей и говорить нечего =)

Идея/мысль в том что точек может быть любое число но все они образуют поверхность которая имеет фиксированную площадь

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

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