заданные расстояния и направления между комбинациями точек

[AlexeiG]

Здравствуйте, помогите пожалуйста найти формулу или методику построения набора точек в двухмерном пространстве так чтобы параметры набора расстояний между комбинациями двух точек а также угол прямой их соединяющей можно было задавать
. Например создать группу точек так чтобы если мерять отрезки расстояния между всеми существующими комбинациями пар точек то они были 10 см для углов 0, 120, 240 потом 20 см для углов 0, 120, 240 и так далее.

[arseniiv]

Немного в сторону: если я правильно понял ваши два примера, они легко друг из друга получаются. Если все расстояния между точками из конечного множества умножить на одно и то же ненулевое число, а потом «одинаковым образом» наставить отрезков между теми точками и новыми точками, получатся подобные фигуры. Так что если одна построена, другая легко получится гомотетией (изменением масштаба). Разумеется, это только в таких редких случаях, как в примере.

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

-- Вс фев 23, 2014 00:48:41 --

На всякий случай уточним: вашу задачу можно свести к следующей (у вас неточное описание) или нельзя?:

Даны количество точек $n$, некоторое количество условий вида $|A_iA_j| = d_{ij}$ и условий вида $\angle A_iA_jA_k = \alpha_{ijk}$, притом величины углов берутся неориентированные. Найти какую-нибудь одну (или все?) конфигурацию из точек $A_1,\ldots,A_n$ на плоскости, удовлетворяющую данным условиям, или сказать о невозможности построения.

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

-- Вс фев 23, 2014 00:59:37 --

Под «или все» подразумевались или все с точностью до изометрий (преобразований, сохраняющих расстояния) плоскости.

[AlexeiG]

Перебор я уже пробовал но логика должна быть достаточно сложной так чтобы следующая фигура (набор точек) учитывал предьидущий набор точек так как он тоже будет включён в выборку пар. Пока я не смог этого сделать.
Наверное правильнее было написать :

$|\it A _i B _j| = d_k \ \ i\neq j$

$A_i B_j = \alpha _{ij}. \ \ d_k=f(ij)$
Проще пальцем показать :
Если строить график зависимости d от $\alpha$ то точки на нем будут создавать прямоугольную решетку типа
$ \[******\] \[******\] \[******\] $

Deggial: формулы поправил - обратите внимание на синтаксис.

[arseniiv]

То есть, углы вы берёте между вектором $\overrightarrow{A_iB_j}$ и каким-то фиксированным направлением? Для каждой пары неравных точек есть ограничения (притом оба), или не для всех? Подписаны ли на графике зависимости $d$ от $\alpha$, какая его точка описывает какие $(i, j)$, или это неизвестно?

AlexeiG в сообщении #829692 писал(а):

$|\it A _i B _j| = d_k \ \ i\neq j$

Вообще, неравенство индексов никак задачу не меняет — можно считать, что $d_{ii} = 0$, если обязательно надо задать все расстояния. А ещё такая запись бессмысленна из-за того что слева $i$ и $j$, а справа с какой-то стати $k$, связь которого с первыми нигде не описана. В итоге, такая переформулировка ничего полезного не внесла.

[AlexeiG]

Согласен, не меняет. Угол измеряется от оси Y. Ограничения существуют. В идеале хотелось бы получить однородное распределение точек для функции $d=f(\alpha)$. Если можно контролировать $\delta d$ и $\delta \alpha $ то ещё лучше. Простой пример - постройке окружность из 12 точек, выберите пары и померьте расстояние между точками а также угол каждой соединяющей линии. Потом постройке график зависимости дистанции от угла. Получится примерно как я хотелбы НО распределение точек на этом графике неравномерно то есть $\delta d\neq const$ . Хотелось бы найти алгоритм построения точек на плоскости где такие параметры можно контролировать.

[arseniiv]

Путём нехитрых преобразований, которые сразу приходят, как только сядешь посмотреть, задача сводится к следующей системе уравнений:

$$\begin{array}{ll} x_1 = y_1 = 0, & \\ x_j - x_i = c_{ij}, & i<j, \\ y_j - y_i = s_{ij}, & i<j, \end{array}$$

где $c_{ij} = d_{ij}\cos\varphi_{ij}$, $s_{ij} = d_{ij}\sin\varphi_{ij}$. Если точек $n$, в системе $2n$ неизвестных и $n(n-1) + 2$ уравнений. Уже начиная с трёх точек она рискует оказаться несовместной. Но это обычная СЛАУ, и решать её методы есть.

Один и тот же график отношения $d$ и $\varphi$ соответствует $(n(n-1)/2)!$ возможных условий, т. к. точки этого графика не помечены парами индексов точек, чьё это ограничение. Некоторые из этих $(n(n-1)/2)!$ условий эквивалентны, описывая повёрнутую вокруг $A_1$ систему точек, но, начиная с некоторого $n$, там будут обязательно и неэквивалентные, так что по каждому интересующему графику вам придётся решать несколько разных систем, ни одна из которых может при этом оказаться совместной.

Если численно решать, уже всё ясно. В символьном виде… тоже можно попытаться что-то исследовать, но я пас (или пока пас). У меня есть ничем не подкреплённая гипотеза, что никакой график в виде узлов прямоугольной сетки, рёбра которой параллельны осям координат, не соответствует никакому расположению точек при их числе больше 2 или какого-то другого конечного. Вот кажется… Так что если вас интересовали именно такие, а не чуть другие, вероятность провала как будто больше. Насчёт «наклонных» таких графиков никаких предположений нет.

-- Вт фев 25, 2014 03:09:21 --

Хотя, вообще-то, из вида уравнений той системы кое-какие следствия о виде «решаемых» условий на $(d,\varphi)$ прямо так и следуют… но я лучше спать пойду. Найдите их сами, если я не ошибся.

-- Вт фев 25, 2014 03:10:25 --

(Подсказка: $x_3 - x_2 + x_2 - x_1 = x_3 - x_1$.)

[arseniiv]

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

-- Вт фев 25, 2014 15:34:40 --

А, и ещё: по-моему, разумнее график отношения $d$ и $\varphi$, если рисовать, делать полярным. Нагляднее.

[AlexeiG]

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