Проблема: у меня есть две перекрывающиеся 2D-формы, A и B, каждая из которых имеет одинаковое количество пикселей, но отличается по форме. Некоторая часть фигур перекрывается, и есть некоторые части каждой, которые не перекрываются. Моя цель - переместить все неперекрывающиеся пиксели в форме A на неперекрывающиеся пиксели в форме B. Поскольку количество пикселей в каждой форме одинаково, я смогу найти отображение 1 к 1 для пикселей. Ограничение состоит в том, что я хочу найти отображение, которое минимизирует общее расстояние, пройденное всеми перемещенными пикселями.
Грубая сила: метод грубой силы для решения этой проблемы, очевидно, исключен, поскольку мне пришлось бы вычислить общее расстояние всех возможных сопоставлений, которых, как мне кажется, существует n! (где n - количество неперекрывающихся пикселей в одной форме), умноженное на вычисление расстояния для каждой пары точек в отображении, n, что в сумме дает O (n * n!) или что-то подобное.
Отслеживание с возвратом. Единственное «лучшее» решение, которое я мог придумать, - это использовать отслеживание с возвратом, при котором я мог бы отслеживать текущий минимум на данный момент и в любой момент, когда я оцениваю определенное сопоставление, если я достигнув или превзойдя этот минимум, я перехожу к следующему отображению. Даже это не поможет, чем O (n!).
Есть ли способ решить эту проблему с разумной сложностью?
Также обратите внимание, что «очевидный» подход простого сопоставления точки с ближайшим совпадающим соседом не всегда дает оптимальное решение.
Более простой подход? В качестве второстепенного вопроса, если приемлемого решения не существует, одна из возможностей может заключаться в том, чтобы разделить каждую неперекрывающуюся секцию на небольшие области и сопоставить эти области, значительно уменьшив количество сопоставления. Чтобы рассчитать расстояние между двумя регионами, я бы использовал центр масс (среднее положение пикселей в регионе). Однако здесь возникает проблема, как мне следует делать разбиение, чтобы получить почти оптимальный ответ.
Любые идеи приветствуются !!
