Задача о четырехугольнике

[dvb]

Формулировка:
Даны (четыре) точки пересечения со сторонами четырехугольника перпендикуляров, опущенных на стороны из точки пересечения его диагоналей. Построить четырехугольник.
Эта "простенькая" задачка преследует меня всю жизнь. Лично мне неизвестно
a) имеет ли она решение;
б) если да, то единственное ли:
О циркуле и линейке прошу не спрашивать. Хоть какое-то решение, например, итерационный алгоритм, но чтобы с гарантией сходимости.

[Vitalius]

Хм, на prima vista у меня в голове пришло вот что:

Пусть искомый четырёхугольник $ABCD$, а точка пересечения его диагоналей $AC$ и $BD$ - $K$. Ваши 4 заданные точки обозначим как $P$, $Q$, $R$ и $S$. Разумеется все они лежат в одной плоскостью. Предположим, что $P\in AB$, $Q\in BC$, $R\in CD$ и $S\in AD$. В плоскостью четырёхугольника $PQRS$ вводим прямоугольную координатную систему с центром в точке $O$ и осы $x$ и $y$. Дополним эту координатную систему до полной ортонормированной системе координат, в которую ось $z$ проходит чрез точку $O$ и перпендикулярна к $PQRS$. Согласно условия Вашей задачи можем считать, что радиус-векторы $\vec r_{P}\equiv(x_{P},y_{P},0)$, $\vec r_{Q}\equiv(x_{Q},y_{Q},0)$, $\vec r_{R}\equiv(x_{R},y_{R},0)$ и $\vec r_{S}\equiv(x_{S},y_{S},0)$ - заданы. Требуется найти 5 радиус-векторов $\vec r_{A}\equiv(x_{A},y_{A},0)$, $\vec r_{B}\equiv(x_{B},y_{B},0)$, $\vec r_{C}\equiv(x_{C},y_{C},0)$, $\vec r_{D}\equiv(x_{D},y_{D},0)$ и $\vec r_{K}\equiv(x_{K},y_{K},0)$, так, чтобы выполнялись условия Вашей задачи. Теперь могу сказать то, что у меня пришло в голове, как сказал - на prima vista. Искомые 10 координат будут решения следующей системе уравнений:

$(\vec r_{A}-\vec r_{B})\cdot(\vec r_{P}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{C})\cdot(\vec r_{Q}-\vec r_{K})=0,$

$(\vec r_{C}-\vec r_{D})\cdot(\vec r_{R}-\vec r_{K})=0,$

$(\vec r_{D}-\vec r_{A})\cdot(\vec r_{S}-\vec r_{K})=0,$

$(\vec r_{A}-\vec r_{K})\times(\vec r_{C}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{K})\times(\vec r_{D}-\vec r_{K})=0,$

$(\vec r_{A}-\vec r_{C})\times(\vec r_{C}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{D})\times(\vec r_{D}-\vec r_{K})=0,$

$|\vec r_{A}-\vec r_{C}|=|\vec r_{A}-\vec r_{K}|+|\vec r_{C}-\vec r_{K}|,$

$|\vec r_{B}-\vec r_{D}|=|\vec r_{B}-\vec r_{K}|+|\vec r_{D}-\vec r_{K}|.$

[mishafromusa]

Программа geogebra сможет Вам помочь разобраться в этой задачке. Посмотрите http://www.geogebra.org Похоже, что задачка решабельная, по крайней мере когда четырёхугольник близок к прямоугольнику. Это можно усмотреть следующим образом. Пусть А, B, C и D -- точки, данные в условиях задачи. Возьмём точку O и рассмотрим отрезки OA, OB, OC и OD. Проведя к ним перпендикулярны в наших 4-х точках, получим четырёхугольник. Пусть P -- точка пересечения его диагоналей. Таким образом возникает отображение, переводящее точку O в точку Р. Очевидно, что когда наш четырёхугольник -- прямоугольник, а заданные точки -- середины его сторон, пересечение диагоналей -- неподвижная точка нашего отображения, а производная около этой точки отображения, переводящего O в P-O, как легко видеть, невырождена. Наше отображение зависит от данных точек, как от параметров, поэтому, по теореме о неявной функции уравнение P=O будет иметь единственное решение и при конфигурациях, близких к прямоугольнику. Это решение можно найти численно, скажем, по методу сопряжённых градиентов. Элементарнго геометрического решения я пока не придумал, хотя идеи есть.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

mishafromusa, замечание за неоформление формул $\TeX$ом

[Skeptic]

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

[dvb]

mishafromusa в сообщении #887619 писал(а):

Элементарнго геометрического решения я пока не придумал, хотя идеи есть.

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

Vitalius в сообщении #887608 писал(а):

Искомые 10 координат будут решения следующей системе уравнений:

Системка недурна, особенно приятны модули в последних уравнениях...

[mishafromusa]

Skeptic в сообщении #887710 писал(а):

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

В задаче задаются не перпендикуляры, а только их основания. В вашем рассуждении присутствует точка $O$ пересечения полудиагоналей, которую надо подобрать так, чтобы из полудиагоналей сложились диагонали, т.е. чтобы наклоны противоположных полудиагоналей были равны. Это условие даёт 2 уравнения с двумя неизвестными (координатами точки $O$), которые однозначно разрешимы, если заданные основания перпендикуляров близки к серединам сторон некоторого прямоугольника.

-- 15.07.2014, 12:40 --

mishafromusa в сообщении #887737 писал(а):

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

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

[g______d]

Пусть данные точки $P$, $Q$, $R$, $S$. Назовём точки $A$ и $B$ сопряжёнными относительно отрезка $PQ$, если углы $APB$ и $AQB$ прямые. Другой способ: построили описанную окружность около $APQ$, провели диаметр из точки $A$, тогда другой конец этого диаметра будет точкой $B$, сопряженной к $A$.

Ясно, что нужно найти такую точку (пересечения диагоналей) $O$, что прямая, соединяющая точки, сопряжённые к $O$ относительно $PQ$ и $RS$, проходит через $O$. И то же условие для пары $QR$ и $SP$. Для первого условия окружности, описанные около $PQO$ и $ORS$, будут касаться друг друга. Следовательно, $O$ лежит на ГМТ общих точек касания касающихся окружностей, одна из которых проходит через $P$ и $Q$, другая – через $R$ и $S$. Ясно, что это ГМТ будет какой-то одномерной кривой, скорее всего окружностью. Т. е. условие для отрезков $PQ$ и $RS$ сводится к тому, что $O$ лежит на некоторой окружности. И ещё одно условие для второй пары отрезков, получаем в случае общего положения пересечение двух окружностей. Зная точку $O$, четырёхугольник восстановить очень легко.

[mishafromusa]

Именно это решение я и печатал, когда оно появилось в исполнении g______d

-- 15.07.2014, 14:16 --

Возьмём выпуклый четырёхугольник $EFGH$. Пусть $O$ -- точка пересечения его диагоналей $EG$ и $FH$, а $OA,OB,OC$ и $OD$ -- перпендикуляры, опущенныe из $O$ на стороны $HE$, $EF$, $FG$ и $GH$ соответственно. Эти перпендикуляры разбивают наш четырёхугольник на 4 четырёхугольника . Рассмотрим один из них, скажем, $OAEB$. В нём углы $A$ и $B$ -- прямые, поэтому все его вершины лежат на окружности $C_E$ с диаметром $OE$. Обозначим через $C_F, C_G, C_H$ три другие аналогичные окружности. Очевидно, окружности $C_E$ и $C_G$ касаются в точке $O$, как и окружности $C_F$ и $C_H$. Далее решение следует по схеме, указанной g______d с ГМТ касания пар окружностей, имеющих противоположные стороны прямоугольника $ABCD$ своими хордами.

Кстати, я ещё не сообразил что за кривые эти ГМТ. Понятно, что в случае прямоугольника это просто отрезки прямых, соединяюще середины его противоположных сторон. В общем случае точки пересечения этих ГМТ со сторонами четырехугольника $ABCD$ можно построить циркулем и линейкой.

[_Ivana]

Простите, соблазн был велик В теге оффтопа Матлабовский код, желающие могут поиграться с начальными данными. Единственный предполагаемый минус - записывал уравнения прямых в "школьном" виде, при вертикальных сторонах финального четырехугольника будет ошибка деления на ноль.

(Оффтоп)

function Main()
clear all; close all;

P = [-11, -7;
    -2, 13;
    4, 1;
    0, -8];

    function r = diagonal_conditions(p0)
        k = (p0(1) - P(:, 1))./(P(:, 2) - p0(2));
        b = P(:, 2) - k.*P(:, 1);
        k = [k; k(1)]; b = [b; b(1)];
        for ii = 2:numel(k)
            z = k(ii) - k(ii-1);
            pv(ii-1, 1) = (b(ii-1) - b(ii))/z;
            pv(ii-1, 2) = (b(ii-1)*k(ii) - k(ii-1)*b(ii))/z;
        end
        r = [p0(2)*(pv(3, 1) - pv(1, 1)) - p0(1)*(pv(3, 2) - pv(1, 2)) - pv(1, 2)*pv(3, 1) + pv(1, 1)*pv(3, 2);
             p0(2)*(pv(4, 1) - pv(2, 1)) - p0(1)*(pv(4, 2) - pv(2, 2)) - pv(2, 2)*pv(4, 1) + pv(2, 1)*pv(4, 2)];
    end

pv = zeros(4, 2);
P0 = fsolve(@diagonal_conditions, [mean(P(:, 1)), mean(P(:, 2))]);

figure(1); axis on, axis equal, grid off, hold on
plot(P(:, 1), P(:, 2), 'ok', 'LineWidth', 2);
plot(P0(1), P0(2), 'or', 'LineWidth', 4);
pv = [pv; pv(1, :)];
plot(pv(:, 1), pv(:, 2), '-ob');

plot([pv(1, 1), pv(3, 1)], [pv(1, 2), pv(3, 2)], '-g');
plot([pv(2, 1), pv(4, 1)], [pv(2, 2), pv(4, 2)], '-g');
plot([P0(1), P(1, 1)], [P0(2), P(1, 2)], '-k');
plot([P0(1), P(2, 1)], [P0(2), P(2, 2)], '-k');
plot([P0(1), P(3, 1)], [P0(2), P(3, 2)], '-k');
plot([P0(1), P(4, 1)], [P0(2), P(4, 2)], '-k');

end

[Vitalius]

Проще будет вот та система квадратичных форм для 10 неизвестных координат $x_{A}$, $y_{A}$, $x_{B}$, $y_{B}$, $x_{C}$, $y_{C}$, $x_{D}$, $y_{D}$, $x_{K}$ и $y_{K}$:

$(\vec r_{A}-\vec r_{P})\cdot(\vec r_{P}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{P})\cdot(\vec r_{P}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{Q})\cdot(\vec r_{Q}-\vec r_{K})=0,$

$(\vec r_{C}-\vec r_{Q})\cdot(\vec r_{Q}-\vec r_{K})=0,$

$(\vec r_{C}-\vec r_{R})\cdot(\vec r_{R}-\vec r_{K})=0,$

$(\vec r_{D}-\vec r_{R})\cdot(\vec r_{R}-\vec r_{K})=0,$

$(\vec r_{D}-\vec r_{S})\cdot(\vec r_{S}-\vec r_{K})=0,$

$(\vec r_{A}-\vec r_{S})\cdot(\vec r_{S}-\vec r_{K})=0,$

$(\vec r_{A}-\vec r_{K})\times(\vec r_{C}-\vec r_{K})=0,$

$(\vec r_{B}-\vec r_{K})\times(\vec r_{D}-\vec r_{K})=0.$

Она удовлетворяет условия задачи ТС. И все 10 уравнения в ней вроде независимы.

[Skeptic]

mishafromusa в сообщении #887737 писал(а):

В задаче задаются не перпендикуляры, а только их основания. В вашем рассуждении присутствует точка $O$ пересечения полудиагоналей, которую надо подобрать так, чтобы из полудиагоналей сложились диагонали, т.е. чтобы наклоны противоположных полудиагоналей были равны. Это условие даёт 2 уравнения с двумя неизвестными (координатами точки $O$), которые однозначно разрешимы, если заданные основания перпендикуляров близки к серединам сторон некоторого прямоугольника.

Перпендикуляры заданы точками концов. Пересечение диагоналей не задано. Предположим, что диагонали пересекаются в точке пересечения перпендикуляров, тогда наклон диагонали определяется двумя соседними перпендикулярами. Если наклоны диагоналей, построенных на противоположных парах перпендикуляров равны, то точки пересечения перпендикуляров и диагоналей совпадают. Нет никаких неизвестных, имеется одно равенство, требующее проверки.

[ex-math]

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

[mishafromusa]

Vitalius в сообщении #887832 писал(а):

Проще будет вот та система квадратичных форм для 10 неизвестных координат

Можно и так, но это менее наглядно. Эта система, конечно, легко решается при помощи базиса Гребнера.

[_Ivana]

Доработал код, теперь считает и вертикальные стороны, убрал цикл - сделал все по-Матлабовски векторно. Кому интересно - у меня решается система с 2 неизвестными (координаты пересечения диагоналей, остальное выражается через них). Матлабовский синтаксис некорректно отображает мой код, поэтому в теге "code".

(Оффтоп)

function Main()
clear all; close all;

P = [-11, -7; -20, 13; 4, 10; 1, -8];
% P = [-2, 0; 0, 1; 2, 0; 0, -1];
% P = [-1, -2; -1, 2; 1, 2; 1, -2];

    function r = diagonal_conditions(p0)
        a = p0(1) - P(:, 1);
        b = p0(2) - P(:, 2);
        c = a.*P(:, 1) + b.*P(:, 2);
        ac = circshift(a, -1);
        bc = circshift(b, -1);
        cc = circshift(c, -1);
        z = a.*bc - ac.*b;
        pv = [(bc.*c - b.*cc)./z, (cc.*a - c.*ac)./z];
        r = [p0(2)*(pv(3,1) - pv(1,1)) - p0(1)*(pv(3,2) - pv(1,2)) - pv(1,2)*pv(3,1) + pv(1,1)*pv(3,2);
             p0(2)*(pv(4,1) - pv(2,1)) - p0(1)*(pv(4,2) - pv(2,2)) - pv(2,2)*pv(4,1) + pv(2,1)*pv(4,2)];
    end

pv = zeros(4, 2);
P0 = fsolve(@diagonal_conditions, [mean(P(:, 1)), mean(P(:, 2))]);

figure(1); axis on, axis equal, grid off, hold on
plot(P(:, 1), P(:, 2), 'ok', 'LineWidth', 2);
plot(P0(1), P0(2), 'or', 'LineWidth', 4);
pv = [pv; pv(1, :)];
plot(pv(:, 1), pv(:, 2), '-ob');

plot([pv(1, 1), pv(3, 1)], [pv(1, 2), pv(3, 2)], '-g');
plot([pv(2, 1), pv(4, 1)], [pv(2, 2), pv(4, 2)], '-g');
plot([P0(1), P(1, 1)], [P0(2), P(1, 2)], '-k');
plot([P0(1), P(2, 1)], [P0(2), P(2, 2)], '-k');
plot([P0(1), P(3, 1)], [P0(2), P(3, 2)], '-k');
plot([P0(1), P(4, 1)], [P0(2), P(4, 2)], '-k');

end