Test if a box is intersecting a disc. Works in N-dimensions.

README.md

Box/disc intersection test

This code sample demonstrates how to check if a box and a disc (in 3d, a sphere) intersects each other. The code works for 2d and 3d, and beyond, without any modifications.

The actual test is the function box_intersect_disc, the rest of the script is just to provide a visual demonstration of the test.

box-disc-intersection-test.py

import numpy
import matplotlib.pyplot as plot



def norm2(X):
	return numpy.sqrt(numpy.sum(X ** 2))



def box_intersect_disc(C, R, min_corner, max_corner):
	center = .5 * (max_corner + min_corner)
	half_extent = .5 * (max_corner - min_corner)

	C = numpy.fabs(C - center) - half_extent
	if min(C) > 0.:
		return norm2(C) < R
	return max(C) < R



def display(C, R, S, box_size, intersection_list):
	fig = plot.figure()
	ax = fig.gca()
	ax.axis('off')	
	ax.set_aspect('equal')

	# Setup view
	size = 2.5
	plot.xlim((-.5 * size, .5 * size))
	plot.ylim((-.5 * size, .5 * size))

	# Plot the disc
	ax.add_artist(plot.Circle(C, R, lw = 1., color='k', fill = False, zorder = 0))

	# Plot the boxes
	for Si, intersect in zip(S, intersection_list):
		ax.add_artist(plot.Rectangle(Si - .5 * box_size, box_size, box_size, fill = False, color = '#f08080' if intersect else '#8080f0', zorder = 1))

	# Job done
	plot.show()



def main():
	# Define a unit disc
	C, R = numpy.zeros(2), .5

	# Generate box centers randomly
	box_size = .05
	S = 1.5 * (numpy.random.random(size = (1024, 2)) - .5)
	
	# Check for intersections
	intersection_list = [box_intersect_disc(C, R, Si - .5 * box_size, Si + .5 * box_size) for Si in S]

	# Display the result 
	display(C, R, S, box_size, intersection_list)



if __name__ == '__main__':
	main()