qrand()

[V1KT0P]

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

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

[Igors]

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

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

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

[V1KT0P]

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

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

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

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

[Igors]

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

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

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

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

[Fat-Zer]

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

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

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

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

[V1KT0P]

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

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

[Igors]

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

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

Рассматриваем треугольник (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;
}
 

Это все   

 

[Igors]

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

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

[V1KT0P]

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

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

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

[Igors]

Имеем 5 треугольников у которых известны длины сторон, а значит можно применить формулу Герона(ибо находить углы или радиусы будет накладней).

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

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

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

[V1KT0P]

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

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

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

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

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