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

[A_Z]

Здраствуйте уважаемые форумчане. Запиливаю небольшой 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

Спасибо

[Артем Валерьевич]

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

[Кирпи4]

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

[A_Z]

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

[Артем Валерьевич]

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

[A_Z]

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

[Артем Валерьевич]

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

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

[A_Z]

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

[Platon]

Сообщение от A_Z

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

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 - искомый центр окружности

[Program23]

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

[A_Z]

Разобрался с проблемой:
Дело было в граничных условиях - если прямо на границу описанной окружности ложились еще точки, то функция выдавала 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

[Platon]

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 )

[A_Z]

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

[Platon]

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

[A_Z]

Platon. ещё раз

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