Точка внутри составного многоугольника

Question

Я видел много алгоритмов для точки внутри многоугольника. То, что я узнал до сих пор, пришло с этого сайта: http://alienryderflex.com/polygon/

Лучший алгоритм обычно выглядит так:

var inside = false;
for (int i = poly.Count - 1, j = 0; j < poly.Count; i = j++)
{
    var p1 = poly.Vertices[i];
    var p2 = poly.Vertices[j];

    if ((p1.Y < testY != p2.Y < testY) && //at least one point is below the Y threshold and the other is above or equal
        (p1.X >= testX || p2.X >= testX)) //optimisation: at least one point must be to the right of the test point
    {
        if (p1.X + (testY - p1.Y) / (p2.Y - p1.Y) * (p2.X - p1.X) > testX)
            inside = !inside;
    }
}

Но составные сегменты многоугольника могут быть либо прямой линией, либо дугой. Сегменты дуги определяются двумя нормальными точками и выпуклостью, которая используется для нахождения центра и радиуса дуги. 2 точки используются для определения начального и конечного угла дуги.

Используя контрольную точку Y и Math.Asin((testY - arc.Center.Y) / arc.Radius) Я могу найти угол, под которым тестовая линия пересекает круг. Когда тестовая линия пересекает окружность, появляются 2 точки пересечения. После этого я проверяю угол, чтобы узнать, находятся ли точки пересечения на дуге.

Мой результат пока неплохой, за исключением того, что когда контрольная точка случается, точно такая же y как вершина. Он будет засчитан за 2 соседних сегмента. Для нормального сегмента этот случай исключается (p1.Y < testY != p2.Y < testY)

Я не могу найти аналогичную реализацию для составного многоугольника для части дуги. Кто-то когда-либо делал что-то подобное или имел какой-то намек?

Answer 1

С этой линией

p1.Y < testY != p2.Y < testY

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

Для этого может быть желательно разделить дугу на монотонные части (относительно оси y). В вашем примере нижняя дуга уже является монотонной. Верхняя дуга должна быть разбита на две части (вдоль вертикальной линии, проходящей через ее центр). Тогда у вас есть minY а также maxY для каждого сегмента можно применить приведенную выше формулу:

minY < testY != maxY < testY

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