Russian Qt Forum

опишите qrand().
для чего и как использовать?
заранее спасибо)

Эммм...

Я могу только предполагать...

Что вы незнаете значения слова random...

А так выдаёт рандомное число...

в смысле как описывать.
что то вроде
int a = qrand() * 10?

А попробовать?

рука-лицо...
нога-тапочка...

Нет слов...

По существу вопрос "а для чего нужны случайные числа ?". Очень для многого.

Пример: нужно подсчитать площадь пересечения 2 фигур - круга и прямоугольника. Площади самих фигур находятся очень просто, а вот площадь пересечения - трудно вывести формулы. А для более сложных фигур формул может вообще не быть. В то же время генерируя случайные числа (Монте-Карло) найти площадь пересечения очень просто (пусть с какой-то погрешностью)

Потока безопасный генератор псевдослучайных чисел.
Юзать очевидно

Многие вещи кажутся нам очевидными - ну действительно, как же можно этого не понимать? Однако достаточно чуть-чуть усложнить задачу - и куда денется вся очевидность  :)

Пример: сгенерировать N случайных (равномерно распределенных) точек (QPoint3D) лежащих на поверхности треугольника заданного QPoint3D p[3]

замени равномерное распределение нормальным, тогда точно будет то что надо ;)

А как Вы себе представляете нормальное распределение точек на треугольнике?  ???

Видимо "если та ф-ция не подходит - ну значит эта авось пройдет". Хелпо-знания во всей своей красе  :)

а что тут не очевидного? генерируем точки в единичном треугольнике и домножаем на матрицу преобразования.
видимо нормальное распределение в плоскости этого треугольника... но алгоритм от этого не меняется =)

А откуда взять эту матрицу? И какой треугольник "единичный"?
Прошу исполнить, а то я совсем растерялся  :)

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

(Ax-Cx)   (Bx-Cx)   (nx-Cx)   (Cx)   (Ay-Cy)   (By-Cy)   (ny-Cy)   (Cy)   (Az-Cz)   (Bz-Cz)   (nz-Cz)   (Cz)   (0) (0) (0) (1)

n= cross(AC,BC)

[added]
вру... даже обратную не надо искать.... нам эта матрица и нужна...

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

Какие "эти", точки-то как генерировать?

Отнимать С от n  все-таки не стоит :) Также неплохо прокомментировать как она применяется - точка множится на строку или на столбец? (полагаю на строку). Ну и неясно как генерируются точки на единичном треугольнике.

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

Школота. Читай до просветления http://www.sernam.ru/book_dm.php?id=6 (http://www.sernam.ru/book_dm.php?id=6)

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

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

Учитель, а что я должен там читать чтобы "просветлиться" ?  :)

Верно, это я сначала ошибся.

Не слабое у Вас "очевидно"  :) :)   Ладно, если хотите - озвучу более простое решение

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

Давайте прильнем к авторитетному для Вас первоисточнику. Вот как применяется QMatrix

C++ (Qt)
#define MAPINT(x, y, nx, ny) \
{ \
    qreal fx = x; \
    qreal fy = y; \
    nx = qRound(_m11*fx + _m21*fy + _dx); \
    ny = qRound(_m12*fx + _m22*fy + _dy); \
}
 

Здесь вектор-строка умножается на столбец матрицы (QMatrix "справа"). Fat-Zer в посте #12 сконструировал матрицу, и я так вижу, там надо множить на строку. Ничего "неправильного" в этом нет - если мы поменяем в матрице строки со столбцами и помножим на столбец - результат будет тот же. Не стоит понимать все слишком буквально :)

Это что еще за авторитетный для меня первоисточник? И причем тут QMatrix? Я тебе говорю про то, как афинные преобразования, записанные в виде матрицы трансформации применяются вообще в графике. И умножается одна матрица на другую. Полностью. А не на какую-то отдельную строку/столбец из нее

mutineer, а есть ли какая то разница?

Умножится n столбцов на n строк по алгоритму, или же умножится матрица на матрицу по алгоритму (то же самое, только скрытое от нас) ?

Вроде как Igors собирается множить только на одну строку/столбец из матрицы трансформации. Иначе не было бы вопроса "точка множится на строку или на столбец?" (в единственном числе ведь написано)

В каком это смысле сложно? Делаем алгоритм который режет пересечение на простые фигуры. А для простых фигур площади уже считаются через известные формулы. Складываем площади и получаем самую точную площадь.

Да понятно что не на один/одну  :)  Обозначим

P - трансформируемая точка
M - матрица
x - операция умножения матриц по правилам математики: строки первой множатся на столбцы второй

Преобразование MxP конечно не равно PxM, но это совсем не значит что одно "правильное" а др нет - зависит то того как создавалась/задумывалась матрица M. Вторая форма пожалуй более популярна

"точка множится на строку или на столбец?" -  и как из этой фразы понятно что не на одну строку?
Вопрос исчерпан

Да, есть, матричное произведение "некоммутативно" (от перестановки сомножителей результат меняется)

Блин, ну вот охота человеку попридираться. А как я скажу? "Вектор множится на первый столбец - получается новый х, потом исходный вектор множится на второй столбец - получается новый y...". Давайте считать что все здесь достаточно грамотны.

А на какие простые? Ну разрезали Вы на миллион квадратикоа - и что, стало легче найти площадь пересечения каждого с кругом? :)  А для особо резвых найдется напр пересечение шара с кубом. Заметим что с Монте-Карликом все остается столь же простым, и любой лох может написать за 5 мин

Сказать же очень просто - вектор множится на матрицу)))

Так у Вас получается наоборот, матрица множится на вектор

Так матрица "слева" (MxP), строки матрицы множатся на вектор-столбец. В общем, Вы сами все запутали  :)

Какие нафиг миллионы квадратиков, обычное разделение на простые фигуры.
Пока что про объемные речи не было, да тогда чуть сложнее но не настолько насколько кажется. Три примера в аттаче:
1) Площадь сегмента + площадь прямоугольного треугольника.
2) Площадь двух сегментов + площадь двух прямоугольных треугольников + площадь прямоугольника.
3) Площадь прямоугольника + площадь прямоугольного треугольника + площадь сегмента.
Как видишь для точного вычисления площадей нам потребовались обычные школьные формулы. Тоже самое делается и в объеме, просто там формул чуть больше и они чуть сложнее, ну и алгоритм разбивки тоже посложнее. Но все-равно это реализуется без проблем.
И как мне кажется это должно работать быстрее чем метод с Монте-Карликом.

У меня была такая (под)задача - и вначале я так же резво рыпался :) Первое впечатление - "та ну елы-палы, тут же школьные формулы!". Однако выяснилось что вариантов не так уж мало (гораздо больше чем Вы привели), а расчеты не так уж просты. Кстати практичнее находить пересечения с треугольником.

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

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

И вопрос в чем выигрывает Монте-Карло у численного интегрирования? Как по мне так численное интегрирование должно работать быстрее при той-же точности.

Да, "полигон" универсален. Но вот триангулировать невыпуклую фигуру может оказаться очень непросто

Я не теоретик но так понимаю что Монте-Карло один из методов численного интегрирования. Поэтому Ваш вопрос "масло масляное" :)  А вообще достоинства Монте-Карло очевидны - требуется ноль памяти и всего неск строк кода. А у Вас может и лучше, и в 100 раз быстрее, но выглядит как работа на неск дней, а то и больше.

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

при пересечении выпуклого многоугольника с кругом получается выпуклая фигура...

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

Все Вы правильно сказали (видно хорошее образование), но такое "очевидно" - издевательство над широким кругом читателей. Откуда взялась матрица? Почему ее надо строить именно так? Ладно, попробую объяснить как умею

Рассматриваем треугольник (p0, p1, p2) как локальную систему координат. Пусть центр этой системы в точке p0, ось X = p1 - p0, ось Y = p2 - p0,  Третью ось мы можем вычислить но здесь она просто не нужна поскольку нас интересуют точки только в плоскости треугольника. Пусть точка имеет локальные координаты local_x, local_y. Для любой системы перевод из локальной в мировые

p_world = center + axis_x * local_x + axis_y * local_y;  // local_z = 0
p_world = p0 + local_x * (p1 - p0) + local_y * (p2 - p0);  // в нашем случае

Раскрываем скобки
p_world = p0 * (1 - local_x - local_y) + local_x * p1 + local_y * p2;
Оказывается дело сводится к пошленькому взвешиванию. Итого

C++ (Qt)
QPoint3D RandPoint( const QPoint3D tria[3] )
{
 float lx = float(qrand()) / RAND_MAX:   // случайное локальное x
 float ly = float(qrand()) / RAND_MAX:   // случайное локальное y
 if (lx + ly > 1.0f) {   // сумма должна быть <= 1
  lx = 1.0f - lx;
  ly = 1.0f - ly;
 }
 return tria[0] * (1.0f - lx - ly) + tria[1] * lx + tria[2] * ly;
}
 

Это все  :) 

 

Возьмите любую букву из Вашего ника  (V1KT0P) - ну конечно с какой-то толщиной. И забот с триангуляцией у Вас будет более чем достаточно  :)

Взял первую букву. Даже усложнил задачу начав не с первой верхней точки а со второй.
Действия примитивного алгоритма для разбиения:
Так как известно какая часть линии смотрит внутрь, то берем первую точку и третью подряд в одном направлении. Если линия от первой до третьей точки не выходит из фигуры то строим треугольник(красным цветом), если нет то переходим к следующей точки. В примере я специально начал со второй верхней точки, так как получилось что первая и третья точки соединяют вершины буквы и выходят за фигуру то переходим к следующей точке. В итоге получается фигура с четырьмя точками в которой уже нельзя из первой в третью точку провести линию. А значит переходим к второй стадии. А именно находим две точки в этой фигуре у которых есть прямая видимость между собой и они не принадлежат одной линии, проводим линию(синим цветом). Дальше переходим к третьей стадии, а именно проверяем получившиеся две фигуры, если они не являются треугольниками, то переходим к первой стадии. У нас же в итоге получились два треугольника. Значит переходим к подсчету площади.
Имеем 5 треугольников у которых известны длины сторон, а значит можно применить формулу Герона(ибо находить углы или радиусы будет накладней).
И где здесь проблема с триангуляцией?

Витя, ну что Вы пузыри такие пускаете - площадь треугольника равна половине длины векторного произведения любых его 2 сторон.

S = crossProduct(p1 - p0, p2 - p0).length() / 2;

А так молодец. Этот алгоритм известен как "откусывание ушей" (cutting ears). Ота синяя линия называется "диагональ". В принципе алгоритм вполне usable, но медленноват (особенно накладно искать диагональ) + создает "не очень красивые" треугольники. Также "линия от первой до третьей точки" может и не выходит за пределы фигуры - но пересекать ее (др линии) - это тоже надо проверять. Также треугольник-кандидат надо выбирать с самым острым углом. Ну все это неважно - вижу что сами придумали, молодец.

Да точно, зачем вычислять расстояние если можно через векторы. Просто я не знал что через векторы просто считается площадь =).

Ну так я и не говорил что это самый быстрый алгоритм, я думаю там много чего можно в плане оптимизаций придумать. Факт что это можно сделать и что это должно быстрее считать площадь, а главное точно.
Если фигура большая и сложная то можно попробовать сразу разделить ее на несколько частей с помощью "диагоналей".
Вообще нужные алгоритмы уже есть и применяются в 3Д надо только найти их =).