Перебирать точки произвольной формы
У меня есть мультикарта точек multimap<int,int> которая окружает (без промежутка) произвольную форму (конкретная территория). Как бы я перебрал все точки, содержащиеся в произвольной форме?
Я знаю, что мультикарты недостаточно для определения внутренних точек, поэтому у меня есть дополнительная точка, которая находится внутри фигуры (для определения внутренней и внешней части фигуры).
Дополнительная информация: точки отсортированы по оси x, потому что multimap — это отсортированный контейнер. Все точки расположены в сетке, потому что я использую растровые изображения.
Решение
-
Если ваши точки находятся дальше, чем 1 пиксель, то точки, отсортированные по координате х, не будут очень полезными. Сортируйте их так, чтобы точки, которые должны быть соединены, находились рядом друг с другом.
-
Найти точку, которая внутри и заливка форма. Если вы реализуете это самостоятельно, для этого вам нужно будет перебрать каждый пиксель внутри фигуры.
Другие решения
Один из тестов на предмет того, находится ли точка внутри / снаружи фигуры, состоит в том, чтобы представить луч от этой точки до точки, которая, как известно, находится за пределами фигуры. Посчитайте, сколько раз луч пересекает границу, если это число нечетное, то точка находится внутри фигуры, если ее четное значение, кроме точки, находится за пределами фигуры. Увидеть алгоритм наведения луча для точки в многоугольнике.
В вашем случае проще всего взять вертикальный луч, который имеет то же значение x, что и ваша контрольная точка, (x0,y0) сказать. Позволять (x0,y1) быть какой-то точкой за пределами ограничительной рамки вашей фигуры. Просто посчитайте количество точек в мультикарте с тем же значением x. Если это странно, вы внутри, если даже вы снаружи.
Вышеприведенное предполагает некоторые подробности о вашей границе фигуры: включена полная граница фигуры, поэтому, если фигура пересекает край вашего изображения, точки на краю включаются в мультикарту, также у вас нет двух смежных точек, поэтому (x,y), а также (x,y+1) не оба в мультикарте.