Algorithm for determining points from given dataset that are within a convex hull defined by a subset of original dataset

Question

Having a dataset of x,y,z with n points like:

1.59855e+006 -185000 -3082.85  
1.59855e+006 -184700 -3064.05 
1.59855e+006 -184400 -3035.3 
1.59855e+006 -184100 -3011.24  
1.59855e+006 -183800 -2990.73  
1.59855e+006 -183500 -2970.26
1.59855e+006 -183200 -2948.27
1.59855e+006 -182900 -2932.94  
1.59855e+006 -182600 -2916.47 
1.59855e+006 -182300 -2897.31
1.59855e+006 -182000 -2881.39 
1.59855e+006 -181700 -2866.74  
1.59855e+006 -181400 -2887.98
1.59855e+006 -181100 -2935.13
1.59855e+006 -180800 -2957.79
1.59855e+006 -180500 -2946.47 
1.59855e+006 -180200 -2917.82 
1.59855e+006 -179900 -2905.03 
1.59855e+006 -179600 -2917.55 
1.59855e+006 -179300 -2896.38 
1.59855e+006 -179000 -2925.13
1.59855e+006 -178700 -2953.91 
1.59855e+006 -178400 -2956.31 
1.59855e+006 -178100 -2836.47

Supposing I have 8 or more points that represent a loop that lives in dataset domain

To solve it I was planning to set z=0, and deal only with x,y points, For instance, if I have 3 points inside a plane like in image (these 3 points are inside all dataset):

I would like to get the bounded subset of the plane, I mean all points that form blue shape (formed by a rubber band stretched). I have the plane and red points, these red points when connected form a convex loop.

something like getting all points inside blue contour:

What algorithm should I use to get all points that are inside that loop? I mean loop is formed by 8 points of dataset (assuming is convex and points have some distance between them)

Kindly suggest some ideas.

Answer 1

I hope I am correctly understanding what you wish to solve. The general idea is as follows: first, construct a convex hull of a selection of $m$ points from your dataset of size $n\ge m$. There are many algorithms that can do this (of varying efficiency); I am making use of the gift-wrapping algorithm (basically verbatim from http://en.wikipedia.org/wiki/Gift_wrapping_algorithm). Once the convex hull has been constructed, we form half-spaces from the pairs of neighboring points on the convex hull. Then, running through each point in the dataset, we can check if the point is within all half-spaces. If so, then that point is within our convex hull of selected points. I'm not making any guarantees about the efficiency of this algorithm, just providing something that (hopefully, have not tested it) works for now.

Let us denote $S$ by the set of $m$ selected points from our dataset.

// CONVEX HULL CODE
pointOnHull = leftmost point in S

i = 0
repeat
    P[i] = pointOnHull
    endpoint = S[0]         // initial endpoint for a candidate edge on the hull
    for j from 1 to m
        if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
    end
    i = i+1
    pointOnHull = endpoint
until endpoint == P[0]      // wrapped around to first hull point

Given the points that make up the convex hull of $S$, we now construct the half-spaces that define the convex hull (note that each point P[i] is a pair; I use P[i].x to denote the x-coordinate). I have denoted the original dataset as D.

// HALF-SPACE CODE
m_hull = |P|  // number of points that make up the hull

for j from 1 to m_hull-1   // loop over line segments of hull to find inward-pointing normals, (dy,-dx)
     dx[j] = P[j+1].x - P[j].x
     dy[j] = P[j+1].y - P[j].y
end
dx[m_hull] = P[1].x - P[m_hull].x
dy[m_hull] = P[1].y - P[m_hull].y

for k from 1 to n          // checking all points in dataset
    for p from 1 to m_hull    // comparing to all half-spaces
       inHullHalfspace[k,p] = (dy[p]*(D[k].x - P[p].x) - dx[p]*(D[k].y - P[p].y) >= 0)   // logical operator, will return 1 if true, 0 otherwise
    end
    inHull[k] = prod[inHullHalfspace[k,:],2]   // logical 'and' across columns, will contain 1 if dataset element k is in the convex hull of selected m points
end

The vector inHull should be what you are after. This should not be too difficult to extend to the 3-dimensional case, but that's all from me tonight. The textbook title Convex Optimization by Boyd may be of help in studying the math behind the half-spaces if you are not familiar.