#algorithm #opencv #computational-geometry #discrete-mathematics #cgal
#алгоритм #opencv #вычислительная геометрия #дискретная математика #cgal
Вопрос:
На дискретной сеточной плоскости (например, в пикселях изображения) у меня есть замкнутый контур, который может быть выражен либо:
- набор 2D точек
(x1,y1);(x2,y2);(x3,y3);... - или 4-связный код Фримена с начальной точкой:
(x1,y1) 00001112...
Я знаю, как переключаться с одного на другое из этих представлений. Это будут входные данные.
Я хочу получить набор координат сетки, ограниченных контуром. Рассмотрим этот пример, где красные координаты — это контур, а серая — начальная точка:
Если серая координата, скажем, равна (0,0), то мне нужен вектор, содержащий: (1,1),(2,1),(3,1),(3,2)
Порядок не важен, и выходной вектор также может содержать сам контур.
Язык выбора — C , но я открыт для любого существующего кода, алгоритма, библиотеки, указателя, чего угодно…
Я подумал, что, возможно, у CGAL будет что-то подобное, но я не знаком с этим и не смог найти свой путь в руководстве, поэтому я даже не уверен. Я также посмотрел в сторону Opencv, но я думаю, что он не предоставляет этот алгоритм (но я могу ошибаться?).
Я думал о том, чтобы найти ограничивающий прямоугольник, затем проверить каждую из точек в прямоугольнике, чтобы увидеть, находятся ли они внутри / снаружи, но это кажется неоптимальным. Есть идеи?
Комментарии:
1. Все, что вам нужно сделать, это найти единственную точку внутри границы, а затем заполнить заливкой. Это простой рекурсивный алгоритм.
2. Вы должны проверить, действительно ли «поиск ограничивающего прямоугольника» является медленным. Если ваш контур не очень большой, вероятно, быстрее всего преобразовать счетчик в 2D-массив, а затем заполнить заливкой, как предлагает j_random_hacker. В противном случае вам будет сложно определить, какая позиция сетки принадлежит контуру.
3. @j_random_hacker Спасибо, я действительно не думал об этом, но это кажется хорошей идеей. Возможно, это не рекурсивная реализация, хотя, боюсь, она может быть не самой быстрой. Я проведу расследование.
4. @DrV Проблема с ограничивающим прямоугольником заключается в том, что если форма глубоко вогнута (например, подумайте о внешней форме буквы «U»), то может потребоваться некоторое время, чтобы найти точку, которая находится внутри контура.
5. На самом деле, найти «внутри» не так просто, поскольку и «снаружи», и «внутри» находятся рядом с точками контура. Используя код Freeman, вы можете рассчитать количество поворотов влево и поворотов вправо, которые вы делаете во время цикла. Если вы делаете больше поворотов налево, ваш счетчик идет против часовой стрелки, а «внутри» находится слева от вас, если вы идете по счетчику.
Ответ №1:
Одним из способов решения этой проблемы является drawContours, и у вас есть точки contours.
- Создайте пустой мат и нарисуйте контур толщиной = 1 (граница).
- Создайте еще один пустой мат и нарисуйте контур с толщиной = CV_FILLED(вся область, включая границу).
- Теперь bitwise_and между двумя выше (вы получили заполненную область, исключая границу).
- Наконец, проверьте ненулевой пиксель.
Комментарии:
1. Спасибо за ответ. Проблема с этим подходом заключается в пункте 4: это означает синтаксический анализ всех пикселей 1 на 1. Если у меня большая сетка и контуры, которые имеют только небольшую площадь, это неоптимально. Но самая большая проблема заключается в том, что у меня есть несколько контуров, и с помощью этого метода я не могу знать, какие пиксели принадлежат какому контуру.