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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

РЕДАКТИРОВАТЬ: см. Комментарии ниже:

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

Если вы сказали «да», то как насчет этого?

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

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

Если a, b два вектора, таких что:

a = (a1, a2, a3)

b = (b1, b2, b3)

Тогда кросс-произведение

axb = (a2b3-a3b2, a3b1-a1b3, a1b2 - a2b1)

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

Итак, при условии, что у вас есть эти пункты по порядку:

a = (a1, a2)

b = (b1, b2)

c = (c1, c2)

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

A = (A1, A2) = ab = (b1-a1, b2-a2)

B = (B1, B2) = bc = (c1-b1, c2-b2)

и тогда вам нужна только третья координата AxB:

A1B2 - A2B1

или

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

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