Как вычислить точки пересечения линии и произвольной формы?

Есть ли способ геометрически вычислить точки пересечения линии и произвольного графического пути? Я знаю, где находятся все линии и кривые на пути, и я использую элемент холста HTML5, если это помогает. По сути, у меня есть доступ ко всем командам рисования холста и их аргументам. Например, если API был вызван с помощью lineTo, затем moveTo, затем дуги, у меня есть вся эта информация. Каждый вызов API хранится в массиве. У меня есть определение пути, я просто хочу выяснить, где линия пересекает путь. Ниже приведено изображение, показывающее пример точек, которые мне нужно найти.

альтернативный текст

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


javascript canvas algorithm geometry computational-geometry
person devongovett    schedule 19.06.2010    source источник

Ответы (4)


arrow_upward
8
arrow_downward

Возможно, вы захотите взглянуть на библиотеку геометрии Javascript Кевина Линдси — она содержит, вероятно, все алгоритмы пересечения, которые вы ищете: http://www.kevlindev.com/geometry/index.htm

person Quasimondo    schedule 20.06.2010

arrow_upward
0
arrow_downward

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

person Community    schedule 19.06.2010
comment
По сути, у меня есть доступ ко всем командам рисования холста и их аргументам. Например, если API был вызван с помощью lineTo, затем moveTo, затем дуги, у меня есть вся эта информация. Каждый вызов API хранится в массиве. У меня есть определение пути, я просто хочу выяснить, где линия пересекает путь. - person devongovett; 20.06.2010
comment
@devongovett: Я предлагаю добавить эту информацию к вопросу. - person Alceu Costa; 20.06.2010
comment
Таким образом, ваша проблема состоит в том, чтобы найти пересечение между линиями, определенными командами рисования холста javascript, и прямой линией. - person ; 20.06.2010

arrow_upward
0
arrow_downward

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

person Seth    schedule 19.06.2010

arrow_upward
0
arrow_downward

Вы хотите пересечь линию и «сплайн» x(t), y(t), который должен быть полиномом не более 4-й степени как для x(t), так и для y(t). Вы научились решать уравнения, но вам нужно знать все параметры. Если решение выходит за пределы любого диапазона (у сегмента линии и сегмента сплайна есть начало и конец), отмените его. Связанный вопрос:

Точка пересечения между сплайном и линией

person Hamish Grubijan    schedule 19.06.2010