2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение30.07.2010, 12:14 
Предложу еще один способ нахождения центра окружности, основанный на векторной алгебре.
Обозначим исходные точки $A$, $B$, $C$, начало координат $O$, центр искомой окружности $S$.
Также обозначим $\overline{CA}=\overline{a}$, $\overline{CB}=\overline{b}$, скалярное произведение $\overline{a}$ и $\overline{b}$ - $\langle \overline{a},\overline{b}\rangle=p$. Единичный вектор, сонаправленный с данным, будем обозначать $\overline{v}_e=\frac{\overline{v}}{v}$, где $v$ - модуль вектора $\overline{v}$.
Требуется найти координаты точки $S$ или, что то же самое, компоненты вектора $\overline{OS}$.
Проекция вектора $\overline{a}$ на вектор $\overline{b}$ равна $\langle \overline{a},\overline{b}_e\rangle \overline{b}_e=\dfrac{\langle \overline{a},\overline{b}\rangle}{b} \dfrac{\overline{b}}{b}=\dfrac{p}{b^2}\overline{b}$. Тогда вектор, перпендикулярный вектору $\overline{b}$ и лежащий в плоскости $ABC$, можно представить следующим образом: $\overline{b}_{\perp}=\overline{a}-\dfrac{p}{b^2}\overline{b}$. Аналогично $\overline{a}_{\perp}=\overline{b}-\dfrac{p}{a^2}\overline{a}$.
Вектор $\overline{CS}$ можно выразить так: $\overline{CS}=\dfrac{1}{2}\overline{a}+\alpha\overline{a}_{\perp}$, где $\alpha$ - некоторый вещественный коэффициент (данное равенство следует из определения серединного перпендикуляра). Аналогично $\overline{CS}=\dfrac{1}{2}\overline{b}+\beta\overline{b}_{\perp}$ (здесь $\beta$ - также некоторый вещественный коэффициент). Приравняем правые часть обоих равенств: $\dfrac{1}{2}\overline{a}+\alpha\overline{a}_{\perp}=\dfrac{1}{2}\overline{b}+\beta\overline{b}_{\perp}$. Группируя все вектора, коллинеарные $\overline{a}$, в одной части уравнения, а коллинеарные $\overline{b}$ - в другой, получим: $\left(\dfrac{1}{2}-\beta-\alpha\dfrac{p}{a^2}\right)\overline{a}=\left(\dfrac{1}{2}-\alpha-\beta\dfrac{p}{b^2}\right)\overline{b}$.
Так как вектора $\overline{a}$ и $\overline{b}$ неколлинеарны (иначе треугольник $\triangle ABC$ вырождается в отрезок), то последнее равенство имеет место только при условии справедливости системы уравнений
$\left\{\begin{array}{l}\alpha+\beta\dfrac{p}{b^2}=\dfrac{1}{2} \\ \beta+\alpha\dfrac{p}{a^2}=\dfrac{1}{2} \end{array} \right.$
Решая эту систему, находим коэффициент $\beta$:
$\beta=\dfrac{1}{2}\cdot\dfrac{a^2 b^2-b^2 p}{a^2 b^2-p^2}$
Искомый вектор $\overline{OS}$ равен
$\overline{OS}=\overline{OC}+\overline{CS}=\overline{OC}+\dfrac{1}{2}\overline{b}+\beta\overline{b}_{\perp}$.
В принципе, можно остановиться на этой формуле, с помощью которой легко находятся координаты точки $S$ в пространстве любой размерности, начиная со второй. Для ее реализации (на Pascal'е) проще всего создать запись (record), в которой бы хранились координаты точек и компоненты векторов, и написать 5 функций (или процедур): сложения, вычитания векторов, умножения вектора на число, скалярного произведения векторов и нахождения квадрата модуля вектора (для этих целей можно использовать и предыдущую функцию, т.к. $v^2=\langle \overline{v},\overline{v}\rangle$). В шестой процедуре необходимо последовательно раскрыть формулы для $\beta$ и $\overline{OS}$ с помощью первых пяти.
P.S. Если подставить выражение для $\beta$ в формулу $\overline{CS}$, получим следующую приятную для взора формулу:
$\overline{CS}=\dfrac{1}{2}\left(\dfrac{a^2 b^2-b^2 p}{a^2 b^2-p^2}\overline{a}+\dfrac{a^2 b^2-a^2 p}{a^2 b^2-p^2}\overline{b}\right)$.
P.P.S. Желающие могут также отвлечься от жары, подставив в последнюю формулу "раскрытые" значения векторов $\overline{a}=\overline{OA}-\overline{OC}$ и $\overline{b}=\overline{OB}-\overline{OC}$ с целью получения "симметричной" относительно $\overline{OA}$, $\overline{OB}$ и $\overline{OC}$ формулы для $\overline{OS}$.

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение30.07.2010, 20:29 
_viktor_ в сообщении #341561 писал(а):
интересно, а код такой программки где-нить остался? было бы очень кстати))

Где уж сохраниться перфокарточным носителям и распечаткам. Но алгоритм-то простой, всё по справочникам. Сначала местная система координат, потом общая…
А вот, похоже, Вам предложили довольно изящное решение...

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение31.07.2010, 11:58 
Аватара пользователя
вот решение в маткаде, которое предложил ewert.
берусь за кодинг)).
Изображение

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение31.07.2010, 16:50 
Маткадовские картинки выкладывать нельзя, иначе забанят!

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение31.07.2010, 17:31 
Аватара пользователя
vvvv,

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

_viktor_,

Вы, наверное, заметили, что Вам пишут старательно, красиво, удобочитаемо. Как бы правила приличия у нас такие. Ваша картинка особого смысла не имеет (как мне кажется: я пока не понял, для чего она). Вы хотите, чтобы знатоки маткада проверили Ваш скрипт? Вы хотите поделиться решением? Вряд ли здесь кому-то интересно мат-кад-решение (ветка математическая). Кто маткадом (Maplом, Mathematicой) пользуется, тот при нужде без труда спрограммирует.
 i  Ежели понадобится --- здесь рассказано, как набирать формулы.

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение31.07.2010, 19:32 
Аватара пользователя
AKM в сообщении #341806 писал(а):
Вы, наверное, заметили, что Вам пишут старательно, красиво, удобочитаемо. Как бы правила приличия у нас такие. Ваша картинка особого смысла не имеет (как мне кажется: я пока не понял, для чего она). Вы хотите, чтобы знатоки маткада проверили Ваш скрипт? Вы хотите поделиться решением? Вряд ли здесь кому-то интересно мат-кад-решение (ветка математическая). Кто маткадом (Maplом, Mathematicой) пользуется, тот при нужде без труда спрограммирует.

ОК, вас понял! а в картинке просто хотел показать готовые формулы для использования их в коде Pascal (если кому, как мне, пригодятся).
Однако, впредь буду использовать LATEX.

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение01.08.2010, 00:01 
_viktor_ в сообщении #341421 писал(а):
разбираюсь с барицентрическими координатами))

_viktor_,

что с ними разбираться? Формула $$
O=w_1\begin{pmatrix} x_1\\y_1\\z_1\end{pmatrix}
+w_2\begin{pmatrix} x_2\\y_2\\z_2\end{pmatrix}
+w_3\begin{pmatrix} x_3\\y_3\\z_3\end{pmatrix}\eqno(*)$$
говорит о том, что центр описанной окружности Вашего треугольника состоит на 50% (точнее, на $w_1$) из первой точки, на $w_2=$22% из второй, и на $w_3=$28% из третьей. Ну просто выбранный треугольник --- таков, 50/22/28.

И дальше, допустим, Вы пошли на рынок за абрикосами, и взяли треугольник с собой. Описанная окружность, естественно, потянулась вослед. И что случилось от этого перемещения с поворотом (когда Вы его в корзинку бросили)? А ничего! Проценты остались теми же самыми --- 50, 22, 28. А изменились эти штуки, типа $\begin{pmatrix} x_1\\y_1\\z_1\end{pmatrix}$, и остальные. А формула (*) --- работает! Заметьте, в ней явно разделены те неизменные проценты, и то, куда Вы пошли.

Понятно, что если треугольник Вам надоест, и Вы выбросите его в унитаз, формула будет продолжать жить и работать. Даже когда Вы спустите воду. И даже если Ваш знакомый космонавт полетит с треугольником на Луну. Эти самые $(x_i,y_i,z_i)$ изменятся страшно, но $w_i$ --- никак.

А что, другая формула не будет работать? Будет, конечно, если она правильная. Они, конечно, эквивалентны. Но неплохо бы привести ту другую формулу именно к виду (*), где отделены свободно летающие мухи от инвариантных $w_i$-котлет.

Также ясно, что если Вы вдруг разозлитесь и покурочите треугольник, то работать ничего не будет. Ну нет больше треугольника.

Я что, приревновал ewertово решение, которое Вы взялись программировать, и пропагандирую своё? Нет, это решение, как следует из темы, далеко не моё. Я бы, может, заподозрил бы ИСНа в авторстве, но подозреваю, что и он моложе барицентрических координат. И вспомнил-то я его не сразу, всё мудрил чего-то там...

На мой взгляд, программировать надо именно это решение, без всяких там СЛАУ. Другое дело, если задачка своей учебностью как-то заточена под СЛАУ. Но по жизни --- поступать надо барицентрично.

Отчего тогда ewert предлагает Вам систему линейную решить? А, наверное, чтоб Вы через это прошли, научились, всё поняли. Или какие-то другие, мне неизвестные, чисто методические соображения. Но если он будет настаивать, что так задачу программировать лучше, то я позову на помощь grisa... :oops:

 
 
 
 Re: Алгоритм нахождения координат центра окружности
Сообщение01.08.2010, 01:02 
Алексей К. в сообщении #341870 писал(а):
На мой взгляд, программировать надо именно это решение, без всяких там СЛАУ. Другое дело, если задачка своей учебностью как-то заточена под СЛАУ. Но по жизни --- поступать надо барицентрично.

Отчего тогда ewert предлагает Вам систему линейную решить?

Оттого, что изначально, насколько я помню, речь шла именно о программировании. И этот способ программирования -- наиболее дёшев. Прежде всего потому, что он менее всего требует размышлений, практически вообще не требует (а думать без необходимости -- вредно). И программка получается вполне и короткая, и быстродействующая.

 
 
 [ Сообщений: 23 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group