Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Геометрия]точка в усечённом конусе ?

Автор: CompWorm 5.6.2009, 22:26

Доброго времени суток. задача состоит в написании функции проверки нахождения точки в усечённом конусе.  итак, мой конус задан 6 координатами центров и, соответственно,  двумя радиусами отсекающих окружностей: X1, Y1, Z1 - центр первой отсекающей окружности R1 - её радиус. X2, Y2, Z2 - центр второй отсекающей окружности R2 - её радиус. x, y, z - координаты точки в пространстве. то есть, конус может быть и наклоненным, а отсекающие окружности, само собой, остаются взаимно перпендикулярными. формула поверхности конуса второко порядка такая:  а выглядит эта штука так:  это конечно не усеченный конус)))) тут нет нижней отсекающей поверхности и более того, он в отрицательной полуоси z повторяется. возможно кто-то знает более подходящую формулу именно усеченного конуса... я лично в ангеме не силён) вопрос... как этим пользоваться? как связать X1, Y1, Z1, R1, X2, Y2, Z2, R2, x, y, z с этой формулой?    я так понимаю, как-то надо заюзать нормали этой поверхности...

Автор: Курсант 6.6.2009, 18:41

Пардон, ошибся... Подумаю  Ага, подумал  Нужно: 1. Построить прямую, проходящую через точки (x1, y1, z1) и (x2, y2, z2) 2. Построить нормаль к этой прямой, проходящую через точку (x, y, z) 3. Если точка пересечения прямой и нормали не находится между точками (x1, y1, z1) и (x2, y2, z2) то точка вне конуса... 4. Если же она между этими точками, то находим коэффициенты a и b радиуса поверхности конуса от расстояния от точки (x1, y1, z1) а именно: a=(R2-R1)/(расстояние между точками),  b=R1... Это коэффициент будет... Дальше берем расстояние от точки (x, y, z) до прямой (x1, y1, z1)-(x2, y2, z2) и сравниваем с выражением ax+b, где x - расстояние от (пересечения нормали построенной в п.2 с этой прямой) до (точки (x1, y1, z1))...  Если радиус в точке пересечения больше чем расстояние от точки до прямой, то точка внутри фигуры, а если радиус меньше - то точка вне фигуры... Уффф, кажется все... Щас рисунок попробую сделать...

Автор: Курсант 6.6.2009, 22:16

Еще есть вариант... У Вас есть две точки и нормаль (нормаль это прямая проходящая через две твои точки)... Поэтому в каждой точке можно построить по одной плоскости, делящей пространство на полупространства... Уравнения полупространств наверняка как-то получить можно... очевидно что уравнение плоскости будет ( ... = 0 ) , тогда уравнения полупространств будут соответственно ( ... > 0 ) и ( ... < 0 )... Аналогично поверхность конуса делит пространство на подпространства, где ( ... = 0 )  - уравнение поверхности, и далее ( ... < 0 ) и ( ... > 0 ) - это соответственно внутреннее и внешнее подпространства поверхности... Вот Вам надо написать три функции - определения нахождения точки в каждом из трех подпространств... Если все три функции вернули тру, значит точка внутри фигуры, если нет - значит вне фигуры... Такое вот предположение... Не ругайтесь, если оно глупой (ан гем я сам забыл сто лет назад), то можно воспользоваться первым вариантом... Добавлено @ 22:27 Мда, посмотрел, Вам прийдется в этом случае найти вершину конуса, и перевести координаты точки (x, y, z) в систему координат с центром в вершине конуса и с осью z направленной по оси симметрии конуса... После этого сможете обращаться с подпространствами, которые получаются из конуса и плоскостей... При этом первое подпространство будет задано неравенством z > z1' , второе будет задаваться неравенством z < z2' , и каноническое уравнение конуса второго порядка будет задано уравнением, которое Вы написали выше.. подпространства его будут: внутреннее - < 0 и внешнее - > 0 ... вот этими то объектами Вы и сможете все это дело определить...

Автор: CompWorm 7.6.2009, 12:39

спасибо, Курсант, допишу свой третий вариант (это фактически доработанный твой первый)... 1) перевести систему координат из стандартной 3D (x, y, z) в  частную систему конуса 2D (x` y`). она располагается на плоскости, образуемой  тремя точками (x, y, z)-(x1, y1, z1)-(x2, y2, z2).  это самый сложный момент. 2) теперь наши точки имеют координаты (x', y') , (x1', y1')-(x2', y2'). теперь совсем просто проверить, находится ли наша точки между отсекающими кругами: она между ними, если (x1'<x'<x2') или (x2'<x'<x1') в противном случае, точка точно за отсекающими кругами. 3) теперь от поверхности конуса осталась только прямая  (её концы нас не интересуют. это учтено в пункте 2) нам нужно найти Y3' этой прямой в точке X3'=x' (абсцисса нашей искомой точки) и если Y3'>y' то наша точка под прямой. ВСЁ!    ----------------------------------------------------- теперь то, ради чего создавалась эта тема - функция контроля точки. то есть далее речь пойдет о формулах и конкретных математических расчетах. надеюсь, кто-нибудь мне в этом поможет. давайте прежде всего прикиним, какой из трёх представленных алгоритмов наиболее быстрый с точки зрения математических расчетов и перейдем к матчасти этой задачи. для меня тут самое сложное это математика)))))  мой метод кажется мне очень простым, но я не уверен в том что он окажется быстрее в плане расчетов двух методов предложенных Курсантом. мне кажется, с использованием уравнения поверхности это выйдет быстрее!!! очень хотелось бы добить именно этот вариант... давайте распишим математику и увидим, какой метод лучше.  я распишу свой вариант. 1) перевод координат...  хммм... понятия не имею, как это реализовать)))))))))) подскажите? 2) проверяем относительно кругов if Min(x1`,x2`) < x' < Max(x1`,x2`) если ни то ни другое - false. 3) y3' = k * x3' + b где: x3'=x' k это тангенс угла наклона = ( Max(R1, R2) - Min (R1, R2) ) / ( Max(x1', x2') - Min (x1', x2') ) b это на сколько приподнята прямая над осью x.  b = Min (R1, R2) когда нашли y3' от x'  -  проверяем, если if (y3' > y') то точка в конусе. в противном случае false подскажите, как мне координаты перевести в первом пункте ?

Автор: Курсант 7.6.2009, 21:42

http://gis-lab.info/qa/datum-transform-methods.html Вот здесь описан переход к другой системе координат через ее известные смещение/поворот относительно исходной... Нормаль все равно прийдется строить мне кажется... Я не помню точно, но мне кажется Вам прийдется найти три единичных вектора. Первый из них направленный по прямой (1)-(2), второй по нормали к этой прямой через точку (xyz), а третий будет их векторным произведением. Тогда в этой СК значения Z для всех точек будет равным нулю, и можно будет поверхность вырождать в трапецию... И все таки мне все больше начинает нравится второй вариант - можно найти всего одну СК, в которой точки (1) и (2) вырождаются в точки на оси z, уравнение поверхности вырождается в каноническое, которое Вы привели, внутренняя область конуса вырождается соответственно в неравенство (x^2/a^2 + y^2/b^2 - z^2/c^2 < 0) а полупространства вырождаются в уравнения z {принадлежит} (z1'...z2')... то есть совпадение точки и полупространств вычислить будет элементарно... Вершина находится элементарно, раз у вас есть координаты и радиусы, углы поворота осей может найдете из приведенной ссылки.

Автор: CompWorm 9.6.2009, 21:48

Курсант,  пока не забыл, +1   . ха ха, я конечно дубина)))) как только я эти матрицы поворота и смещения увидел - сразу вспомнил, что они у меня в одной книжке были)) Цитата(Курсант @  7.6.2009,  21:42 ) И все таки мне все больше начинает нравится второй вариант вот, да! мне тоже))) если я правильно понимаю, надо "сместить" конус в начало координат, и развернуть его стоймя, так чтоб ось идущая от нас совпала с нормалью от искомой точки до оси конуса и тогда одна ось вырождается? сместить просто - берм центр одного из отсекающих кругов, например 1 и вычетаем его x, y, z из коорднинат искомой точки, точки 1 и 2. для поворота надо использовать матрицу поворота. с углами поворота замута тоже, но думаю можно вычисить из катетов и акрсинусов всяких. Цитата внутренняя область конуса вырождается соответственно в неравенство (x^2/a^2 + y^2/b^2 - z^2/c^2 < 0) а полупространства вырождаются в уравнения z {принадлежит} (z1'...z2')... а как быть с концом конуса??? достраивать? ну допустим)) тогда есть мысль - подставить в каноническое уравнение координаты от искомой точки y` и z` ( где z {принадлежит} (z1'...z2') )  y'=0 к стати    оси как тут (ось x сонаправлена с нормалью искомой точки) , найдя точки X поверхности (их будет две на одной и другой стороне) и проверить, принадлежит ли x' этому промежутку? так?

Автор: Курсант 9.6.2009, 23:36

За плюсик пасибо     Что касается преобразований - я немного другое имел ввиду... Найти систему координат конуса, вот что я имел ввиду... Систему координат, в которой начало координат в вершине конуса, ось z направлена по прямой (1) - (2)... Вот по координатам точек этой прямой можно найти два угла поворота системы координат конуса относительно исходной. А по "раствору" конуса можно определить коэфф-ты a, b, c для его канонического уравнения в этой системе координат. Усе. Теперь у Вас есть вектор смещения СК конуса относительно исходной СК (координаты вершины конуса и будут составляющими этого вектора). Углы поворота тоже можно вычислить через угол наклона оси конуса... Дальше преобразовывайте координаты точки из исходной СК в СК конуса, и уже в ней, имея коэффициенты a, b, c, а также значения z1 и z2 (где z1 и z2 есть расстояния центров отсекающих кругов от вершины конуса) можно определить, внутри конуса точка или снаружи... Если трудно - всегда можно вернуться к первому варианту - построению нормали, проходящей через точку. Всего то... Добавлено @ 23:49 Вершина конуса:  x0 = x2-(x1-x2)/(R1-R2)*R2; y0 = y2-(y1-y2)/(R1-R2)*R2; z0 = z2-(z1-z2)/(R1-R2)*R2; З.Ы. Есть предположение у меня, что по координатам двух точек не получится найти углов наклона прямой. Хотя возможно что: Угол поворота вокруг оси Ox будет равен углу между осью z и проекцией прямой на плоскость yOz... А угол поворота вокруг оси Oy' будет равен углу между прямой и плоскостью yOz... В общем код будет представлять из себя пару квадратных корней, пару арккосинусов, несколько синусов-косинусов... А так - ничего особенного... Как по координатам синусы углов между прямыми и плоскостями, проекциями и т.п. найти думаю сможете? Там по т. Пифагора все проекции очень миленько высчитываются... Щас спать пора, а завтра может допишу  Вот графический комментарий... Сначала поворачиваем вокруг оси X на угол альфа, а потом вокруг получившейся оси Y' на угол бета. То есть в моем понимании, угол поворота вокруг оси X , будет равен arccos((z1-z0)/корень((z1-z0)^2+(y1-y0)^2)) а вокруг оси Y' arccos(корень((z1-z0)^2+(y1-y0)^2)/корень((z1-z0)^2+(y1-y0)^2+(x1-x0)^2))

Автор: CompWorm 10.6.2009, 15:19

хе хе!    ну а матрицы то на что! я почесал репу и пришел к такому мнению: ты прав, достаточно два любых поворота, но нас сами углы как таковые не интересуют, ибо если сместить R2 в точку (0,0,0), где R2>R1, то координаты точки R1 мы знаем! давай считать, что расстояние между R1 и R2 известно и равно L. тогда координаты точки R1 после смещения x1', y1', z1'  = (0,0,-L).  начальные координаты и конечные знаем, теперь осталось определить внешний вид самих матриц поворота. думаю, что математики меня не порвут, если я сделаю так    : |x1|  |        |  |        |    | x' | |y1|*|   Z   |*|   Y   | = | y' | |z1|  |        |  |        |    | z' | то есть, помножив известные x1,y1,z1 на две матрицы поворота (вокруг Z и вокруг Y например) получим известные координаты (0,0,-L). соответственно нам надо отсюда найти элементы произведения |Z| на |Y|. всё. теперь подставляем вместо координат точки 1 координаты искомой точки x, y, z и получаем её новые координаты x', y', z' !   сами матрицы берем http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%D0%B0 с матрицами я не в ладах, но думаю так можно)))) я тебя малость не дождаля и решил от скуки расписать своё решение из предыдущего поста. посмотри рисунок, который я приложил. считаем, что координаты уже преобразованы и конус торчит как на рисунке 2.  для перехода к каноническому уравнению надо найти смещение усеченного конуса по оси Z. для этого я нахожу его вершину. хмм... эти формулы у нас с тобой разные))))) вершина находится в точке (0, Z) и для ее нахождения я использую уравнение прямой, проходящей через две заданные несовподающие точки. расстояние от начала координат до первой отсекающей окружности я обозначил как Lo и Lo=-Z  теперь решаем каноническое уравнение (рисунок 1). здесь считаем, что a=b; c=L+Lo; x=y. решив его находим два игрика Yo и Y1, равные, соответственно, двум иксам. это и есть промежуток для сравнения. сравнение такое: Z {принадлежит} (Lo, Lo+L) X {принадлежит} (Yo, Y1) Y {принадлежит} (Yo, Y1) всё    --------------------- есть ещё свежая мысль, определить, принадлежит ли искомая точка сечению конуса в точке z... но я пока не нашел уравнения сечения конуса в декартовых координатах... возможно такой способ еще проще, ведь сечение можно построить, наверно и без преобразования СК ))) хотя хз...

Автор: Курсант 10.6.2009, 17:37

Я считаю, что удобнее будет центр СК помещать в вершине конуса. Тогда вектор смещения исходной СК в СК конуса будет равен (координаты вершины конуса) - (координаты начала координат, т.е. (0, 0, 0) ) Удобнее потому, что если у тебя центр СК будет в точке x1, y1, z1 то уравнение конуса будет иметь вид (x-x1)^2/a^2 + (y-y1)^2/b^2 - (z-z1)^2/c^2 = 0, а это трабла полная... Проще центр СК иметь в точке вершины конуса, тогда уравнение будет x^2 + y^2 - z^2/((расстояние от т.1 до вершины)/R1)^2 = 0, то есть a=1, b=1, c=(расст. от т.1 до вершины конуса)/R1... А по отношениям длин проекций (см пост выше) можно построить сразу и матрицу направляющих косинусов... как в той википедии которую ты разместил в предыд посте... Вектор сдвига есть, матрица поворота есть. Сначала пересчитывай точку (x y z) в сдвинутой СК, потом пересчитывай эту точку из сдвинутой СК в сдвинуто-повернутую, путем умножения на матрицу  направляющих косинусов  - вуаля, у тебя есть координаты точки относительно канонического конуса и двух плоскостей... Проверяй условия вхождения точки одновременно в три объемных области, если хоть одна область не содержит точку, то вне, а если все содержат, то внутри. Чтобы пересчитать точку (x, y, z) в СК конуса, в любом случае нужны вектор смещения и поворотная матрица.

Автор: CompWorm 11.6.2009, 10:56

Цитата(Курсант @  10.6.2009,  17:37 ) Я считаю, что удобнее будет центр СК помещать в вершине конуса. Тогда вектор смещения исходной СК в СК конуса будет равен (координаты вершины конуса) - (координаты начала координат, т.е. (0, 0, 0) ) Удобнее потому, что если у тебя центр СК будет в точке x1, y1, z1 то уравнение конуса будет иметь вид (x-x1)^2/a^2 + (y-y1)^2/b^2 - (z-z1)^2/c^2 = 0, а это трабла полная... Проще центр СК иметь в точке вершины конуса, тогда уравнение будет x^2 + y^2 - z^2/((расстояние от т.1 до вершины)/R1)^2 = 0, то есть a=1, b=1, c=(расст. от т.1 до вершины конуса)/R1... я так и делаю. просто сначала мне надо найти Lo, а потом делаем СК стандартной для канонического уравнения, ка ты и пишешь. на счет остального, соглашусь и подумаю над этим. спасибо. скорее всего это и будет идеальный вариант. последнее, вопрос про формулу сечения конуса, о чем я писал выше... не в курсе какая она? может её как-то можно использовать без преобразований СК

Автор: Курсант 11.6.2009, 13:16

Лучше не стоит - это опять надо будет по теореме Пифагора длины вычислять, и тому подобное.. Лучше не стоит.. Сначала лучше ную матрицу, потом каноническое уравнение... Тем более что от поворота все равно никуда не деться - как минимум одну точку поворачивать надо...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)