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

Я видел много алгоритмов для точки внутри многоугольника. То, что я узнал до сих пор, пришло с этого сайта: 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;
    }
}

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

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

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

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


c# point point-in-polygon polygons
person Eric Biron    schedule 19.01.2016    source источник
comment
У вас есть целые или плавающие координаты?   -  person Nico Schertler    schedule 19.01.2016
comment
координаты с плавающей запятой (двойные)   -  person Eric Biron    schedule 19.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

С этой строкой

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

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

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

minY < testY != maxY < testY

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

person Nico Schertler    schedule 19.01.2016
comment
Было непросто разбить дугу на монотонные части, потому что на одной стороне оси Y могло быть две части, но как только я ее нашел, это решило мою проблему. Танки - person Eric Biron; 14.07.2016