CODEWITHSUNDEEP
c++opencvoptimization
Simon Ninon
Simon Ninon

Reputation: 2451

OpenCV most efficient way to find a point in a polygon

I have a dataset of 500 cv::Point.

For each point, I need to determine if this point is contained in a ROI modelized by a concave polygon. This polygon can be quite large (most of the time, it can be contained in a bounding box of 100x400, but it can be larger)

For that number of points and that size of polygon, what is the most efficient way to determine if a point is in a polygon?

Upvotes: 4

Views: 3826

Answers (3)

McBoh
McBoh

Reputation: 21

This is faster than pointPolygonTest with and without a bounding box!

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;
    }
}

It uses the color to check if the point is inside the contour. For faster matrix access than Mat::at() we're using pointer access. In my case this was up to 20 times faster than the pointPolygonTest.

Upvotes: 2

legrojan
legrojan

Reputation: 589

In general, to be both accurate and efficient, I'd go with a two-step process.

  • First, a bounding box on the polygon. It's a quick and simple matter to see which points are not inside the box. With that, you can discard several points right off the bat.
  • Secondly, pointPolygonTest. It's a relatively costly operation, but the first step guarantees that you will only perform it for those points that need better accuracy.

This way, you mantain accuracy but speed up the process. The only exception is when most points will fall inside the bounding box. In that case, the first step will almost always fail and thus won't optimise the algorithm, will actually make it slightly slower.

Upvotes: 5

Amadeusz
Amadeusz

Reputation: 1706

Quite some time ago I had exactly the same problem and used the masking approach (second point of your statement). I was testing this way datasets containing millions of points and found this solution very effective.

Upvotes: 3

Related Questions