Алгоритм нахождения координат центра окружности

[_viktor_]

Привет! Помогите, разобраться!

Даны координаты трех точек в пространстве. Нужен алгоритм нахождения центра окружности проходящей через эти точки. Алгоритм планирую реализовать на языке Pascal.

[gris]

Формулу координат центра окружности легко вывести, да она и известна. Если точки не лежат на одной прямой, то

$$x_0=\frac{1}{4S}\begin{vmatrix} x_A^2 + y_A^2 & y_A & 1 \\ x_B^2 + y_B^2 & y_B & 1 \\ x_C^2 + y_C^2 & y_C & 1 \end{vmatrix} \qquad y_0=-\frac{1}{4S}\begin{vmatrix} x_A^2 + y_A^2 & x_A & 1 \\ x_B^2 + y_B^2 & x_B & 1 \\ x_C^2 + y_C^2 & x_C & 1 \end{vmatrix} $$

Распишите определители по звёздочкам, а площадь треугольника по формуле Герона.

[mihailm]

у автора точки в пространстве

Вопрос автор умеет находить общее решение СЛАУ (случай неединственности решения)?

[Алексей К.]

Ну, давайте поищем. Запишем систему трёх уравнений

$$(x_i-X)^2+(y_i-Y)^2+(z_i-Z)^2=R^2,\quad i=1,2,3.$$

Этим мы ищем точки $(X,Y,Z)$, равноудалённые от трёх данных, т.е. прямую (ось цилиндра, в сечении которого имеется искомая окружность). Потом из этих точек найдём ближайшую, например, к $(x_1,y_1,z_1)$.
Такой у меня план решения.
Продолжить можете?


upd: Заменил обозначения $(A,B,C)$ на $(X,Y,Z)$.

[_viktor_]

mihailm в сообщении #341308 писал(а):

Вопрос автор умеет находить общее решение СЛАУ (случай неединственности решения)?

знаю что есть несколько алгоритмов реализации решений СЛАУ на языках высокого, но какой лучше всего использовать в нашем случае?

Алексей К. в сообщении #341311 писал(а):

Такой у меня план решения.
Продолжить можете?

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

-- Ср июл 28, 2010 17:09:31 --

нашел алгоритм нахождения центра окружности на плоскости http://algolist.manual.ru/maths/geom/equation/circle.php.
Подскажите, может проще будет привести 3D координаты точек в 2D плоскости на которой они лежат. Вычислить координаты центр окружности, и перевести их в 3D?

[mihailm]

_viktor_ в сообщении #341317 писал(а):

mihailm в сообщении #341308 писал(а):

Вопрос автор умеет находить общее решение СЛАУ (случай неединственности решения)?

знаю что есть несколько алгоритмов реализации решений СЛАУ на языках высокого, но какой лучше всего использовать в нашем случае?

Гаусса

Приводите идею Алексея К. к СЛАУ, решаете,
далее, находите по формуле уравнение плоскости, проходящей через Ваши три точки
ну и почти решено

[Алексей К.]

_viktor_ в сообщении #341317 писал(а):

представляю как это решить на бумаге карандашом, но не пойму как это реализовать в программном коде

Я обычно поступал так. Если что-то у меня уже написано на бумаге карандашом, например, $z=\sqrt{x^2+y^2}$, то я смотрел синтаксис соотв. языка программирования и писал что-то вроде (если на АЛГОЛе)

real x, y, z;
z := sqrt(x*x+y*y);

или, скажем, на PS

%  get x y from stack, push z: 
dup mul exch dup mul add sqrt

Так что предлагаю выписать бумажку про прямую $X(t),Y(t),Z(t)$ прямо здесь, потом пересечь здесь же с плоскостью. А потом попросимся в соседнюю ветку, там нам и закодировать помогут.
Подсказка (если не получается): сделаем замену $R^2=X^2+Y^2+Z^2+t$.

-- 28 июл 2010, 19:10 --

_viktor_ в сообщении #341317 писал(а):

Подскажите, может проще будет привести 3D координаты точек в 2D плоскости на которой они лежат. Вычислить координаты центр окружности, и перевести их в 3D?

Тоже неплохой вариант. Что проще --- мне трудно сказать.

[_viktor_]

Алексей К. в сообщении #341346 писал(а):

Подсказка (если не получается): сделаем замену .

спасибо!!! сейчас примусь за решение))

mihailm в сообщении #341321 писал(а):

Гаусса

ОК, его и возьму!

[Алексей К.]

Замечу, _viktor_, решение не предполагает программирование метода Гаусса. Вы не можете решить систему на компе, так как в неё входит ещё и неизвестный параметр $t$. Предполагается решение на бумажке (наверное, Крамером), потом определение $t$, подстановка его в найденные $X(t),Y(t),Z(t)$. Получается готовая формула (наверняка громоздкая, все эти определители там будут, и прочие штуки), и с этого момента начинается программирование.

Но вот барицентрические координаты пришли в голову...

-- 29 июл 2010, 11:25 --

Конечно! Надо решить плоскую задачу для $\triangle ABC$ со сторонами $a,b,c$ и выразить ответ в барицентрических координатах как

$$O=w_1A+w_2B+w_3C,\quad \text{где}\quad w_i=w_i(a,b,c),\quad w_1+w_2+w_3=1.$$

Всё должно быть или легко, или просто, или красиво. И применить к нашему пространственному тр-ку. И ответ наверняка в Инете ищется.

Гауссы, Крамеры, повороты в пространстве, --- во наворотили! Думалки от жары расплавились, похоже.

-- 29 июл 2010, 11:45 --

$$ w_1\sim a^2(b^2+c^2-a^2);\quad w_2\sim b^2(c^2+a^2-b^2);\quad w_3\sim c^2(a^2+b^2-c^2).$$

И сумму на единичку отнормировать. И всё.

[_viktor_]

Алексей К. в сообщении #341405 писал(а):

Замечу, _viktor_, решение не предполагает программирование метода Гаусса. Вы не можете решить систему на компе, так как в неё входит ещё и неизвестный параметр . Предполагается решение на бумажке (наверное, Крамером), потом определение , подстановка его в найденные . Получается готовая формула (наверняка громоздкая, все эти определители там будут, и прочие штуки), и с этого момента начинается программирование.

И все же... после приведения системы уравнений к линейной получаю:

$2x_iX+2y_iY+2z_iY+T=x_i^2+y_i^2+z_i^2$

Можно ли добавить еще одно уравнение для переменной T, из условия что, R – минимальное из возможных, или, что координаты искомой точки лежат на той же плоскости что и три остальные?

Стало интересно решить задачу разными способами! разбираюсь с барицентрическими координатами))

[mihailm]

_viktor_ в сообщении #341421 писал(а):

Можно ли добавить еще одно уравнение для переменной T, из условия что, R – минимальное из возможных, или, что координаты искомой точки лежат на той же плоскости что и три остальные?

Координаты искомой точки лежат на той же плоскости что и три остальные - это хорошая идея, добавляйте

[ewert]

Тупо и в лоб:

$(x_B-x_A)({x_A+x_B\over2}-x)+(y_B-y_A)({y_A+y_B\over2}-y)+(z_B-z_A)({z_A+z_B\over2}-z)=0$

$(x_C-x_A)({x_A+x_C\over2}-x)+(y_C-y_A)({y_A+y_C\over2}-y)+(z_C-z_A)({z_A+z_C\over2}-z)=0$

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

$\left|\begin{matrix}x-x_A & y-y_A & z-z_A \\ x_B-x_A & y_B-y_A & z_B-z_A \\ x_C-x_A & y_C-y_A & z_C-z_A \end{matrix}\right|=0$

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

[_viktor_]

ewert в сообщении #341428 писал(а):

Тупо и в лоб:





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

Спасибо!:) перевожу уравнения в СЛАУ

[alekcey]

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

[_viktor_]

alekcey в сообщении #341505 писал(а):

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

интересно, а код такой программки где-нить остался? было бы очень кстати))