Как "натянуть" одну фигуру на другую?

Kosat · 07/01/14 119

Есть одна фигура (пусть для простоты сначала в двумерном пространстве). И другая. Как совместить обе фигуры (можно изменять размеры, поворачивать), чтобы отображение было наиболее точным? Фигуры состоят из точек, пусть для простоты мы можем совместить (поставить в соответствие) несколько точек этих двух фигур. Что-то дальше моя фантазия не работает. У кого есть идеи?

arseniiv · 27/04/09 28128

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

UPD: значительно уконкретил вопросы.

Munin · 30/01/06 72407

Скорей всего, в конечном счёте всё упрётся в тот или иной вариант метода наименьших квадратов (МНК). Вопрос только в том, к чему его применять.

svv · 23/07/08 10910 Crna Gora

Kosat в сообщении #834729 писал(а):

У кого есть идеи?

Есть идея. Сначала надо научиться любую фигуру (из хорошего, «допустимого» класса) отображать на круг. Тогда нужное Вам отображение между двумя фигурами можно построить как композицию отображений «фигура 1 $\to$ круг» и «круг $\to$ фигура 2».

Kosat · 07/01/14 119

Большое спасибо всем, кто откликнулся.

arseniiv в сообщении #834742 писал(а):

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

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

svv в сообщении #834790 писал(а):

Kosat в сообщении #834729 писал(а):

У кого есть идеи?

Есть идея. Сначала надо научиться любую фигуру (из хорошего, «допустимого» класса) отображать на круг. Тогда нужное Вам отображение между двумя фигурами можно построить как композицию отображений «фигура 1 $\to$ круг» и «круг $\to$ фигура 2».

Как треугольник отобразить на круг? А из него получить другой треугольник? Строго той ориентации, что нужна (с расстоянием между вершинами наименьшей по МНК, например)? Меня интересует практическая часть. :((

arseniiv · 27/04/09 28128

Kosat в сообщении #834847 писал(а):

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

Спасибо.

Самый простой способ — можно, как сказал Munin, применить метод наименьших квадратов. Сразу к вершинам. Если у фигур совпадают количества вершин, и они даже каким-то образом пронумерованы, можно минимизировать сумму квадратов расстояний от точек фиксированной фигуры до точек подвинутой. Но, наверно, это вряд ли будет. Тогда можно минимизировать сумму квадратов расстояний от каждой точки первой фигуры до каждой точки второй.

Можно взять точки на серединах сторон фигур и использовать вместо вершин. (Не могу прикинуть, не то же ли это самое даст в результате.)

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

Если выбрать функцию неправильно, метод может предложить уменьшить размер фигуры до нуля и расположить на месте вершины другой.

Надеюсь, ниже будут советы получше.

-- Пн мар 10, 2014 19:13:07 --

А! Можно минимизировать площадь симметрической разности внутренностей фигур — тех областей, которые принадлежат одной из них, но не пересечению. Или максимизировать площадь пересечения. Вычислений чуть больше, но наивному представлению о «натягивании» фигур это соответствует, по-моему, намного лучше.

Pavia · 31/10/08 1244

Kosat

Kosat в сообщении #834847 писал(а):

Как треугольник отобразить на круг?

По определению?
Поставить все точки на контуре треугольника в соответствии всем точкам на контуре круга.

arseniiv · 27/04/09 28128

svv, Pavia, мне кажется, задача немного не о том. К тому же, аффинными преобразованиями (а тут их собственное подмножество) многоугольник и круг не совместить.

Kosat, вы, случайно, такими совмещениями не пытаетесь проверить, на какую фигуру из некоторого множества «похожа» данная?

Kosat · 07/01/14 119

arseniiv в сообщении #835053 писал(а):

svv, Pavia, мне кажется, задача немного не о том. К тому же, аффинными преобразованиями (а тут их собственное подмножество) многоугольник и круг не совместить.

Kosat, вы, случайно, такими совмещениями не пытаетесь проверить, на какую фигуру из некоторого множества «похожа» данная?

Задача и вправду не о том. Мы же постим в разделе Computer Science, а не Школьная геометрия... Я хочу понять, как это сделать НА ПРАКТИКЕ - я не понимаю алгоритм. Пусть у меня есть два треугольника (заданы вершинами на плоскости) - как их совместить наилучшим образом (например, в Matlab-e)? Интересует практическая сторона алгоритма (теоретическая идея про минимизацию площадей/расстояний мне понятна)...

Я такими совмещениями не пытаюсь проверить, на какую фигуру из некоторого множества «похожа» данная. Хотя эта задача и очень близка моей.

arseniiv · 27/04/09 28128

Kosat в сообщении #835091 писал(а):

Интересует практическая сторона алгоритма (теоретическая идея про минимизацию площадей/расстояний мне понятна)...

Вот берите формулы и пишите алгоритм — что останавливает? :roll:

Расскажите, поможем.

Kosat · 07/01/14 119

arseniiv в сообщении #835108 писал(а):

Kosat в сообщении #835091 писал(а):

Интересует практическая сторона алгоритма (теоретическая идея про минимизацию площадей/расстояний мне понятна)...

Вот берите формулы и пишите алгоритм, что останавливает? :roll:

Расскажите, поможем.

Так. Давайте ещё проще. Есть два отрезка. Мы один конец одного привязываем к концу другого - после этого вычисляем вектор направления первого отрезка и в этом направлении отсчитываем длину второго отрезка.

Теперь прибавляется ещё одна точка. Два треугольника (на плоскости). Уже такой же самой однозначности направления не наблюдается. Даже без зеркальных симметрий у нас уже три варианта привязки начальной точки второго треугольника к начальной точке первого (и бесконечное множество направлений первого отрезка второго треугольника). Пусть, как я и говорил раньше, каким-то чудом мы поставим в соответствие точки обоих треугольников. Но что дальше? Дальше имеем два вектора направления отрезков, выходящих из начальной точки первого треугольника (да и не факт, что если жёстко связать "первые" точки обоих треугольников, то результат будет наилучшим). Что мы делаем после этого? Непонятно.

Вот мне тут подсказывают, что есть такая штука, как Thin-Plate Spline transform. В Вики про неё нет (то, что есть: http://en.wikipedia.org/wiki/Thin_plate_spline). Кто-то что-то про неё знает?

Deformation is achieved using the Thin-Plate Spline transform (TPS). TPS is
a non-linear landmark transform that maps a set of landmarks (source landmarks)
to another set of landmarks (target landmarks). Mapping is achieved trough
interpolation and aims at minimizing a bending energy for ensuring that the
deformation is smooth and without discontinuities.

Pavia · 31/10/08 1244

Kosat
Пока вы не напишете, что надо найти? Мы вам помочь не сможем. Так как кроме вас этого никто не знает.
Тем более критерий по которому производить совмещение должны выбрать вы.
Чем вам не устраивает просто совместить центры масс?

Kosat в сообщении #835118 писал(а):

Вот мне тут подсказывают, что есть такая штука, как Thin-Plate Spline transform. В Вики про неё нет (то, что есть: http://en.wikipedia.org/wiki/Thin_plate_spline ). Кто-то что-то про неё знает?

А чем того что в википедии не достаточно? Там же ссылки есть даже с кодом.

Kosat · 07/01/14 119

Pavia в сообщении #835188 писал(а):

Kosat
Пока вы не напишете, что надо найти? Мы вам помочь не сможем. Так как кроме вас этого никто не знает.
Тем более критерий по которому производить совмещение должны выбрать вы.
Чем вам не устраивает просто совместить центры масс?

Kosat в сообщении #835118 писал(а):

Вот мне тут подсказывают, что есть такая штука, как Thin-Plate Spline transform. В Вики про неё нет (то, что есть: http://en.wikipedia.org/wiki/Thin_plate_spline ). Кто-то что-то про неё знает?

А чем того что в википедии не достаточно? Там же ссылки есть даже с кодом.

Так вроде я пытался объяснить, что мне нужно. Совместить две фигуры (для начала - два треугольника в двумерном пространстве), чтобы было "похоже" (хоть как-нибудь - на уровне практического алгоритма). Пусть соответствие (биекцию) вершин этих треугольников ( $A_1 \leftrightarrow B_1; A_2 \leftrightarrow B_2; A_3 \leftrightarrow B_3$ ) я введу вручную. Что мне даст нахождение и совмещение центров масс? Треугольники же можно вертеть вокруг них - и площадь взаимного наложения может быть совсем небольшой, и сумма расстояний между соответствующими вершинами может оказаться огромной...

В Википедии написано про Thin-Plate Spline, а не Thin-Plate Spline transform. Это одно и то же? Коды глянул, не увидел Matlab-овского, опечалился. В имеющихся кодах, как я понял, упор делается именно на TPS как аналог сплайнов (в трёхмерном пространстве?) - аппроксимацию имеющихся данных (набора точек?) функциями (многочленами высших порядков?). А мне же надо один набор точек привести к другому (формы фигур, представленных наборами, должны совпадать). Это же немного разные вещи, нет?

Pavia · 31/10/08 1244