Карта расстояний

[GAGArin]

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

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

[tyomitch]

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

[GAGArin]

Спасибо. Думаю это лучше чем то что я хотел сделать. Вот только вопросик по привязыванию к плоскости. Это именно пружинки из начальной точки к её начальной проекции на плоскость, или все же сила всегда направленная к плоскости? По моему второй вариант обьективнее.

[tyomitch]

Да, второй.
Но сила не обычная, а пружинистая: пропорциональная модулю отклонения.

[Approximator]

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

У меня вопрос (последнее время я нередко сразу не ухватываю о чём именно идёт речь старею, видимо). Нужно отобразить трёхмерное многообразие в некое двумерное с сохранением топологических свойств? Из того, что мне известно "про математику", сие невзоможно (вААще).


Если же вам с Тёмычем удастся её решить, то объясните поподробнее (для таких, как я) как именно вы это сделали!?

Мне подойдёт объяснение, как вам это удалось, на примере всего-то четырёх точек, не лежащих в одной плоскости...

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

[GAGArin]

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

Мне нужно чтобы человек мог визуально работать с двумерной картой расстояний. Как она получена и какие "на самом деле" координаты его волновать не будет. На глазок ему погрешность 5-10% не сильно помешает. Учитывая что мерить что-то ему все равно придеться инструментами которые для этого будут даны, а не линейкой по монитору.

[uhm]

Согласен с Approximatorом, невозможно. И погрешность в 5-10%, боюсь, не получишь. Простейший пример - берем треугольную пирамиду, у которой все ребра равны. Получаем 4 точки, каждая из которых находится на расстоянии x от трех других. Как теперь такое отобразить на плоскости?

[tyomitch]

То, что задача не имеет решения, -- ещё не повод её не решать

[uhm]

Согласен, просто чтобы GAGArin сразу понял, что про точность в 5-10% можно забыть.

Я уже тоже заинтересовался темой. Пойду порешаю задачку, которую сам и задал - заодно можно получить оценку, лучше которой точность метода не может быть в худшем случае (вот интересно, кому-нибудь кроме меня понятно, что я этой фразой имел в виду? )

[uhm]

О, кстати, какой критерий оптимальности? Сумма квадратов отклонений длины проекции от длины самого ребра? Или максимум отклонения?

[Approximator]

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

Мне нужно чтобы человек мог визуально работать с двумерной картой расстояний. Как она получена и какие "на самом деле" координаты его волновать не будет. На глазок ему погрешность 5-10% не сильно помешает. Учитывая что мерить что-то ему все равно придеться инструментами которые для этого будут даны, а не линейкой по монитору.

Дык, штука-то в том, что задолбаешься уже на уровне ПРИДУМЫВАНИЯ критерия "близости". Когда топология меняется кардинально, критерий придётся изобретать тот ещё... Проще всего сделать простую проекцию, а вот метрику (организовать работу "измерительного инструмента") ввести особую. С однородной метрикой эта задача даже в "приблизительном виде", imo, не решается...