Я успешно использовал номер обмотки: http://geomalgorithms.com/a03-_inclusion.html
Шаг 1. Определите направление рисования многоугольника.
По сути, многоугольник статичен и не имеет направления. Однако учтите движения, которые вы выполняете, когда рисуете многоугольник на листе бумаги. Вы начинаете с одной позиции и перемещаете ручку, чтобы нарисовать линию для каждой стороны многоугольника. Если вы не снимаете ручку с бумаги, все стороны многоугольника будут либо нарисованы по часовой стрелке, либо против часовой стрелки.
Мы можем использовать это «направление», чтобы определить, как стороны многоугольника «закручиваются» вокруг точки (по часовой стрелке или против часовой стрелки).
С реальным рассматриваемым многоугольником (который не был нарисован в направлении), не важно, в каком направлении вы считаете его нарисованным, но важно, чтобы каждая сторона считалась нарисованной в одном и том же направлении. .
Шаг 2. Рассмотрим каждую сторону многоугольника как отдельный объект с двумя вершинами.
Если мы знаем вершины многоугольника, мы можем определить конечные точки каждой стороны многоугольника.
Шаг 3: Определите направление, в котором каждая сторона пересекает точку (если стороны пересекают точку).
Пример использования намотки по часовой стрелке для определения, окружает ли многоугольник point:
Определите counter для отслеживания числа обмоток.
Для каждой стороны многоугольника возьмите первую вершину vertex1 и вторую вершину vertex2 (эти точки определяют конец каждой стороны).
Если vertex1.x <<code>point.x, то сторона начинается слева от point.x.
Если vertex2.x> point.x, то сторона заканчивается справа от point.x.
Если сторона начинается слева И заканчивается справа, линия пересекает точку.
Если сторона пересекает point, нам нужно определить, в каком направлении она пересекается.
Используя положительное направление по часовой стрелке, сторона должна пересекать отметку point, чтобы считаться положительной. Линия пересекается выше point, если значение y строки в позиции x point больше значения y * point. Иначе оно пересекает точку ниже.
Если оно пересекается выше, увеличить counter. Если оно пересекает ниже, уменьшите counter.
ПРИМЕЧАНИЕ: обратите внимание, что если линия проходит слева направо, то в положительном направлении линия проходит выше точки, но если линия идет справа налево (смещается назад под точкой), то в положительном направлении линия видна. пройти ниже точки. Положительное направление по часовой стрелке.
Теперь сделайте то же самое со следующей стороной многоугольника, где vertex1 будет vertex2 предыдущей стороны, а новый vertex2 будет следующим углом многоугольника при движении по часовой стрелке.
Сделайте это для всех сторон многоугольника.
В конце у вас будет счетчик с положительным, отрицательным или нулевым значением.
Если значение счетчика равно 0, многоугольник не содержит точку, в противном случае он содержит.
Это потому, что многоугольник, содержащий точку, всегда будет иметь четное число сторон, проходящих точку. Либо 2 стороны, либо 4 стороны и т. Д. Из этих сторон половина будет проходить слева направо над точкой, а половина - справа налево под точкой.
Результат 0 означает, что ни одна из сторон не проходит точку (следовательно, многоугольник никогда не пересекает ось точки), или многоугольник проходит по одной стороне точки в двух направлениях (например, выше точки слева направо, затем выше точки справа налево). Поэтому номера обмоток взаимно уничтожаются.