Задача по оптимизации

mitgor

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

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

Niklz

конечно есть - рисуешь решётку, раскладываешь точки по ее узлам.

tester1

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

vadim_sv74

Это не преобразование пространства.

mitgor

Верно, забыл условие.
Как бы это сказать. Нельзя произвольно перемешивать точки. Для одномерного пространства, например, это означает что если точки лежат на прямой в порядке
... A B C D E ...
То после преобразования они не должны поменять порядок, т.е. вот так - нельзя:
... A B D C E ....

mitgor

Да, ограниченная.
И количество точек всегда ограничено.
А что такое перемешивающее отображение?
Возможно эту задачу можно решить многими способами, буду рад любым отсылкам к чему-то полезному для решения этого,

BSCurt

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

Suebaby

а например для двумерного

toxin

Можно использовать kd-деревья. Делишь область на две равные по количеству точек части горизонтальной прямой. С помощью растяжения/сжатия правой и левой части переносим ее в центр. Потом для каждой из частей проводишь перпендикулярную прямую и.т.д. Когда останавливаться зависит от того, насколько гладкое нужно отображение.

blackout

Я правильно понимаю, что при этом синий квадратик перейдет в синий, а красный в красный? Тогда, видимо, такое отображение даже не непрерывно гомеоморфизм.

lenmas

Я правильно понимаю, что при этом синий квадратик перейдет в синий, а красный в красный? Тогда, видимо, такое отображение даже не непрерывно гомеоморфизм.
По условию задачи требуемое отображение не может быть гомоморфизмом.

BSCurt

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

mitgor

ну, например, если любые два отрезка не пересекаются, то и после преобразования они не должны пересекаться
попробовал изобразить пример используя mad skills:

где искомые точки - точки пересечения линий

mitgor

Отличная идея!
Я вот думаю, что сработает еще и вот так: взять и поочередно для каждой координаты (x, y, z, ...) отсортировать их. Потом просто изменить каждую координату с индексом i в остортированном списке на coord_min + i * (coord_max - coord_mix)
А, нет, фигня. Если взять множество точек на прямой x=y то твой алгоритм его отработает на ура, а этот - нет.

tester1

А что такое перемешивающее отображение?
http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%BC%...

Suebaby

Отличная идея!
но не гарантирует сохранение пересечения отрезков

Vlad128

напиши лучше, откуда задача возникает

BSCurt

ну, например, если любые два отрезка не пересекаются, то и после преобразования они не должны пересекаться
Любое инъективное отображение это гарантирует.
Автор думай ещё.

tester1

инстинктивное отображение
что это? яндекс не помог.

BSCurt

Это слово инъективное после того как оно прошло через спеллчекер.

tester1

:grin:

toxin

Да, с непрерывностью у моего отображения плохо :( .

filippov2005

Чтобы обеспечить непрерывность, надо оставлять на месте ранее сдвинутые прямые деления - когда двигаем голубую линию, зеленая должна быть неподвижна. Можно, чем ближе мы к ранее сдвинутой прямой, тем меньше сдвигать точки так, что на самой прямой сдвиг будет уже нулевым. Даже гладко может получиться.
Правда точки вблизи прямых будут расположены плохо, но это небольшая часть от всех.
Оставить комментарий
Имя или ник:
Комментарий: