Qt项目中Flood Fill算法过慢及并行优化无效问题问询

我在Qt计算机图形项目中手动实现了基于BFS的Flood Fill算法，但运行耗时过长；尝试并行化循环后也未获得显著性能提升，特此求助。

核心问题 #

• 基于BFS的Flood Fill版本运行耗时极久
• 并行化循环为何未带来显著性能提升

已尝试方案 #

• 最初使用递归DFS，后切换为迭代式BFS
• 将plotPoint函数外置，预分配QVector存储待着色点，但无改善
• 尝试用OpenMP并行化plotPoint函数，但未达预期，不确定是否使用正确

代码实现 #

void MainWindow::iterativeFloodFill(int x, int y, QVector<QPoint> &interior)
{
    std::queue<QPoint> q;
    q.push(QPoint(x, y));

    int xdir[] = {0, -1, 1, 0};
    int ydir[] = {-1, 0, 0, 1};

    while (!q.empty())
    {
        QPoint p = q.front();
        q.pop();

        if (visited.contains(p) || pts.contains(p))
            continue;

        interior.push_back(QPoint(p.x(), p.y()));
        visited.insert(p);

        for (int i = 0; i < 4; ++i)
        {
            QPoint neighbor = QPoint(p.x() + xdir[i], p.y() + ydir[i]);
            if (!visited.contains(neighbor) && !pts.contains(neighbor))
            {
                q.push(neighbor);
            }
        }
    }
}


void MainWindow::on_floodfill_clicked()
{
    if (polygonPoints.size() == 0) return;
    QPoint seed = polygonPoints[0];
    QVector<QPoint> interior_points;
    interior_points.reserve(1011);
    polygonPoints.clear();
    iterativeFloodFill(seed.x(), seed.y(), interior_points);
    #pragma omp parallel for
    for(int i = 0; i<interior_points.size(); i++)
    {
        #pragma omp critical
        plotPoint(interior_points[i], QColor(10,20,30));
    }
}
void MainWindow::plotPoint(int x, int y, int r, int g, int b)
{
    pts[QPoint(x, y)] =  QColor(r,g,b) ;
    int gridOffset = (ui->gridOffset->value()==0)?1:ui->gridOffset->value();
    int width = ui->workArea->width();
    int height = ui->workArea->height();
    int centerX=width/2;
    int centerY=height/2;
    int calcX = centerX+ x*gridOffset + gridOffset/2;
    int calcY = centerY -  y*gridOffset - gridOffset/2;
    colorPoint(calcX, calcY, r,g,b, gridOffset);
}
void MainWindow::plotPoint(QPoint pt, QColor col)
{
    plotPoint(pt.x(), pt.y(), col.red(), col.green(), col.blue());
}
void MainWindow::colorPoint(int x, int y, int r, int g, int b, int penwidth=1) {
    QPixmap canvas=ui->workArea->pixmap();
    QPainter painter(&canvas);
    QPen pen=QPen(QColor(r,g,b),penwidth);
    painter.setPen(pen);
    painter.drawPoint(x, y);

    ui->workArea->setPixmap(canvas);
}

函数说明 #

• plotPoint：将自定义坐标系的(x,y)转换为QPixmap坐标系，调用colorPoint完成像素着色
• colorPoint：执行具体的像素着色操作
• visited为QSet类型，pts为QHash类型

GUI应用界面 #

性能瓶颈分析与优化方案 #

1. Flood Fill算法本身的效率问题 #

• 容器选择不当：QSet<QPoint>和QHash<QPoint>的contains操作存在哈希计算与查找开销，建议改用二维布尔数组或QBitArray标记已访问点，直接通过坐标索引访问（visited[y * width + x]），将时间复杂度降到纯O(1)。
• BFS重复入队问题：当前代码在弹出队列元素时才标记已访问，会导致同一邻居被多个父节点重复入队，浪费队列资源。优化方式是入队前先标记已访问：

  QPoint neighbor = QPoint(p.x() + xdir[i], p.y() + ydir[i]);
  if (!visited.contains(neighbor) && !pts.contains(neighbor))
  {
      visited.insert(neighbor); // 入队前标记
      q.push(neighbor);
      interior.push_back(neighbor); // 提前加入结果，避免弹出时重复操作
  }
  

2. 并行化无效的原因 #

• Critical区完全串行化：你在并行循环中添加了#pragma omp critical，导致所有线程执行plotPoint时必须排队等待，完全抵消了并行效果。
• GUI操作线程限制：Qt的GUI操作必须在主线程执行，子线程直接调用ui->workArea->setPixmap存在线程安全问题，且跨线程GUI操作本身会带来额外开销，无法实现有效并行。

3. 绘图流程的关键优化 #

当前colorPoint每次绘制一个点都要拷贝Pixmap、创建Painter、更新UI，几百次操作会导致性能雪崩。正确做法是内存中批量绘制，最后一次更新UI：

void MainWindow::on_floodfill_clicked()
{
    if (polygonPoints.size() == 0) return;
    QPoint seed = polygonPoints[0];
    QVector<QPoint> interior_points;
    // 根据画布大小动态预分配容量，避免多次内存重分配
    interior_points.reserve(ui->workArea->width() * ui->workArea->height());
    polygonPoints.clear();
    iterativeFloodFill(seed.x(), seed.y(), interior_points);

    // 获取内存中的Pixmap副本，批量绘制所有点
    QPixmap canvas = ui->workArea->pixmap() ? *ui->workArea->pixmap() : QPixmap(ui->workArea->size());
    QPainter painter(&canvas);
    QPen pen(QColor(10,20,30));
    painter.setPen(pen);

    // 预计算固定参数，避免循环内重复获取UI值
    int gridOffset = ui->gridOffset->value() == 0 ? 1 : ui->gridOffset->value();
    int width = ui->workArea->width();
    int height = ui->workArea->height();
    int centerX = width / 2;
    int centerY = height / 2;

    // 批量转换坐标并绘制
    for(const QPoint& pt : interior_points)
    {
        int calcX = centerX + pt.x() * gridOffset + gridOffset / 2;
        int calcY = centerY - pt.y() * gridOffset - gridOffset / 2;
        painter.drawPoint(calcX, calcY);
        pts[pt] = QColor(10,20,30);
    }

    // 最后一次更新UI
    ui->workArea->setPixmap(canvas);
}

4. 其他细节优化 #

• 预计算gridOffset、centerX等固定参数，避免在循环中重复读取UI控件值。
• 若填充区域较大，可考虑使用扫描线填充算法替代BFS，减少队列操作的开销，进一步提升效率。

内容的提问来源于stack exchange，提问作者Siddhartha Mondal