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

Question

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

1) Я все края пикселей

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

Answer 1

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

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

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

Это, конечно, работать только если у вас есть все края пикселей. Взгляните на Marching Squares, может быть полезной.

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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