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

Question

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

Я хочу, чтобы формы при перетаскивании привязывались друг к другу, как две части головоломки (как в MS Word «Привязка к сетке»)

Как мне это сделать?

Ограничения:

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

Нет дальнейшего ввода пользователя: Пользователь не должен делать никаких действий, кроме открытия файла изображения и перетаскивания изображений.

Возможности:

Используйте какой-нибудь алгоритм вогнутой оболочки + упрощение, затем сопоставьте длину ребер. Проблема в том, что края пользователя не могут быть такими четкими / четко определенными.

Используйте преобразование Лапласа на компоненте прозрачности изображения (для обнаружения краев), затем обработайте эти области как положительно и отрицательно заряженные, и используйте физическое моделирование, чтобы найти, как они соединяются. Ограничение: Скорость, тюнинг.

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

Answer 1

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

Возьмите блоки тетриса. Каждый блок имеет контрольные точки на пересечении сетки, и каждая линия представляет собой прямую линию. Квадратная форма будет иметь 8 точек и линий, а L-форма будет иметь 10 точек / линий. Сначала сопоставьте контрольные точки, а затем сопоставьте, если одинаковые точки на каждой фигуре имеют линии между ними (и учитывают ориентацию линии).

Возьмите пазлы. Обычно у вас есть 4 точки / линии, но линии - это произвольные кривые. Вы можете на самом деле использовать математические кривые, но вы также можете иметь некоторый индекс кривой головоломки для каждой кривой. Когда вы сначала пытаетесь сопоставить две фигуры, вы сопоставляете контрольные точки, а затем сопоставляете кривые, просто сравнивая их индексы с точки зрения как ориентации линий, так и их парных индексов.