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

[m_ax]

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

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

Код

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

 

[shirushizo]

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

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

Код

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

 

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

[Igors]

Еще раз  

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

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

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

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

[/quote]

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

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

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

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

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

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

Код

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

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

[ufna]

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

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

Определение "лежит ли на грани" тоже не так уж ясно.

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


Всем мира.


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

[brankovic]

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

например?!

Определение "лежит ли на грани" тоже не так уж ясно. Нужно брать какой-то epsilon

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

[ufna]

например?!

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

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

[brankovic]

например?!

на самом деле достаточно много. Пирамиды, конусы, призмы.

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

[ufna]

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

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

[shirushizo]

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

[ieroglif]

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

определим понятия
плоскость, параллельная плоскости 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 рандомные точки образующие плоскость ЙУХ уже не будут гарантированно эллипсом, вписанным в ббокс цилиндра образующего капсулу... так что пока тоже не догоняю =)

[Igors]

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

Вычисляется 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 больших длин по осям

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

[Igors]

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

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

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

[Igors]

1.

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

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

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

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

[shirushizo]

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

[brankovic]

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

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