алгоритм - обнаружение попаданий прямоугольника внутри повернутого прямоугольника

скриншот обреза внутри повернутого изображения

Я работаю над проектом редактора изображений, где вы можете вращать и обрезать изображение.

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

Может кто-то указать мне верное направление? Я лаю не на то дерево?


javascript algorithm geometry collision-detection coordinate
person daviestar    schedule 14.09.2017    source источник
comment
Проверьте, все ли четыре угла внутреннего прямоугольника находятся внутри внешнего прямоугольника.   -  person alain    schedule 15.09.2017
comment
Наивный метод состоит в том, чтобы проверять каждый сегмент линии меньшего прямоугольника, чтобы увидеть, пересекает ли он какой-либо сегмент большего прямоугольника. У вас есть точки для повернутого прямоугольника (при условии, что вы знаете угол поворота), так что это всего лишь 16 тестов пересечения линий. Не оптимально, но это начало. И если вы можете сделать некоторые предположения (например, левая сторона прямоугольника выбора не может пересекаться с правой стороной повернутого прямоугольника), вы можете уменьшить количество тестов, которые вам нужно сделать.   -  person Jim Mischel    schedule 15.09.2017

Ответы (2)


arrow_upward
2
arrow_downward

Воспользуйтесь комментарием Алена. Чтобы проверить внутреннюю часть углов, достаточно повернуть изображение в противоположных направлениях, чтобы его края выровнялись по осям. Тогда у вас есть простая проблема с коробкой, выровненной по оси.

введите здесь описание изображения

(Я не имею в виду, что вам действительно нужно вращать изображение, только геометрию.)

person Yves Daoust    schedule 15.09.2017
comment
спасибо, это гениально :) чуть более интенсивная операция обратного вращения может быть выполнена при наведении мыши, а затем при движении мыши я могу просто проверить, все ли 4 угла находятся в поле. большой! - person daviestar; 27.09.2017
comment
Интенсивный? Что ты имеешь в виду ? Это должно занимать менее 0,1 микросекунды. - person Yves Daoust; 27.09.2017
comment
собственные триггерные функции в javascript могут быть медленными, поэтому приятно, что ваш ответ позволяет мне стратегически кэшировать эти вычисления (при нажатии мыши) и не запускать их со скоростью 60 кадров в секунду (при перемещении мыши). каждая мелочь помогает в браузере! - person daviestar; 28.09.2017
comment
@daviestar: ИМО, 60 кадров в секунду — это вечность по сравнению со временем, которое требуется для оценки триггеров. И пока угол фиксирован, нет необходимости их пересчитывать. Этот код обнаружения попаданий - арахис. - person Yves Daoust; 28.09.2017

arrow_upward
0
arrow_downward

Если движение, которое пытается выполнить пользователь, равно [dx,dy], то рассмотрите сегменты линии от углов выделения до тех точек, которые переведены с помощью [dx,dy] (желтые линии в примере ниже). Эти линии могут пересекаться с границами повернутого изображения (зеленые линии) в определенных точках (красные точки). Если перекрестков нет, то движение разрешено. Если есть один или несколько перекрестков, они сообщат вам, до какой точки движение было законным; точка пересечения, ближайшая к исходному положению (достаточно проверки горизонтального или вертикального расстояния, чтобы установить это), определяет максимальное перемещение (нижний правый угол в примере). Затем вы можете ограничить перевод этой точкой.

перевод прямоугольного выделения

В зависимости от того, в каком квадранте находится направление движения (в примере вверху справа), вы можете пропустить проверку одного из углов (нижний левый угол в примере); другие углы всегда будут сталкиваться с границами первыми.
Вы также можете пропустить проверку двух границ (нижней и левой в примере), сравнив направление движения с углом поворота изображения.
Поэтому вам нужно проверить пересечение 3 отрезков с 2 отрезками. Код пересечения сегментов линий см., например, в этот вопрос.

Если пользователь перетаскивает только одну сторону и расширяет прямоугольник, а не перемещает его, вам нужно проверить только два движущихся угла.

person m69 ''snarky and unwelcoming''    schedule 15.09.2017