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

Question

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

альтернативный текст http://cl.ly/3228b0e7ea32b172e960/content

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

Answer 1

Возможно, вы захотите взглянуть на библиотеку геометрии Javascript Кевина Линдси - она ​​содержит, вероятно, все алгоритмы пересечения, которые вам нужны:

Answer 2

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

Answer 3

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

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

Answer 4

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