Алгоритм морфинга 2D отрезка

Question

Создание игры-головоломки, в которой я хочу, чтобы формы изменялись на основе пользовательского ввода.Пользователь нажимает на вершину и перетаскивает точку, изменяя форму.Например, если пользователь нажимает на A и перетаскивает вниз (сокращение сегмента AG), точка B будет уменьшаться на равную величину (сокращение BC), точка F переместится влево, сокращая как AF, так и FG, и, наконец, точка E также сместится вслева, чтобы оставаться на одной линии с точкой F.

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

Я работаю над этим в течение двух дней и полностью в замешательстве.

                A
   B-------------\
    |           | \
    |           |  \
    |           |   \
    |           |    \
   C------------------\F
    |           G     |
    |                 |
    |                 |
   D-------------------E

Answer 1

Одновременные уравнения, не так ли?

Я предполагаю, что каждая линия должна сохранять свой наклон. Тогда ваша фигура удовлетворяет этим уравнениям (или почти этим уравнениям, я не уверен на 100% относительно наклона линии автофокусировки):

B.x = C.x = D.x

B.y = A.y

C.y = G.y = F.y

D.y = E.y

A.x = G.x

F.x = E.x

(A.y - F.y) = 2 (F.x - A.x)

Когда игрок перетаскивает A, тогда A.y и A.x фактически постоянны, поэтому у вас есть одиннадцать уравнений и двенадцать неизвестных. (Как указывает Бета, есть некоторые ограничения, потому что три уравнения B.x = C.x = D.x не относятся ни к одному из других, а также к D.y = E.y.)

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

• Пусть S будет набором переменных, которые мы сохраняем постоянными. Инициализируйте его пустым набором.
• Для каждой переменной V, если можно решить систему уравнений, сохранив переменные в S S {V}, добавьте V к S.
• Последнее найденное вами решение - это то, которое вы используете.

Answer 2

Как насчет этого ... в вашей загадке только треугольники, прямоугольники и квадраты? В этом случае вы можете разработать метод для работы с каждой формой в зависимости от того, какая вершина перемещается и какие фигуры зависят от движения этой вершины ... В вашем примере перемещение вершины A будет влиять на квадрат ABCG и треугольник AGF. Таким образом, когда A перемещается, вершина C остается неизменной ... вам нужно только "переставить" B и G. Если я не понимаю ваш пример неправильно, я не вижу, как перемещение A повлияет на F, хотя. НТН.

Answer 3

Моей первой мыслью было линейное программирование с симплексным алгоритмом, но я думаю, что это либо неправильно, либо, по крайней мере, неполно. По сути, большинство, если не все ваши правила являются линейными правилами "это равно", где линейное программирование имеет дело с правилами "это меньше, чем то" (или <= или что-то еще). </p>

Исправление может быть объединением. То есть выражайте свои правила WRT как можно меньшим количеством переменных. Если у вас есть правило f (a) = g (b), вы можете эффективно исключить b, определив b = g '(f (a)) и подставив его везде, где найдете b. Так как на самом деле замена неэффективна, вы можете просто отметить связь между a и b.

При незначительных осложнениях основной подход - поиск союза. В случае точного равенства вы удалили бы b, добавив ссылку из b в a. Когда вы «находите» b, вы вместо этого идентифицируете a (или то, с чем оно было связано). Таким образом, в любое время вы можете эффективно преобразовать любое правило в форму, в которой используются только неисчезающие переменные. Сложность в этом случае - вам нужно следить за вещами в стиле g '(f (a)), когда вы переходите по ссылкам. Поскольку все это линейно, это не должно быть такой большой проблемой, но и не тривиальным.

Возможно, вам понадобится иметь возможность откатить объединение - запишите ссылки, которые вы установили в стеке, чтобы вы могли снова обнулить их в правильном порядке при размотке стека.

Я не уверен, есть ли у вас какие-либо относительные условия (меньше или меньше), но если это так, как только вы удалите столько переменных, сколько возможно, вам все равно потребуется некоторое линейное программирование. Если у вас есть две оставшиеся переменные, это концептуально просто. Для каждого линейного условия на этих двух переменных нарисуйте линию на двухмерном графике так, чтобы одна сторона линии представляла действительную область. Условия традиционно «нормализуются», поэтому действительная сторона всегда включает происхождение. Исходя из точек пересечения, отрезки, ближайшие к началу координат, образуют выпуклый многоугольник. Оптимальное решение находится на одном из углов и оценивается с использованием линейного правила оценки (то, что вы оптимизируете), которое в вашем случае будет определено, чтобы придать «лучшую» форму, где есть некоторая неопределенность или некоторый конфликт приоритетов ваши правила - например Вы не можете протолкнуть точку через линию, поэтому в определенных точках все блокируется.

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

Это уже упрощено до такой степени, что, возможно, это неправильно в некоторых деталях, и это, насколько я могу объяснить. IIRC вы можете получить хорошие описания этих техник компонентов в Седжвике, хотя Википедия может быть столь же хороша в наши дни.

Симплексные решатели иногда используются для макетов окон - я думаю, что wxWidgets использует один для изменения размеров элементов управления в окне, например. Унификация является определяющей особенностью логического программирования (Пролог и т. Д.), Но лежащие в основе принципы поиска объединения достаточно просты. Ключевой трюк состоит в том, чтобы выяснить, как преобразовать 2D-фигуру в набор правил, выражающих, как она будет меняться, и понять, как представлять и управлять этими правилами, особенно в матричной форме.