Paul Lutkus - Boundary Point Detection Algorithms

My current project involves sampling a set of points on which I’ll learn a control barrier function. I need to automate the detection of boundary points in the sampled set, which is not guaranteed to be convex. I’m using this post to document my experimentation with a number of algorithms that could solve this problem.

2 Alpha Shape

The concept of an ‘alpha shape’ is a nonconvex generalization of the convex hull. Most theorems and proofs regarding the alpha shape of a set of points necessitate placing the points in ‘general position’.

2.1 General Position

Considering points that are in general position is a way to avoiding edge cases when constructing proofs and programs. In \(n\)-dimensional space, general position is the

3 Convex Hull

I’ve decided to use the ‘Gift Wrapping’ algorithm to compute the convex hull since it generalizes nicely to computing the alpha shape as I’ll explain. Loosely, the procedure is as follows:

Since, for each hull point, we must iterate through each of the other \(n\) points, this procedure has a time-complexity of \(O(hn)\), where \(h\) is the number of hull points.

3.1 The Initial Maximum

As in step 1 , we first find the point that is maximal in the \(y\)-dimension. Given a datasent of shape \((n,2)\), We’ll create a copy of the data to process, and iterate through it to obtain its maximum in \(y\).

# sort and remove point with maximum y
pt_max = pts[0,:]
pts_copy = [pt_max]
for idx, x in enumerate(pts[1:]):
	if x[1] > pt_max[1]:
		pt_max = x
	pts_copy.append(x)

3.2 The Central Loop

This section covers step 3 and step 4 and is primarily a do-while-loop that checks whether each new focus is the original (in which case, we’ve completed the hull). Recall that the new focus is the point which makes the minimum nonnegative slope with the previous focus.

A useful trick here, for initializing the minimum slope, is to set it to np.infty , which is evaluates as larger than any numeric data type. This is an easy way to ensure that the first prospective point will always be chosen as the initial candidate.

Note that multiple points could generate the same slope with respect to the focus. In this case we want to pick the point that is furthest from the focus

In order to emulate a ‘do-while’, we use while True: to ensure that the loop always runs at least once, and then we evaluate the condition focus != pt_max at the end of the loop and break if it is false.

Note: ### THE REST ### denotes what processing must be done between iterations to ensure the slope conditions are continually valid, and is what we’ll discuss next.

# for each focus f, find min slope >= 0, 
# then rotate clockwise
f = pt_max
hull = []
total_theta = 0 # this will come in handy later
while True:
	m_min = np.infty
	for idx, pt in enumerate(pts_copy):
		# compute slope, update focus candidate 
		# 'fc' if slope is nonnegative and lesser 
		# than previous
		m = (f[1] - pt[1]) / (f[0] - pt[0])
		if m >= 0 and m < min_m:
			fc = idx
			min_m = m 
		# if same slope as previous candidate, take
		# whichever is further from current focus
		elif m == m_min:
		if np.linalg.norm(f - pt) 
		   > np.linalg.norm(f - pts_copy[fc]):
			fc = idx            
	# new focus is pt w/ minimum positive slope 
	# wrt prev focus, no need to consider in 
	# next iteration
	f = pts_copy[fc]
	hull.append(f)
	pts_copy.remove(fc)

	############
	# THE REST #
	############

	# a do-while in python:
	if f != pt_max:
		continue
	else:
		break

3.3 Tracking Affine Transformations

We next regard step 5 and consider how the dataset must be rotated between iterations to ensure that the minimum nonnegative slope condition is still valid. The code here will be inserted at the point marked ### THE REST ### in the above snippet

Boundary Point Detection Algorithms

Table of Contents

1 Introduction