Помогите найти способ, как определить области, заштрихованные на рисунке. Есть куб со стороной 1 и единичная окружность, пересекающая его. Окружность определяется через радиус, координаты центра и нормаль к плоскости. Центр куба совпадает с началом координат, стороны куба ориентированы вдоль декартовых осей (направление осей приведено на рисунке).



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

Кто может, подскажите, в какую сторону "копать", т.к. очень нужно

честно говоря, не очень понятно, что значит "отсечение окружностью"... (впрочем, может, это только мне)
если я не ошибаюсь, об отсечении (в данном случае в 3d) можно говорить, когда какая-то поверхность разделяет какое-то тело на две несвязанные части
в случае окружности такого не происходит - это даже не поверхность, с тем же успехом можно отсекать от куба что-нибудь с помощью прямой
если даже заменить окружность на круг и предположить, что он достаточно большой, то это эквивалентно отсечению плоскостью
однако, если окружность пересекает куб, значит, соответствующий круг недостаточно большой и он не делит куб на несвязанные части...
P.S. может, описать исходную задачу, при решении которой понадобилось решать эту?
Добавлено @ 20:43
вообще, если посмотреть на рисунок, создается впечатление, что речь идет о проекции круга на разные грани куба... в случае куба, да еще и ориентированного по осям, проекция - одно удовольствие - просто отбрасывать одну координату...

Это сообщение отредактировал(а) maxim1000 - 30.10.2005, 20:44

maxim1000, спасибо за ответ.

Переформулирую задачу: есть телесный угол, выходящий из центра куба. Телесный угол задан своим направлением и углом раствора. Надо для каждой грани куба определить, пересекается ли она с телесным углом, и если да - то определить прямоугольную область, охваченную телесным углом у этой грани. В итоге должна получиться фигура, аналогичная сферическому сегменту, но начерченная на гранях куба (поэтому говорится об отсечении). Вроде, правильно сформулировал... Можно ещё представить, будто куб со стороной 1/sqrt(2) вписан в сферу с радиусом 1, тогда задача будет сводиться к проекции краевой окружности сферического сегмента на вписанный куб.

Цитата(maxim1000 @ 30.10.2005, 20:41)

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

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

Хелп !

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

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

Цитата(maxim1000 @ 31.10.2005, 03:59)

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

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

Цитата(fin @ 30.10.2005, 23:27)

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

я тоже помню такие задачки: пересечение двух плоскостей, рисуется 2 треугольника - и погнали; только это не катит, т.к. нужно программно это делать, да и задача отличается (нужно проецировать, а не пересекать 2 плоскости).

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

Цитата

Если есть куб и конус, который "из него торчит", то мы просто имеем две пересекающиеся поверхности.

похоже на то...

Цитата

Т.е. пишем уравнение для обоих поверхностей и считаем в каких точках они пересекаются

да, это - более общий случай
получится уравнение типа F(x,y,z)=0, которое надо будет решать
предложенный мной вариант - один из способов решения этого уравнения...
Добавлено @ 15:37

Цитата

попробую... хотя не очень хорошо понял...

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

Цитата(DENNN @ 31.10.2005, 09:24)

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

Полностью прав.

Цитата(maxim1000 @ 31.10.2005, 15:30)

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

Дано:
1) есть куб со стороной 1, центр куба лежит в начале координат;
2) из начала координат выходит конус, описываемый двумя параметрами: направление прямой (kx,ky,kz) и углом конуса (alpha)
3) alpha может быть: 270, 180, 90, 45, 22.5 градусов, и т.д.
4) направление прямой (kx,ky,kz) может быть произвольным
5) высоту конуса (т.е. длину его направляющей прямой) можно считать бесконечной

Найти:
Для каждой грани куба нужно определить, пересекает ли её конус, и если да - найти область, лежащую внутри конуса. Как минимум, нужно вывести формулы, по которым находится такая область для грани куба, параллельной плоскости XY, т.к. это самый простой вариант. Потом можно будет использовать эти формулы для любой грани куба, просто поворачивая грань и конус к плоскости XY.

Цитата(DENNN @ 31.10.2005, 09:24)

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

Да. У меня проблемы с аналитической геометрией, к сожалению

Ну, определить какие грани конус не пересекает не сложно. Нужно брать угол между нормалью к грани и "вектором направления" конуса (та самая твоя прямая). Если грани ориентированны так, что нормали всегда направленны наружу, а угол не развернутый (меньше 180 градусов), то конус не будет пересекать грань(ни), угол с нормалью которой больше 90 градусов.
для граней, которые рассекаются стороной конуса на ЭВМ определять линию пересечения можно итеративно.
Скажем, для грани, параллельной пл. OXY, пересекаемой осью конуса под углом alfa, то мы получаем вектор, вершиной расположенный вточке пересечения оси и плоскосит и очерчивающий круг радиуса R. Тогда задача сводится к тому, что необходимо найти все проекции этого вектора на плоскость грани куба.
Возбмем одно из положений ветора, когда он находится в плоскости грани за начальное и будем отсчитывать от него угол beta. Тогда спроектироанный на плоскость вектор можно получить как сумму двух векторов: проекция на саму ось пересечения, равная S*cos(beta) и перпендикулярная сосотавляющая в плоскости грани равная sin(beta)*cos(alfa), где S- длина вектора.

Постараюсь к вечеру изобразить на рисунке и отсканировать. Только возникает вопрос: в каком виде нужно представить результат? В виде полигона, ввиде набора 3D точек, просто показать, что линия пересечения - это кривая второго порядка (в частном случае эллипс или круг)?

Это сообщение отредактировал(а) DENNN - 1.11.2005, 13:34

DENNN, спасибо за ответ.

Цитата(DENNN @ 1.11.2005, 13:32)

Ну, определить какие грани конус не пересекает не сложно. Нужно брать угол между нормалью к грани и "вектором направления" конуса (та самая твоя прямая). Если грани ориентированны так, что нормали всегда направленны наружу, а угол не развернутый (меньше 180 градусов), то конус не будет пересекать грань(ни), угол с нормалью которой больше 90 градусов. для граней, которые рассекаются стороной конуса на ЭВМ определять линию пересечения можно итеративно.

Если угол не развёрнутый - тогда всё Ok, но если скажем угол в 270 градусов - как в таком случае определяется, пересекает ли конус грань куба ?

Цитата(DENNN @ 1.11.2005, 13:32)

Возбмем одно из положений ветора, когда он находится в плоскости грани за начальное и будем отсчитывать от него угол beta. Тогда спроектироанный на плоскость вектор можно получить как сумму двух векторов: проекция на саму ось пересечения, равная S*cos(beta) и перпендикулярная сосотавляющая в плоскости грани равная sin(beta)*cos(alfa), где S- длина вектора.

Без рисунка наверное не пойму

Цитата(DENNN @ 1.11.2005, 13:32)

Постараюсь к вечеру изобразить на рисунке и отсканировать. Только возникает вопрос: в каком виде нужно представить результат? В виде полигона, ввиде набора 3D точек, просто показать, что линия пересечения - это кривая второго порядка (в частном случае эллипс или круг)?

Буду очень благодарен !
Результат нужен в виде прямоугольной области, полностью охватывающей линию пересечения, т.е. для грани OXY нужны координаты (x1;y1)-(x2;y2). Куб можно взять с любой стороной - важен лишь способ вычисления результата.

Цитата(mr @ 1.11.2005, 17:40)

о если скажем угол в 270 градусов - как в таком случае определяется, пересекает ли конус грань куба ?

Если ты представишь себе даный случай, то поймешь, что на самом деле конус просто направлен в противоположную сторону. Т.е. берешь обратное направление конуса и угол у него = 360-угол

Мне тут мысль пришла в голову, что возможно будет полезно просто определить точки пересечение куба с конусом и соединить их векторами. Чем больше точек будет в общем, тем больше будет всяких разных векторов, которые и описывают плоскость, котороя заштрихована. То есть я бы предложил решить задачу не аналитическим а нумерическим образом (или как там по-русски ). И массив векторов соединяющих точки пересечения и будет описывать твою плоскость. Потом с помощью массива можно наривать ее и повернуть так как тебе захочется.

Цитата(mr @ 1.11.2005, 08:52)

Как минимум, нужно вывести формулы, по которым находится такая область для грани куба, параллельной плоскости XY, т.к. это самый простой вариант.

А хотя если прочитать вот это, то похоже все таки нужно аналитическое решение.

Кстати помоему векторное произведение двух векторов соединяющих точки пересечения (то есть вектор) и описывает плоскость, которая отсекает часть куба...

Цитата(cardinal @ 1.11.2005, 18:27)

Мне тут мысль пришла в голову, что возможно будет полезно просто определить точки пересечение куба с конусом и соединить их векторами. Чем больше точек будет в общем, тем больше будет всяких разных векторов, которые и описывают плоскость, котороя заштрихована. То есть я бы предложил решить задачу не аналитическим а нумерическим образом (или как там по-русски ). И массив векторов соединяющих точки пересечения и будет описывать твою плоскость. Потом с помощью массива можно наривать ее и повернуть так как тебе захочется.

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

Цитата(cardinal @ 1.11.2005, 18:27)

Кстати помоему векторное произведение двух векторов соединяющих точки пересечения (то есть вектор) и описывает плоскость, которая отсекает часть куба...

Нужно получить линию, по которой конус пересекается с кубом. Разве бока у конуса являются плоскостью ?

Очень всё-таки хочется докопаться до истины.
Добавлено @ 20:04

Цитата(DENNN @ 1.11.2005, 18:14)

Если ты представишь себе даный случай, то поймешь, что на самом деле конус просто направлен в противоположную сторону. Т.е. берешь обратное направление конуса и угол у него = 360-угол

Понял !

Получается как бы два конуса - один с углом 180 градусов (линия пересечения с кубом будет равна линии, по которой куб пересекается с плоскостью, нормаль которой = направляющей конуса), и другой конус - с углом меньше 180 градусов. Находим линию пересечения второго конуса с кубом, и инвертируем полученную область на кубе. Здорово !

Вот бы ещё научиться находить сабж...

Вот, типа мои скромные художества . Если получилось непонятно - спрашивайте.

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

На втором собственно сама суть: две плоскости. X-плоскость грани куба. Н- плоскость, образованная радиусом в точке пересечения оси конуса с кубом. r- радиус-вектор, численно равный радиусу конуса в данной плоскости.

Присоединённый файл ( Кол-во скачиваний: 5 )
 duda.zip 192,29 Kb