marmakoide

Golden dot spiral on the sphere

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

42 points	256 points	999 points

marmakoide

import numpy

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

def trilateration_3d(A, B, C, rA, rB, rC):
	# Find the two intersection points of three spheres
	# The routine returns D, W, h_sqr, and the two solutions are D - sqrt(h_sqr) * W and D + sqrt(h_sqr) * W
	# The points are at a distance 2 * sqrt(h_sqr) from each other, and both on the line of origin D and direction W
	# If h_sqr is negative, there's no solutions to the problem

marmakoide

import numpy

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

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

def pick_orthogonal_vector(U):
	# Original idea from Sam Hocevar

marmakoide

import numpy

def norm2_sqr(X):
	return numpy.sum(X ** 2)

def perp(X):
	return numpy.array((-X[1], X[0]))

def trilateration_2d(A, B, rA, rB):
	# Find the two intersection points of two circles

marmakoide

import numpy

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

def get_circumcircle(A, B, C):
	U, V = B - A, C - A
	U_norm, V_norm = norm2(U), norm2(V)
	U /= U_norm
	V /= V_norm

marmakoide

import numpy

'''
Pick N points uniformly from the unit disc
This sampling algorithm does not use rejection sampling.
'''
def disc_uniform_pick(N):
	angle = (2 * numpy.pi) * numpy.random.random(N)
	out = numpy.stack([numpy.cos(angle), numpy.sin(angle)], axis = 1)
	out *= numpy.sqrt(numpy.random.random(N))[:,None]

marmakoide

import numpy

'''
Pick N points uniformly from the unit disc
This sampling algorithm does not use rejection sampling.
'''
def disc_uniform_pick(N):
	angle = (2 * numpy.pi) * numpy.random.random(N)
	out = numpy.stack([numpy.cos(angle), numpy.sin(angle)], axis = 1)
	out *= numpy.sqrt(numpy.random.random(N))[:,None]

marmakoide

'''
Compute a triangle's area from its edges length with Heron's formula
Numerically stable
'''
def triangle_area_from_lengths(a, b, c):
	# Sort input
	c, b, a = sorted((a, b, c))

	# Compute Heron's formula
	ret = (a + (b + c)) * (c - (a - b)) * (c + (a - b)) * (a + (b - c))

marmakoide

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):

marmakoide

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.