Центр описанной окружности

Дан остроугольный треугольник координатами своих углов.
Нужен алгоритм (приближенный), который бы позволил достаточно
быстро вычислить центр описанной вокруг этого треугольника
окружности.
Решение
1. Несложно вычислить стороны треугольника
2. Потом площадь треугольника
3. Наконец радиус описанной окружности
4. Центр описанной окружности будет находиться внутри треугольника
5. Можно конечно с помощью случайных чисел определить с
заданной погрешностью этот центр...
А есть ли нечто более быстрое?

0

Опять 25…для чего вам центр окружности по 3 точкам?
Вот аналитику показали… два других метода тоже придумал =). Быстрей метода 1 ничего не будет.

Сообщение от йот Найдем в этом треугольнике центр описанной окружности

Это и есть окружность по трем точкам…дальше ненужные усложнения. Честно лень вникать.

0

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

0

Любые итерационные методы хуже аналитических и в смысле скорости и в смысле точности.

0

Быстрей метода

Сообщение от Excalibur921 1)Координаты в 2д разбить сеткой.

наверно ничего не существует.
Намного меньше база данных у метода 2 но он и медленней.

Добавлено через 3 часа 11 минут
Пределы координат вершин и точность центра?

Добавлено через 59 минут
Стоит прикинуть грубо размеры базы данных центров так становиться страшно.
50 на 50 сетка =2500 положений точки
точек 3 значит:
2500^3= 15 625 000 000 комбинаций
Координаты ответа 2 значит 15*2=30 Гиг флоат =).
Итого примерно 30 Гиг ответов и вход адрес 3 инт вектора…
Puporev, Этот код разве не быстрей?
Найти координаты центра окружности по трём точкам
йот, Берите 9 строк аналитики и находит центр точно без фантастических размеров базы данных.

0

Excalibur921, По моему тоже, только вид сбоку.

0

Ну давайте посчитаем если не пропустил ничего =).
Ваш код:
18 сложений \вычитаний
18 умнож\делений
36 действий

По моей ссылке:
15 сложений \вычитаний
13 умнож\делений
28 действий
Явно быстрей. Хоть это и voodoo math.

0

0

Igor3D, Есть расчет быстрей?

Сообщение от Excalibur921 По моей ссылке: 15 сложений \вычитаний 13 умнож\делений 28 действий

Какие-то барицентрические или прочая экзотика…
Допустим вход 3 вектора флоат выход 1 вектор флоат. Быстрей 28 математических есть метод?

0

https://ru.wikipedia.org/wiki/Описанная_окружность
Казалось бы мелкий расчет да?

Вот прикинем все что математики не написали то программистам огребать =)
Набросал код лень проверять...он уже проиграл.
rA rB rC вершины
a=Sqrt((rBx-rCx)^2+(rBy-rCy)^2) длина BC
b=Sqrt((rAx-rCx)^2+(rAy-rCy)^2) длина AC
c=Sqrt((rAx-rBx)^2+(rAy-rBy)^2) длина AB
p=(a+b+c)/2
S=Sqrt(p*(p-a)*(p-b)*(p-c))
A0=8*S^2
A1=a^2/A0
A2=b^2/A0
A3=c^2/A0
Aax=A1*(rAx-rBx)
Aay=A1*(rAy-rCy)
Abx=A2*(rBx-rAx)
Aby=A2*(rBy-rCy)
Acx=A3*(rCx-rAx)
Acy=A3*(rCy-rBy)
r0x=Aax*rAx+Abx*rBx+Acx*rCx
r0y=Aay*rAy+Aby*rBy+Acy*rCy
24 сложений\вычитаний
33 умножений\делений\корней
57 действий Ого..
А что если тот код по моей ссылке самый быстрый в мире?

0

йот, Утратили интерес к задаче? Нужны хоть примерно макс\мин возможные координаты вершин и точность центра окружности.

0

Excalibur921
я не утратил интереса к своей теме... я разрабатываю более
быстрый алгоритм решения... по сути прямое решение...
кажется... я нашел...

Добавлено через 3 минуты
Можете поместить одну вершину прямо в центр
Декартовой системы координат... это ускорит решение...

0

А это секрет?

Сообщение от Excalibur921 Нужны хоть примерно макс\мин возможные координаты вершин и точность центра окружности.

0

Excalibur921,
Это не секрет... я даже не подумал об этом...
Примените масштабирование... а сам треугольник
в отношении (большая сторона)/(малая сторона) < 2
...
то есть треугольник более похож на равносторонний...
тут целая теория о Степени подобия треугольников.
Вот пример... даны два треугольника с углами A1; B1; C1
и A2 B2 C2... углы заданы в порядке возрастания
D - Степень подобия треугольников... тогда
D = |A1 - A2| + |B1 - B2| + |C1 - C2| (это определение)
вывод: при D = 0 треугольники подобны...

0

Найти длины всех сторон.
Найти макс длину стороны MaxL0.
Найти макс длину стороны из двух оставшихся сторон MaxL1.
Найти какой вершине (хранить имя в A0) треугольника принадлежат эти стороны.
Найти угол Alfa0 между сторонами MaxL0 MaxL1 при A0.
Пересчитать длину в долях от наибольшей MaxL1New=MaxL1/MaxL0

Теперь любой треугольник можно представить так:
MaxL0 будет лежать на OX и длинной 1.
Зная Alfa0 и длинну MaxL1New отложить от ОХ против часовой и найти координаты точки P.

Поскольку MaxL1New всегда <1 то любой треугольник покажет точку принадлежащую сектору круга.
Осталось разбить это поле сеткой точек в которых нужно аналитически посчитать центр описанной окружности заранее и сделать базу данных ответов.

Работает так:
1)Задан произвольно ABC.
2)Нашли вершину треугольника в закрашенной области (красная P).
3)Округлили ее координаты( к какому узлу сетки она ближе Фиолетовая) и получили адрес (i,j) в котором ответ координаты центра окружности вокруг этого мелкого треугольника точка M.
4)Ставим M в этом мелком треугольнике масштабируем и крутим треугольник обратно.
5)Получили центр M найденный по аналитически заданным двум вершинам, а третья округлена. База данных очень мелкая.
Вопрос только будет ли это быстрей чем 28 действий.

1

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

0

Сообщение от йот хотел применить случайные числа

Какие случайные числа? Здесь их нет. Ничего не поняли? =\.

Не знаю что за теории...может так проще?
Если есть два близких +- Delta по значению угла то это равнобедренный.
Если все углы близки к 60+- Delta градусов то равносторонний.
Если один угол близок к 90+- Delta град то прямоугольный.
Поскольку все эти 3 вида крайне редкие…то смысл?
Если только у вас не огромная Delta. Всеравно выпадает огромное количество других случаев.

Метод что я описал выше перемалывает любые треугольники… вопрос в скорости и оптимизации математики.

Была идея что всякий треугольник это равносторонний+некая деформация сдвига+ деформация масштабирования вдоль некоторой линии. Может тут как то подойти…найти их величину, посчитать для равностороннего и применить трансформации к центру описанной окружности.Тут нужен взгляд математика.

А этот самый простой и быстрый:

Сообщение от Excalibur921 1)Координаты в 2д разбить сеткой

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

Сообщение от йот (большая сторона)/(малая сторона) < 2

Кстати тогда и поле меньше:

1

Координаты вершин треугольника от 0 до 5 с плавающей.
Сетка точек 5 на 5.
a=round(x(A)) //округляет до целых
b=round(y(A))
c=round(x(B))
d=round(y(B))
e=round(x(С))
f=round(y(С))
Вот тут хитрая задачка, нужна функция возвращающая уникальное число для уникальной комбинации a,b,c,d,e,f.
Получим уникальное число f(a,b,c,d,e,f)=a + 5*b+25*c+125*d+625*e+3125*f
А может так правильно?
a + 10*b+100*c+1000*d+10000*e+100 000*f

Массив M[i] по адресу i содержит 2д вектора центров описанных окружностей посчитаны заранее для треугольников по точкам A(a,b),B(c,d),C(e,f).

Работает так:
Округляем координаты вершин получаем a,b,c,d,e,f.
Получаем уникальное число f(a,b,c,d,e,f).
Читаем ответ M[f(a,b,c,d,e,f)] =центр описанной окружности.
Почему то математики не хотят ничего сказать =(.

Итого: 16 действий и база данных + грубый ответ против 28 действий аналитика есть ли смысл?

1

Сообщение от Excalibur921 есть ли смысл?

Товарищ изобретает велосипед, ну хочется ему, это бывает.

0

Если найдете такое уравнение, то есть идея как еще можно попробовать сделать поиск центра.
Нужна формула поверхности z=f(x,y) похоже на однополостный гиперболоид со сдвигом


или другая формула рисующая похожую поверхность просто.
Конкретно нужны только эти участки:

Есть идеи?

0

Сообщение от Excalibur921 Нужна формула поверхности z=f(x,y) похоже на однополостный гиперболоид со сдвигом

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

x = f(u, v)
y = f(u, v)
z = f(u, v)

Где u и v "параметры" меняющиеся с заданным шагом в заданных диапазонах. Напр полагаем v = 0, прогоняем u от 0 до 360 с швгом напр 10. Потом v = 1, опять прогоняем u и.т.д. Получившиеся "цепочки" соединяем полигонами. Начинаем с цилиндра

x = cos(u) * R
y = sin(u) * R
z = v

сдавливаем его в середке и двигаем по x напр так

x = cos(u) * R * (0.5 + cos(fabs(v - 5) / 10 * 30) + v;
y = sin(u) * R * (0.5 + cos(fabs(v - 5) / 10 * 30);
z = v

Вот и вся любовь

0