基于深度优先的图片联通域算法

#include <jni.h>
#include <android/bitmap.h>
#include <android/log.h>
#include <vector>
#include <stack>
//宏定义,计算最大最小值
#define max(a, b) ((a) >= (b) ? (a) : (b))
#define min(a, b) ((a) <= (b) ? (a) : (b))
#define  LOG_TAG    "native-dev"
#define  LOGI(...)  __android_log_print(ANDROID_LOG_INFO, LOG_TAG, __VA_ARGS__)
#define LOGE(...)  __android_log_print(ANDROID_LOG_ERROR, LOG_TAG, __VA_ARGS__)
extern "C"
JNIEXPORT void JNICALL
Java_com_gowow_bitmapnativehelp_BitmapNativeHelp_dfsConnectedComponent(JNIEnv *env, jobject thiz,
                                                                       jobject bitmap,
                                                                       jobject rect_list) {
    AndroidBitmapInfo bitmapInfo;
    memset(&bitmapInfo, 0, sizeof(bitmapInfo));
    // 获取bitmap的信息
    AndroidBitmap_getInfo(env, bitmap, &bitmapInfo);
    // 位图像素数据
    void *bitmapPixels;
    // 锁定内存
    AndroidBitmap_lockPixels(env, bitmap, &bitmapPixels);
    if (bitmapInfo.format == ANDROID_BITMAP_FORMAT_A_8) { // 透明通道图
        uint8_t *pixelsMarks = new uint8_t[bitmapInfo.width * bitmapInfo.height];
        memset(pixelsMarks, 0, bitmapInfo.width * bitmapInfo.height);
        // 存储矩形区域列表
        // 获取 ArrayList 对象的类和方法
        jclass arrayListClass = env->GetObjectClass(rect_list);
        jmethodID add_method = env->GetMethodID(arrayListClass, "add", "(Ljava/lang/Object;)Z");
        for (int y = 0; y < bitmapInfo.height; ++y) {
            for (int x = 0; x < bitmapInfo.width; ++x) {
                //计算当前像素在一维数组中的索引
                int index = y * bitmapInfo.width + x;
                //如果当前像素已经被处理过（标记为1），则跳过，继续下一个像素。
                if (pixelsMarks[index]) {
                    continue;
                }
                //取当前像素的透明通道值
                uint8_t *a8Value = ((uint8_t *) bitmapPixels) + index;
                // 找到一个透明通道值大于0的像素，进行洪水填充
                if (*a8Value > 0) {
                    //创建一个栈 pixelStack 用于实现深度优先搜索。
                    std::stack<std::pair<int, int>> pixelStack;
                    //将当前像素的坐标推入栈。
                    pixelStack.push({x, y});
                    //初始化最小和最大坐标值，用于记录洪水填充区域的边界。
                    int minX = x;
                    int maxX = x;
                    int minY = y;
                    int maxY = y;
                    //进入洪水填充的循环，直到栈为空。
                    while (!pixelStack.empty()) {
                        //弹出栈顶元素，表示当前要处理的像素。
                        auto current = pixelStack.top();
                        pixelStack.pop();
                        //获取当前像素的坐标和在一维数组中的索引
                        int currentX = current.first;
                        int currentY = current.second;
                        int currentIndex = currentY * bitmapInfo.width + currentX;
                        //如果当前像素已经被处理过，跳过。
                        if (pixelsMarks[currentIndex]) {
                            continue;
                        }
                        //标记当前像素为已处理。
                        pixelsMarks[currentIndex] = 1;
                        // 更新边界坐标。
                        minX = min(minX, currentX);
                        minY = min(minY, currentY);
                        maxX = max(maxX, currentX);
                        maxY = max(maxY, currentY);
                       // 定义相邻像素的偏移数组，表示左、右、上、下四个方向。
                        int offsets[4][2] = {
                                {-1, 0},
                                {1,  0},
                                {0,  -1},
                                {0,  1}
                        }; // left, right, top, bottom
                        
                        //遍历相邻像素的偏移数组
                        for (const auto &offset: offsets) {
                            //计算相邻像素的坐标。
                            int newX = currentX + offset[0];
                            int newY = currentY + offset[1];
                            //检查相邻像素是否在图像范围内。
                            if (newX >= 0 && newX < bitmapInfo.width && newY >= 0 &&
                                newY < bitmapInfo.height) {
                                //计算相邻像素在一维数组中的索引。
                                int newIndex = newY * bitmapInfo.width + newX;
                                //如果相邻像素未被处理且透明通道值大于0，将相邻像素的坐标推入栈。
                                if (!pixelsMarks[newIndex]) {
                                    uint8_t alpha = *((uint8_t *) bitmapPixels + newIndex);
                                    if (alpha > 0) {
                                        pixelStack.push({newX, newY});
                                    }
                                }
                            }
                        }
                    }
                    // 结束一轮洪水填充,添加一个Rect
                    jclass rectClass = env->FindClass("android/graphics/Rect");
                    jmethodID rectConstructor = env->GetMethodID(rectClass, "<init>", "(IIII)V");
                    jobject rectObject = env->NewObject(rectClass, rectConstructor,
                                                        minX, minY,
                                                        maxX + 1, maxY + 1);
                    env->CallBooleanMethod(rect_list, add_method, rectObject);
                }
            }
        }

        // 释放内存
        delete[] pixelsMarks;
    } else {
        LOGE("for performance reasons, only transparent channel images are supported");
    }
    // 解锁内存
    AndroidBitmap_unlockPixels(env, bitmap);
}