forum.boolean.name - Новый 3d редактор RiFLe - вопрос к математикам

forum.boolean.name (http://forum.boolean.name/index.php)

- 3D-программирование (http://forum.boolean.name/forumdisplay.php?f=12)

- - Новый 3d редактор RiFLe - вопрос к математикам (http://forum.boolean.name/showthread.php?t=17900)

Новый 3d редактор RiFLe - вопрос к математикам

Здраствуйте уважаемые форумчане. Запиливаю небольшой 3d редактор RiFLe(во вложении версия на текущий момент, скриншот) для удобства создания low-poly моделей типа рельефных надписей, стен с оконными и дверными проёмами, хотя можно сделать модель и посложнее.

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

СУТЬ ПРОБЛЕМЫ
В триангуляции использован исходник для нахождения координат центра описанной окружности, который, как оказалось, с ошибкой. Из-за этого треугольники не рисуются в случае, подобном примеру Example_with_Error.

Есть статья на википедии http://ru.wikipedia.org/wiki/Описанная_окружность

но там в векторной форме и непонятно как использовать эти два числа в скобке через запятую (перемножить или что?)

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

Вот старый исходник, который счас в редакторе.

Код:

Function InCircle(xp#, yp#, x1#, y1#, x2#, y2#, x3#, y3#, xc#, yc#, r#)

                Local eps#

                Local m1#

                Local m2#

                Local mx1#

                Local mx2#

                Local my1#

                Local my2#

                Local dx#

                Local dy#

                Local rsqr#

                Local drsqr#

                eps# = 0.000001        

                Result = False

                If Abs(y1 - y2) < eps And Abs(y2 - y3) < eps Then

                    Return True

                EndIf

                If Abs(y2# - y1#) < eps# Then

                    m2# = -(x3# - x2#) / (y3# - y2#)

                    mx2# = (x2# + x3#) / 2

                    my2# = (y2# + y3#) / 2

                    xc# = (x2# + x1#) / 2

                    yc# = m2# * (xc# - mx2#) + my2#

                ElseIf Abs(y3# - y2#) < eps# Then

                    m1# = -(x2# - x1#) / (y2# - y1#)

                    mx1# = (x1# + x2#) / 2

                    my1# = (y1# + y2#) / 2

                    xc# = (x3# + x2#) / 2

                    yc# = m1# * (xc# - mx1#) + my1#

                Else

                    m1# = -(x2# - x1#) / (y2# - y1#)

                    m2# = -(x3# - x2#) / (y3# - y2#)

                    mx1# = (x1# + x2#) / 2

                    mx2# = (x2# + x3#) / 2

                    my1# = (y1# + y2#) / 2

                    my2# = (y2 + y3#) / 2

                    xc# = (m1# * mx1# - m2# * mx2# + my2# - my1#) / (m1# - m2#)

                    yc# = m1# * (xc# - mx1#) + my1#

                EndIf

                      

                dx# = x2# - xc#

                dy# = y2# - yc#

                rsqr#= dx# * dx + dy * dy#

                ;r = Sqr(rsqr)

                dx# = xp# - xc#

                dy# = yp# - yc#

                drsqr = dx# * dx# + dy#* dy#

                If drsqr# <= rsqr# Then Result = True

                Return Result

End Function

Спасибо

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Смешно выкладывать прототип редактора Модех, выдавая его за свой!, хоть бы название сменил!

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

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

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Где там Модэкс? Возможно мы его потом в Модэкс и встроим, но счас он отдельно

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

жди, я потираю руки в предвкушении срача

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Ещё раз разуйте глаза и взгляните на скриншот - это не модекс. Это мой редактор, который я писал для L.D.M.T и продолжил счас развивать

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

а тогда другое дело,

так сразу бы и отписался,

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

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

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Цитата:

Сообщение от A_Z (Сообщение 253053)

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

Код:

Edge1.X = B.X - A.X

Edge1.Y = B.Y - A.Y



Edge2.X = C.X - A.X

Edge2.Y = C.Y - A.Y



Edge3.X = C.X - B.X

Edge3.Y = C.Y - B.Y



Point1.X = A.X + B.X

Point1.Y = A.Y + B.Y



Point2.X = A.X + C.X

Point2.Y = A.Y + C.Y



Alpha1 = Edge1.X * Point1.X + Edge1.Y * Point1.Y

Alpha2 = Edge2.X * Point2.X + Edge2.Y * Point2.Y



Scale = 0.5 / ( Edge1.X * Edge3.Y - Edge1.Y * Edge3.X )



Center.X = ( Edge2.Y * Alpha1 - Edge1.Y * Alpha2 ) * Scale

Center.Y = ( Edge1.X * Alpha2 - Edge2.X * Alpha1 ) * Scale

A, B, C - вершины треугольника
Center - искомый центр окружности

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

L.D.M.T. залогинься

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Разобрался с проблемой:
Дело было в граничных условиях - если прямо на границу описанной окружности ложились еще точки, то функция выдавала true. Чтоб обойти это, в таком случае сортируем точки по величине угла к центру окружности (помог Atan2), чтоб узнать, в каком случае включать их, а в каком нет. Заодно это приводит к некоторому порядку в прорисовке треугольников

Код:

Function InCircle4(xp#, yp#, x1#, y1#, x2#, y2#, x3#, y3#, xc#, yc#, r#)



If ((xp#=x1#) And (yp#=y1#)) Or ((xp#=x2#) And (yp#=y2#)) Or ((xp#=x3#) And (yp#=y3#)) Return False



Edge1X# = X2# - X1#

Edge1Y# = Y2# - Y1#



Edge2X# = X3# - X1#

Edge2Y# = Y3# - Y1#



Edge3X# = X3# - X2#

Edge3Y# = Y3# - Y2#



Point1X# = X1# + X2#

Point1Y# = Y1# + Y2#



Point2X# = X1# + X3#

Point2Y# = Y1# + Y3#



Alpha1# = Edge1X# * Point1X# + Edge1Y# * Point1Y#

Alpha2# = Edge2X# * Point2X# + Edge2Y# * Point2Y#



Scale# = 0.5 / ( Edge1X# * Edge3Y# - Edge1Y# * Edge3X# )



CenterX# = ( Edge2Y# * Alpha1# - Edge1Y# * Alpha2# ) * Scale#

CenterY# = ( Edge1X# * Alpha2# - Edge2X# * Alpha1# ) * Scale#



radius#=Sqr((CenterX#-x1#)^2+(CenterY#-y1#)^2)

rasst#=Sqr((CenterX#-xp#)^2+(CenterY#-yp#)^2)



If rasst#<radius# Then Return True

If rasst#>radius# Then Return False



If rasst#=radius#

        angle#=ATan2(CenterY#-YP#,CenterX#-XP#)

        If (angle#>=90 And angle#<180) Or (angle#=>-90 And angle#<0)

                Return True

        Else

                Return False

        EndIf

EndIf



End Function

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

A_Z
немного побрюзжу по поводу кода :)

- не забывай о погрешности float и сравнивай float переменные в виде разницы между ними:

Код:

If Abs( переменная1 - переменная2 ) < EPSILON

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

Код:

...

If rasst#=radius#

...

- зачем это условие? Если расстояние не больше и не меньше радиуса, значит и так очевидно что они равны :)
- не обязательно везде указывать тип переменной ( я про значок # ), достаточно при обьявлении или первом использовании.
- не забывай обьявлять локальные переменные в функциях как Local, иначе может быть конфликт с глобальными переменными

Код:

If (angle#>=90 And angle#<180) Or (angle#=>-90 And angle#<0)

        Return True

Else

        Return False

EndIf

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

Код:

Return ( angle >= 90 And angle < 180 ) Or ( angle => -90 And angle < 0 )

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Cпасибо Platon, это все учту:)
конкректно по вопросу почему
...
If rasst#=radius#
...
- это как раз и есть граничное условие в триангуляции Делоне, что больше чем 3 точки оказывается на описанной окружности (скажем надо протриангулировать прямоугольник - там два треугольника, но если описывать окружность вокруг них, то четвёртая точка прямоугольника будет лежать на её границе) - поэтому конкретно для этого случая и приходится делать так.

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

A_Z
Это условие лишнее, т.к. у тебя выше него есть два условия - расстояние меньше радиуса и расстояние больше радиуса, если оба условия не сработают, то значит расстояние равно радиусу и смысла еще раз это проверять нет :)

Ответ: Новый 3d редактор RiFLe - вопрос к математикам

Platon. ещё раз

если прямо на ГРАНИЦУ описанной окружности ложились еще точки, то функция выдавала true. Чтоб обойти это, в таком случае сортируем точки по величине угла к центру окружности (помог Atan2), чтоб узнать, в каком случае включать их, а в каком нет. Заодно это приводит к некоторому порядку в прорисовке треугольников