Determining the "inner domain" of a set of points

Question

I have a set of (x, y) points and I would like to interpolate from those points the value of any points "inside" this set of point. (The yellow area in the picture bellow).

The problem is that I have not find any good way to:

1. Find the polygon which would be the boundary of my interpolated points (green line)
2. Test if the point is inside the polygon or not. I found the Point in Polygon algorithm but I'm not sure that taking all the point in a certain range and testing if they belong in the polygone is a good idea. I would like to find a way that let me test a fewer number of points than (max(x)-min(x))*(max(y)-min(y)), ideally a way to know on which points to do my iteration.

Edit: In the 2nd part I'm iterating on all the points (pixels) in the image, what I'd like to do is only iterate on the points in the yellow field.

Do you have any lead?

Ps: I'm coding in C++ if it's of any help.

Answer 1

The green line that you're looking at is called the convex hull of the set of points and there are many good, efficient algorithms for computing it. The best of them run in time O(n log h), where h is the number of points found on the hull and n is the total number of points. As a totally shameless self-promotion, I have a C++ implementation of one of these algorithms available on my personal site.

As to your second question - once you have the convex hull, it's very easy to determine which points are purely inside the polygon as opposed to on the hull. Just make a hash table of all the points, then iterate over the convex hull and remove all points contained in the hull. What remains in the hash table is the set of points contained within the polygon but not on the boundary.

Hope this helps!