Devert Alexandre marmakoide

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.

Golden dot spiral on the disc

This code sample demonstrates how to generates a set of points that covers a disc almost evenly, for any number of points. The trick is to use a Fermat's spiral and the golden angle.

42 points	256 points	999 points

MIT License

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

2d Voronoi diagrams

This code sample demonstrates how to compute a Voronoi diagram in 2d.

It works as following

Transform the points (called here lifting the points) from 2d to 3d.

	import numpy



	def quickhull_2d(S):
	def process(P, a, b):
	signed_dist = numpy.cross(S[P] - S[a], S[b] - S[a])
	K = [i for s, i in zip(signed_dist, P) if s > 0 and i != a and i != b]

	if len(K) == 0:

	import numpy



	def get_circumsphere(S):
	U = S[1:] - S[0]
	B = numpy.sqrt(numpy.sum(U ** 2, axis = 1))
	U /= B[:,None]
	C = numpy.dot(numpy.linalg.solve(numpy.inner(U, U), .5 * B), U)
	return C + S[0], numpy.sqrt(numpy.sum(C ** 2))

	import numpy

	def get_unit_simplex(N, dtype = float):
	# Original algorithm from John Burkardt
	A = numpy.full(N, (1. - numpy.sqrt(N + 1)) / N, dtype = dtype)
	S = numpy.concatenate([A[:,None].T, numpy.identity(N, dtype = dtype)])
	S -= numpy.mean(S, axis = 0)
	S /= numpy.sqrt(2.)
	return S

	import numpy

	'''
	Pick a point uniformly from the unit circle
	'''
	def circle_uniform_pick(size, out = None):
	if out is None:
	out = numpy.empty((size, 2))

	angle = 2 * numpy.pi * numpy.random.random(size)

	import numpy

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

	def normalized(X):
	return X / norm2(X)

	'''
	Returns the intersection, a line, between the plane A and B

	from collections import defaultdict



	'''
	Represents the sequence of all partitions of a set, by increasing number of
	partition. This is a pseudo-sequence, each item of the sequence is generated
	rather than stored.
	'''
	class partition_set(object):