Get all the points in triangular ROI in a xy plane

Question

Input: I have some 50000 points in a xy plane as shown in the below picture.

Now, I need to get all the possible points in a triangular ROI. How to get it. It can can be opencv or Matlab.

The below is the sample where I need to get the possible points of the triangular areas.

Answer 1

MATLAB has an inpolygon command: inpolygon.

For example, this code

 xv = [0.1 0.4 0.15 0.1]; yv = [0 0.4 0.8 0];
 x = rand(250,1); y = rand(250,1);
 in = inpolygon(x,y,xv,yv);
 plot(xv,yv,x(in),y(in),'r+',x(~in),y(~in),'bo')

generates a picture like this:

Answer 2

Something like this, in c++?

Mat plane = imread("plane.png"); // this is the 50 000 pixel plane image

// I assume your triangles are here. E.e. findContours function would save them here, but I don't know your situation.
vector<vector<Point> > triangles;

// this size is something like 1000, so here are only points that should be checkedd if they are inside some triangle
    vector<Point> points; 

// lets loop all rois and check if point is inside one of them
for (int j = 0; j < triangles.size(); j++) {
    for (int i = 0; i < points.size(); i++) {
     double test = pointPolygonTest(trigangles[j], points[i] false);
     if (test < 0) {
      cout << " point " << points[i] << " is outside of triangle " << j << endl;
     } else if (test > 0) {
      cout << " point " << points[i] << " is inside of triangle " << j << endl;
     } else if (test == 0) {
      cout << " point " << points[i] << " is on edge of triangle " << j << endl;
     }
    }
}

for more info: http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

here is OpenCV's example: http://docs.opencv.org/trunk/doc/tutorials/imgproc/shapedescriptors/point_polygon_test/point_polygon_test.html

Answer 3

In OpenCV, you can quickly filter out the points that are not in the minimal bounding rectangle for each triangle. This rectangle can be previously computed by hand or with cv::boundingRect(). The hit test is done with Rect::contains(). This is a fast operation (at least much faster than cv::pointPolygonTest)and this will filter out the points that are obviously not in any triangle. Afterward, you test the points that pass the filter with cv::pointPolygonTest().

That is:

std::vector<cv::Point> pointList;
std::vector<cv::Rect> rectList;
std::vector<std::vector<Point>> triangleList;

for (int pointIndex = 0; pointIndex < pointList.size(); pointIndex++)
{
  for (int rectIndex = 0; rectIndex < rectList.size(); rectIndex++)
  {
    if (!rectList[rectIndex].contains(pointList[pointIndex]))
      continue;

    if (cv::pointPolygonTest(triangleList[rectIndex], pointList[pointIndex], false) < 0)
      continue;

    /* TODO Mark the point for future use */
  }
}