Эффективный способ заполнить выпуклую форму

Question

Скажем, у меня есть замкнутая форма, как показано на рисунке ниже, и у меня есть края пикселей.Какой самый эффективный способ заполнить форму, т.е. включить пиксели «внутри» внутри фигуры, если:

1) у меня есть все краевые пиксели

2) у меня большая часть краяпикселей, а не все (как показано на рисунке).

Answer 1

Построить выпуклый корпус и добавить недостающие пиксели. Затем используйте алгоритм линии сканирования, чтобы заполнить многоугольник.

Answer 2

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

Answer 3

Все зависит от ситуации.

Если вы вручную создали кадровый буфер (в основном используя байтовый массив или что-то похожее), вам придется перебирать все пиксели, которые вы хотите изменить. Так, например, начиная с самого левого края строки:

• Найти начало фигуры в ряду
• Прыгните на один вправо и включите пиксель, пока не найдете второй конец фигуры в строке (или конце строки)
• Продолжить в следующем ряду

Это, конечно, будет работать только при наличии всех краевых пикселей. Взгляните на Марширующие квадраты , вам может помочь.

И, пожалуйста, будьте более конкретны. «Самый эффективный способ заливки фигуры» зависит от вашей базовой библиотеки рендеринга, от растровой графики и т. Д. *

EDIT Обратите внимание, что алгоритм намного быстрее, если вы можете генерировать краевые пиксели, тогда нет необходимости искать начало края.

Answer 4

1. Разрывы на границе разрушают смысл, если слово «внутри».
2. Нейронная сеть, такая как сетчатка человека, очень эффективна при такой обработке.
3. На компьютере вам нужно время, чтобы определить, что вы подразумеваете под «внутри». Насколько велик разрыв? Насколько извилистая граница?
4. Имитация большого кругового жучка, подпрыгивающего вокруг "изнутри" - слишком большого, чтобы пройти через промежутки, но меньше минимального радиуса кривизны границы ????

Answer 5

Прежде чем вы сможете заполнить что-то внутри, вам необходимо определить точную границу, в этом случае это будет означать распознавание круга.

После этого вы можете просто установить флажок вокруг круга для каждого пикселя, если он на самом деле в нем. Поскольку вам нужно что-то делать с каждым пикселем внутри круга, а количество пикселей в круге является линейным по количеству пикселей ограничивающего квадрата (при условии, что стороны ограничивающего квадрата имеют длину «радиус * постоянная» для некоторой постоянной), должно быть близко к оптимальному.