Пересечение пирамиды с конусом

[Igors]

Добрый день

Дано:
есть пирамида и конус, имеющие общую вершину O. Пирамида задана 4 векторами исходящими из O. Известно что в сечении они образуют выпуклый (convex) 4-x угольник, но длины сторон могут быть любыми (не обязательно прямоугольник). Конус задан лучом исходящим из точки O + радиус раствора. Др. словами заданы телесные углы, а "высоты" обоих не имеют значения.

Цель:
а) определить какая часть конуса в % пересекается пирамидой
b) сгенерировать N случайных новых лучей исходящих из O и пересекающих общую часть, N вычисляется как M * percent / 100, где M - общее число лучей на конус (задано пользователем) и percent - то что найдено в a)

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

Понимаю что задачка "та еще" (сам ломаю голову не первый день), ну а вдруг у кого-то скрытый/дремлющий талант? 

Спасибо

[Fat-Zer]

если это только телесные углы, то задача эквивалентна пересечению круга и четырёхугольника(двух треугольников) в плоскости перпендикулярной оси конуса.

[popper]

Вторая часть задачи наталкивает на мысль, что нужно использовать метод Монте-Карло (в том числе, для первой части). Аналитическое решение - это интеграл по объему, который тоже придется считать численно.

[Igors]

если это только телесные углы, то задача эквивалентна пересечению круга и четырёхугольника(двух треугольников) в плоскости перпендикулярной оси конуса.

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

Вторая часть задачи наталкивает на мысль, что нужно использовать метод Монте-Карло (в том числе, для первой части).

А так и было/есть в предыдущей реализации. Насовали внутрь пирамиды N векторов, проверяем сколько из них в растворе конуса. С реализацией все отлично, но беда в том что самплов нужно много (100 и больше) чтобы получить приемлемое качество. А тогда тормоза 

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

Дополнительная информация: "пирамида" не меняется в процессе расчетов, можно предвычислять любые ее данные.   

[Fat-Zer]

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

итого 8 вариантов из которых 3 тривиальные. ИМХО это будет на порядок быстрее численных методов.
для первой части можно просто добавлять/отнимать площади секторов/сегментов для второй - надо запоминать их все.

[Igors]

идея такая: отсекать или включать сегменты из круга,

Я пришел к похожим выводам, только наверное лучше идти "сегмент за сегментом". Аккуратность нужна но ничего такого уж сложного. Сделаю - отпишусь

[popper]

Может быть, для решения задачи помогут исходники QPainterPath::subtracted()?

[Igors]

Может быть, для решения задачи помогут исходники QPainterPath::subtracted()?

Не помогло, но все равно, замечание правильное, осмотреться не помешает

Точное вычисление площади сделал, получается все не так страшно

1) Проверяем возможно ли пересечение вообще используя предвычисленные данные

2) Переводим данные в систему координат с центром в точке cone_dir (направление конуса)

Код

C++ (Qt)
radius = tan(cone_angle);
for (i = 0; i < 4; ++i)   // проецируеи в плоскость конуса
 src[i] = pyramid[i] / dot(pyramid[i], cone_dir) - cone_dir;
 

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

4) Если новых точек меньше 2, проверяем находится ли центр окружности внутри пирамиды. Если да, то пирамида полностью покрывает конус, иначе они не пересекаются

5) Если новых точек 2, то это часть круга отсеченная хордой (внутренняя или внешняя в зависимости от того где центр)

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

Теперь думаю как пристроить новые N лучей. Все "кусочки" площадей имеются, поэтому "корявенько" уже можно. А вот как лучше...

[Igors]

если это только телесные углы, то задача эквивалентна пересечению круга и четырёхугольника(двух треугольников) в плоскости перпендикулярной оси конуса.

Я тоже так думал, но это неверно. Решение на плоскости приближенное  (приемлемое для небольших углов), но не точное 

[Fat-Zer]

Я тоже так думал, но это неверно. Решение на плоскости приближенное  (приемлемое для небольших углов), но не точное 

а где собака зарыта? площадь не соотносится с объёмом как 1 к одному?

[Igors]

а где собака зарыта? площадь не соотносится с объёмом как 1 к одному?

Площадь соотносится с телесным углом как 1:1 (он ведь и есть площадь на сфере). Но я промазал с пирамидой и телесным углом в одном из вариантов . См приаттаченную картинку, это банальный spherical map. Возьмем напр 1 красный квадратик. Увы, он НЕ соответствует "пирамиде" с вершиной в центре сферы, и чем он больше  - тем больше погрешность. Для др. типов маппинга (напр cubic) все хорошо/точно

[Fat-Zer]

Площадь соотносится с телесным углом как 1:1 (он ведь и есть площадь на сфере).

на сфере, но не на плоскости... дальше ничего не понял -  я не силён в графике  =(
кстати... аналитически же можно и на сфере всё просчитать...

[popper]

...
 Др. словами заданы телесные углы, а "высоты" обоих не имеют значения.

Цель:
а) определить какая часть конуса в % пересекается пирамидой
...

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

[Igors]

Но терминология здесь пока хромает.  

С терминологией нет проблем, см "телесный угол" хоть в той же Вики. Это площадь кусочка сферы, единица измерения стерадиан. Видите красные и белые квадратики на аттаче? Вот и надо посчитать какой % этой площади входит в заданный конус

на сфере, но не на плоскости... дальше ничего не понял -  я не силён в графике  =(

Просто представьте один из квадратиков пошире и 3 точки на одной из его сторон. Они не лежат в 1 одной плоскости (с центром) - значит и не проецируютя на 1 прямую

кстати... аналитически же можно и на сфере всё просчитать...

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

А в полярных координатах - квадратик описывается прекрасно, и площадь его найти несложно. Но как присобачить конус - хз. К тому же spherical map - случай частный

[Fat-Zer]

со сферой тоже самое, что и с плоскостью:
площадь окружности от конуса [сегмента сферы] = телесному углу конуса [* радиус сферы (= 1)];
площадь сектора = площадь круга * угол при вершине /2pi ;
площадь сегмента = площадь сектора - площадь треугольника.