Нахождение минимального вектора переноса по точкам пересечения

Я создаю приложение на основе Paper.js.
У меня есть список элементов, каждый из которых состоит из группы верхнего уровня и множества дочерних путей.
Мне нужно реализовать обнаружение столкновений, которое в настоящее время работает следующим образом:

  1. Когда элемент перетаскивается, его компоненты (пути, из которых он состоит) сравниваются с любыми другими путями в том же слое с помощью метода Path#getIntersections(path).

  2. Если метод возвращает непустой массив (CurveLocations, которые описывают точки пересечения), я знаю, что произошло столкновение. Я перестаю перетаскивать и комбинирую элементы.

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

А теперь вот что мне нужно сделать на шаге 2:

При обнаружении столкновения мне нужно переместить элемент в ближайшую «правильную» позицию (ближайшую к текущей позиции мыши, не перекрывая какую-либо другую форму/границу).

Теперь я могу заняться реализацией SAT или GJK и решать их без метода getIntersections, но единственное, чего мне здесь не хватает, так это MTV (если не ошибаюсь).

Может кто-нибудь подтвердить, возможно ли это или нет, и если да, то как?

Обновлять

После некоторого возни с различными событиями мыши я пришел к текущему (несовершенному) решению:

  1. onMouseDown: сохранить смещение мыши (положение элемента минус положение мыши).

  2. onMouseDrag: проверка пересечений. Если это так, переместите перетаскиваемый объект с помощью event.delta.negate(), пока проверка возвращает true. Когда закончите, обновите смещение.
    Если пересечение не обнаружено, просто переместите перетаскиваемый элемент в позицию мыши минус смещение.

  3. onMouseUp: то же, что и в событии перетаскивания, за исключением того, что если столкновения не обнаружено, ничего не делать.

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


javascript geometry paperjs collision-detection vector-graphics
person dd_dent    schedule 29.01.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если у вас есть только две фигуры, и все они довольно близки к кругам и прямоугольникам и имеют одинаковые размеры, вы можете получить центр ограничивающей рамки фигур и использовать эти центральные точки в качестве вектора направления. Затем вы постепенно отодвигаете его, пока пересечения больше не будет. Но если у вас есть формы, такие как U или O, которые окружают другую меньшую форму, вероятно, этот метод не даст кратчайшего расстояния. То же самое, если удаляясь заденет другие объекты.

Поэтому я думаю, что вам действительно нужно численное решение, которое перемещает фигуру от ее центральной точки по окружности с растущим диаметром до тех пор, пока не останется никаких пересечений.

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

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

Edit2: Вторая пример, который проверяет пересечение и перемещает фигуру наружу. Как видите, одного пересечения недостаточно, чтобы проверить, становится ли препятствие больше, чем перетаскиваемый элемент.

person Christoph    schedule 30.01.2014
comment
Поэтому я думаю, что вам действительно нужно численное решение, которое перемещает фигуру от ее центральной точки по окружности с растущим диаметром до тех пор, пока не останется никаких пересечений. Вы имеете в виду ЭПРА? - person dd_dent; 30.01.2014
comment
Я не эксперт по SAT, EPA, GJK или MTV, но я добавил вам пример того, что я имел в виду. Его можно было бы оптимизировать, и он не очень эффективен для многих форм, но я думаю, что он работает. Теперь это все еще отсутствует циклическая идея. Но это было бы просто дополнением к способу перемещения круга. Может быть, это даже не нужно. - person Christoph; 30.01.2014
comment
Здесь вы можете увидеть, что я имел в виду: установить гравитацию и отскок на "нет" , установите максимальное трение и перетащите (удерживая пробел, зависая над мячом). Когда вы перетаскиваете поле в центре, вы можете увидеть необходимый эффект. Это делается с помощью реализации SAT. Мяч переводится в положение мыши, а MTV редактируется, поэтому он всегда выровнен по краю поля. Я хочу получить такое же расстояние (не постепенно) и применить его к положению перетаскиваемых элементов. - person dd_dent; 30.01.2014
comment
Исправление: я хочу получить MTV, используя точки пересечения (не используя SAT, GJK, EPA и т. д.). - person dd_dent; 30.01.2014
comment
Не думаю, что точек пересечения достаточно. Потому что вы потеряете их, когда мышь заберется далеко внутрь препятствия. Я добавил пример для этого. - person Christoph; 31.01.2014
comment
Проблема, о которой вы говорите, это сдерживание. Я думаю, что это можно решить с помощью метода Item#contains. В любом случае это может быть уже неактуально (см. мое последнее редактирование). - person dd_dent; 31.01.2014