Russian Qt Forum
Ноябрь 11, 2024, 05:25 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 2 [3] 4   Вниз
  Печать  
Автор Тема: Распознать кубик  (Прочитано 29159 раз)
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #30 : Февраль 12, 2011, 23:48 »

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

Если второе могу предложить оч быстрый и простой метод:
Код
C++ (Qt)
bool isParallepipet(const vector<Point3D> &/*data*/) {
   return (rand() > RAND_MAX/2);
}
 

 Крутой
« Последнее редактирование: Февраль 12, 2011, 23:51 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
shirushizo
Гость
« Ответ #31 : Февраль 13, 2011, 08:11 »

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

Если второе могу предложить оч быстрый и простой метод:
Код
C++ (Qt)
bool isParallepipet(const vector<Point3D> &/*data*/) {
   return (rand() > RAND_MAX/2);
}
 

 Крутой
Слишком большая вероятность  Смеющийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #32 : Февраль 13, 2011, 17:08 »

Еще раз  Шокированный
могу уточнить еще раз Улыбающийся
А можно без понтов?  Улыбающийся  А то сейчас попрошу найти плоскость по 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
Гость
« Ответ #33 : Февраль 13, 2011, 17:30 »

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

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

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

Мне Вам доказывать ничего не интересно Улыбающийся


Всем мира.


P.S. - кстати, "для сферы" есть давно уже созданные алгоритмы. Наверное "там же" будут более общие решения.
Записан
brankovic
Гость
« Ответ #34 : Февраль 13, 2011, 17:51 »

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

например?!

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

Так всегда с флоатами, ufna-то тут причём? Подмигивающий
Записан
ufna
Гость
« Ответ #35 : Февраль 13, 2011, 18:09 »

Цитировать
например?!

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

только суть не в этом, а в том, что Igors подменяет постоянно задачи, либо не умеет их формулировать Улыбающийся
Записан
brankovic
Гость
« Ответ #36 : Февраль 13, 2011, 18:14 »

Цитировать
например?!

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

ни про одну из них нельзя сказать "все точки лежат на bounding box". Это вообще-то свойство параллелепипедов. Напрашиваются "параллелепипед с дыркой", "параллелепипед с двумя дырками", "параллелепипед с дыркой в форме сердечка" и так далее..
Записан
ufna
Гость
« Ответ #37 : Февраль 13, 2011, 18:17 »

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

здесь встает вопрос что понимать под "все точки лежат". Так то да, я с тобой согласен, если говорить "о всех точках" - ты прав. Просто в контексте задачи, как я понимаю, речь идет о фигурообразующих точках, т.е. "вершинах". В этом случае множество таких фигур сразу появляется.
Записан
shirushizo
Гость
« Ответ #38 : Февраль 13, 2011, 22:10 »

Товарищи, я что-то не воткну... надо найти все возможные кубы для N точек или куб включающий все точки? Я телепатию со среды не включал
Записан
ieroglif
Гость
« Ответ #39 : Февраль 14, 2011, 02:23 »

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

определим понятия
плоскость, параллельная плоскости 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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #40 : Февраль 14, 2011, 13:57 »

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

Вычисляется 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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #41 : Февраль 14, 2011, 14:09 »

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #42 : Февраль 14, 2011, 14:18 »

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

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

3. Не стоит бояться что фигура "повернута", Ее всегда можно развернуть по осям подобрав матрицу поворота
Записан
shirushizo
Гость
« Ответ #43 : Февраль 14, 2011, 19:43 »

В английском языке слово "параллелепипед" не что инное, как "cuboid". Им проще  =)
Записан
brankovic
Гость
« Ответ #44 : Февраль 14, 2011, 21:24 »

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

зачем морочите-то народ? Улыбающийся http://en.wikipedia.org/wiki/Parallelepiped
Записан
Страниц: 1 2 [3] 4   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.307 секунд. Запросов: 23.