Convex Hole

 
 

Suppose we have lots of randomly placed points in a region. We want only the contour points. How can we find them?  The answer is convex hole. Let's find it...
 

a. Find the extreme points (right-most, left-most, top, down).

b. Break the whole region in four parts.

c. Start rotating clock-wise or counter clock-wise from one extreme point to another using (y/x)=TAN(q) equation.

 

 

 

 

 

You can download full algorithm in Adobe Acrobat format from here.

 

Here is the Pascal source code and a sample data file.

 

 

Sample Execution Results