Как найти направление векторного пути

Question

У меня есть векторный путь (составленный из линий lineto, curveTo), и я хочу определить его направление (по часовой стрелке, против часовой стрелки).

Есть ли какой-либо алгоритм, который можно использовать для одного и того же?

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

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

Answer 1

EDIT: см комментарии ниже:

Что такое по часовой стрелке? Дело в точке. Считаете ли вы этот путь по часовой стрелке ?:

Если вы сказали да, то что об этом?

Следит мое первоначальное предложение, которое отлично работает для выпуклых путей:

Вы можете использовать декартово произведение 3D векторов.

Если а, б два вектора таким образом, что:

а = (а1, а2, а3)

Ь = (b1, b2, b3)

Затем перекрестный продукт

AXB = (a2b3-a3b2, a3b1-a1b3, A1B2 - A2B1)

Теперь, если вы предполагаете, что путь, который вы описали, не пересекает себя (что аннулирует точку по часовой стрелке или против часовой стрелки), то все, что вам нужно это первые три точки в том порядке, в котором они представлены. И из них вы создаете 2 вектора, чье поперечное произведение вы можете вычислить.

Так если у вас есть эти пункты в следующем порядке:

а = (а1, а2)

Ь = (b1, b2)

с = (с1 , c2)

Вы создаете следующие векторы:

А = (А1, А2) = AB = (b1-a1, b2-a2)

В = (В1, В2) = Ьс = (с1-b1 с2-b2)

, а затем все, что вам нужно, это третья координата Axb которая:

A1B2 - A2B1

или

(b1-a1) (c2-b2) - (b2-a2) (c1-b1)

Если эта координата положительна, то ваш путь против часовой стрелки, если он отрицательный, то он по часовой стрелке.

Answer 2

Выберите любую точку внутри компонента пути, а затем использовать правило заливки, чтобы определить, является ли его обмотки номер равен +1 или -1:

1. рисовать луч от точки до бесконечности
2. Начните с отсчетом нуля
3. Добавить 1 каждый раз, когда сегмент пути пересекает луч слева направо
4. Вычесть 1 каждый раз, когда сегмент пути пересекает луч справа налево

(Если компонент пути прост, то будет только одно пересечение. Если путь не прост, т. Е. Он пересекает себя, то это не означает ничего сказать, если он по часовой стрелке или нет.)

Тогда, так как вы хотите, чтобы компоненты по часовой стрелке ожидали числа +1. Счетчик -1 указывает, что компонент наизнанку.