Что вызывает переполнение стека?И как я могу решить это?

Question

Я делал домашнее задание для компьютерной графики. Нам нужно использовать floodfill для рисования области, но независимо от того, как я изменил reserve stack Visual Studio, он всегда будет выпадать stackoverflow.

void Polygon_FloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) {
int interiorColor;
interiorColor = GetPixel(hdc, x0, y0);
if ((interiorColor != borderColor) && (interiorColor != fillColor)) {
    SetPixel(hdc, x0, y0, fillColor);
    Polygon_FloodFill(hdc, x0 + 1, y0, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0, y0 + 1, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0 - 1 ,y0, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0, y0 - 1, fillColor, borderColor);
}

Answer 1

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

Ваши варианты:

• увеличьте стек выполнения, если сможете
• уменьшить площадь (как насчет 100x100 или 20x20?)
• прекратить использование стека выполнения и использовать структуру данных, которая работает аналогично, но может содержать больше элементов (будучи более эффективной и / или способной расти / увеличиваться)
• использовать другой алгоритм (например, рассмотрите переход от отдельных пикселей к горизонтальным промежуткам пикселей, из которых будет намного меньше последних, чем первый)

Answer 2

сколько пикселей заполнить? каждый пиксель имеет один уровень глубины рекурсии, и у вас есть много переменных, все локальные и операнды рекурсивной функции + возвращаемое значение и адрес, поэтому для достижения пикселя вы сохраняете это:

void Polygon_FloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) {
int interiorColor;

в 32-битной среде. Я оцениваю это в [байтах]:

4 Polygon_FloodFill return address
4 HDC hdc ?
4 int x0
4 int y0
4 int fillColor
4 int borderColor
4 int interiorColor
-------------------
~ 7*4 = 28 Bytes

Может быть даже больше, в зависимости от механизма C и последовательности вызовов.

Теперь, если заполненная область имеет, например, 256x256 пиксель, вам нужно:

7*4*256*256 = 1.75 MByte

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

Как с этим бороться?

1. опускание стека / кучи мусора

   просто не используйте операнды для вашего flood_fill, вместо этого переместите их в глобальные переменные:

   HDC floodfill_hdc;
   int floodfill_x0,floodfill_y0,floodfill_fillColor,floodfill_borderColor;
   void _Polygon_FloodFill()
    {
    // here your original filling code
    int interiorColor;
    ...
    }
   void PolygonFloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) // this is what you call when want to fill something
    {
    floodfill_hdc=hdc;
    floodfill_x0=x0;
    floodfill_y0=y0;
    floodfill_fillColor=fillColor;
    floodfill_borderColor=borderColor;
    _Polygon_FloodFill();
    }
   

   это позволит заполнить ~ в 14 раз большую область.

2. предельная глубина рекурсии

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

3. изменить заливку с пикселей на строки

   это просто устраняет множество рекурсивных вызовов в дико грубой оценке до sqrt(n) рекурсий от n ... Вы просто заполняете всю строку от начальной точки до заданного направления, пока не достигнете границы ... Так что вы бы иметь только рекурсивный вызов для каждой строки, а не для каждого пикселя. Вот пример (см. [Edit2]):

   • Алгоритм рисования, оставляющий белые пиксели по краям при окрашивании

Однако имя функции Polygon_FloodFill подразумевает, что вы получили полигон границы в векторном виде. Если случай, чем заполнение, будет намного быстрее с использованием методов растеризации полигонов, таких как:

• как растеризовать повернутый прямоугольник (в 2d с помощью setpixel)

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

Answer 3

Что вызывает переполнение стека?

Каков диапазон x0?+/- 2 000 000 000?Это ваш потенциал глубины стека.

Код явно не предотвращает выход за пределы диапазона, если только GetPixel(out-of-range) не возвращает значение без совпадения.

И как я могу его разрешить?

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