OpenCV中寻找多边形内某一点的最有效方法

Question

我有一个包含500个cv::Point的数据集。

对于每个点，我需要确定该点是否包含在由凹多边形模拟的ROI中。 这个多边形可能很大（大多数情况下，它可以包含在100x400的边界框中，但它也可能更大）。

对于这些点和这个大小的多边形，最有效的方法是什么来确定一个点是否在一个多边形内？

• 使用pointPolygonTest openCV函数？
• 使用drawContours构建掩码，并查找点在掩码中是白色还是黑色？
• 其他解决方案？（我真的想要精确，所以凸多边形和边界框被排除在外）。

- Simon Ninon

---

很难说哪个更快。你必须在目标环境中测试它们（是否有CUDA、SSE、Neon等？）不要依赖理论比较。在确切的目标环境中对它们进行基准测试。 - Humam Helfawi

Answer 1

为了既准确又高效，我会采用两个步骤。

• 首先，对多边形进行边界框（bounding box）处理。很容易简单地看出哪些点不在边界框内。这样就可以直接舍弃几个点。
• 其次是pointPolygonTest。这是一个相对耗时的操作，但第一步保证了你只会对需要更好精度的那些点执行该操作。

这种方法既能保持准确性，又能加速处理过程。唯一的例外情况是大多数点都在边界框内。在这种情况下，第一步几乎总是失败的，因此不会优化算法，实际上会稍微慢一些。

- legrojan

---

好的解决方案。您还可以尝试使用MinAreaRect，这可能会更准确。 - Humam Helfawi

Answer 2

很久以前，我遇到了与您完全相同的问题，采用了掩码方法（您陈述的第二点）。我一直在测试包含数百万个数据点的数据集，发现这种解决方案非常有效。

- Amadeusz

Answer 3

这比使用边界框的pointPolygonTest函数更快！

Scalar color(0,255,0);
drawContours(image, contours, k, color, CV_FILLED, 1); //k is the index of the contour in the array of arrays 'contours'
for(int y = 0; y < image.rows, y++){
    const uchar *ptr = image.ptr(y);
    for(int x = 0; x < image.cols, x++){
        const uchar * pixel = ptr;
        if((int) pixel[1] = 255){
            //point is inside contour
        }
        ptr += 3;
    }
}

它使用颜色来检查点是否在轮廓内。 为了比Mat::at()更快地访问矩阵，我们使用指针访问。 在我的情况下，这比pointPolygonTest快20倍。

- McBoh