hashing -- Fast access to space associated data

This modules provide tools for accessing data using its space location (not for final user).

The complexity and therefore the cost of those operations are most of the time close to the hashmap complexity O(1). It means data is found in time independently of the actual size of the mesh or whatever storage it is.

Connectivity

edgekey(a, b)

Return a key for a non-directional edge

Source code in madcad/hashing.py

def edgekey(a,b):
	''' Return a key for a non-directional edge '''
	if a < b:	return (a,b)
	else:		return (b,a)

facekeyo(a, b, c)

Return a key for an oriented face

Source code in madcad/hashing.py

def facekeyo(a,b,c):
	''' Return a key for an oriented face '''
	if a < b and b < c:		return (a,b,c)
	elif a < b:				return (c,a,b)
	else:					return (b,c,a)

arrangeface(f, p)

Return the face indices rotated the way p is the first index, if p is in the face

Source code in madcad/hashing.py

def arrangeface(f, p):
	''' Return the face indices rotated the way `p` is the first index, if `p` is in the face '''
	if   p == f[1]:	return f[1],f[2],f[0]
	elif p == f[2]:	return f[2],f[0],f[1]
	else:			return f

arrangeedge(e, p)

Return the edge indices rotated the way p is the first index, if p is in the edge

Source code in madcad/hashing.py

def arrangeedge(e, p):
	''' Return the edge indices rotated the way `p` is the first index, if `p` is in the edge '''
	if p == e[1]:	return e[1], e[0]
	else:			return e

connpp(ngons)

Point to point connectivity

input is a list of ngons (tuple of 2 to n indices)

Source code in madcad/hashing.py

def connpp(ngons):
	''' Point to point connectivity 

		input is a list of ngons (tuple of 2 to n indices)
	'''
	conn = {}
	for loop in ngons:
		for i in range(len(loop)):
			for a,b in ((loop[i-1],loop[i]), (loop[i],loop[i-1])):
				if a not in conn:		conn[a] = [b]
				elif b not in conn[a]:	conn[a].append(b)
	return conn

connef(faces)

Oriented edge to face connectivity

Source code in madcad/hashing.py

def connef(faces):
	''' Oriented edge to face connectivity '''
	conn = {}
	for i,f in enumerate(faces):
		for e in ((f[0],f[1]), (f[1],f[2]), (f[2],f[0])):
			conn[e] = i
	return conn

connpe(edges)

Point to edge connectivity

Source code in madcad/hashing.py

def connpe(edges):
	''' Point to edge connectivity '''
	conn = Asso()
	for i,edge in enumerate(edges):
		for p in edge:
			conn.add(p,i)
	return conn

connexity(links)

Return the number of links referencing each point as a dictionary {point: num links}

Source code in madcad/hashing.py

def connexity(links):
	''' Return the number of links referencing each point as a dictionary {point: num links} '''
	reach = {}
	for l in links:
		for p in l:
			reach[p] = reach.get(p,0) +1
	return reach

suites(lines, oriented=True, cut=True, loop=False)

Return a list of the suites that can be formed with lines. lines is an iterable of edges

Parameters:

Name	Type	Description	Default
oriented		specifies that (a,b) and (c,b) will not be assembled	True
cut		cut suites when they are crossing each others	True

Return a list of the sequences that can be formed

Source code in madcad/hashing.py

def suites(lines, oriented=True, cut=True, loop=False):
	''' Return a list of the suites that can be formed with lines.
		`lines` is an iterable of edges

	Parameters:
		oriented:      specifies that (a,b) and (c,b) will not be assembled
		cut:           cut suites when they are crossing each others

	Return a list of the sequences that can be formed
	'''
	# TODO: rewrite this to use hashmaps instead of search loops
	lines = list(lines)
	# get contiguous suite of points
	suites = []
	while lines:
		suite = list(lines.pop())
		found = True
		while found:
			found = False
			for i,edge in enumerate(lines):
				if edge[-1] == suite[0]:		suite[0:1] = edge
				elif edge[0] == suite[-1]:		suite[-1:] = edge
				# for unoriented lines
				elif not oriented and edge[0] == suite[0]:		suite[0:1] = reversed(edge)
				elif not oriented and edge[-1] == suite[-1]:	suite[-1:] = reversed(edge)
				else:
					continue
				lines.pop(i)
				found = True
				break
			if loop and suite[-1] == suite[0]:	break
		suites.append(suite)
	# cut at suite intersections (sub suites or crossing suites)
	if cut:
		reach = {}
		for suite in suites:
			for p in suite:
				reach[p] = reach.get(p,0) + 1
		for suite in suites:
			for i in range(1,len(suite)-1):
				if reach[suite[i]] > 1:
					suites.append(suite[i:])
					suite[i+1:] = []
					break
	return suites

Specific Hashmaps

PositionMap(cellsize, iterable=None)

Holds objects associated with their location. Every object can be bound to multiple locations, and each location can hold multiple objects. cellsize defines the box size for location hashing (the smaller it is, the bigger the memory footprint will be for non-point primitives)

Attributes defined here

:cellsize: the boxing parameter (DON'T CHANGE IT IF NON-EMPTY) :dict: the hashmap from box to objects lists

Source code in madcad/hashing.py

def __init__(self, cellsize, iterable=None):
	self.options = {}
	self.cellsize = cellsize
	self.dict = {}
	if iterable:	self.update(iterable)

keysfor(space)

Rasterize the primitive, yielding the successive position keys currently allowed primitives are

    :points:                vec3
    :segments:              (vec3,vec3)
    :triangles:             (vec3,vec3,vec3)

Source code in madcad/hashing.py

def keysfor(self, space):
	''' Rasterize the primitive, yielding the successive position keys 
		currently allowed primitives are 

			:points:		vec3
			:segments:		(vec3,vec3)
			:triangles:		(vec3,vec3,vec3)
	'''
	# point
	if isinstance(space, vec3):
		return tuple(i64vec3(glm.floor(space/self.cellsize))),
	# segment
	elif isinstance(space, tuple) and len(space) == 2:
		return core.rasterize_segment(space, self.cellsize)
	# triangle
	elif isinstance(space, tuple) and len(space) == 3:
		return core.rasterize_triangle(space, self.cellsize)
	else:
		raise TypeError("PositionMap only supports keys of type:  points, segments, triangles")

update(other)

Add the elements from an other PositionMap or from an iterable

Source code in madcad/hashing.py

def update(self, other):
	''' Add the elements from an other PositionMap or from an iterable '''
	if isinstance(other, PositionMap):
		assert self.cellsize == other.cellsize
		for k,v in other.dict.items():
			if k in self.dict:	self.dict[k].extend(v)
			else:				self.dict[k] = v
	elif hasattr(other, '__iter__'):
		for space,obj in other:
			self.add(space,obj)
	else:
		raise TypeError("update requires a PositionMap or an iterable of couples (space, obj)")

add(space, obj)

add an object associated with a primitive check keysfor for a description of allowed primitives

Source code in madcad/hashing.py

def add(self, space, obj):
	''' 
		add an object associated with a primitive 
		check `keysfor` for a description of allowed primitives
	'''
	for k in self.keysfor(space):
		if k not in self.dict:	self.dict[k] = [obj]
		else:					self.dict[k].append(obj)

get(space)

get the objects potentially intersecting the given primitive check keysfor for a description of allowed primitives

Source code in madcad/hashing.py

def get(self, space):
	''' 
		get the objects potentially intersecting the given primitive 
		check `keysfor` for a description of allowed primitives
	'''
	for k in self.keysfor(space):
		if k in self.dict:
			yield from self.dict[k]

display(scene)

Source code in madcad/hashing.py

def display(self, scene):
	web = mesh.Web()
	if 'color' in self.options:		web.options['color'] = self.options['color']
	base = vec3(self.cellsize)
	for k in self.dict:
		l = len(web.points)
		web += mesh.Web([base*(p+k)  for p in self._display[0]], self._display[1], groups=[k])
	return web.display(scene)

__contains__(space)

check if any stored object is potentially intersecting the given primitive

Source code in madcad/hashing.py

def __contains__(self, space):
	''' check if any stored object is potentially intersecting the given primitive '''
	return next(self.get(space), None) is not None

meshcellsize(mesh)

Returns a good cell size to index primitives of a mesh with a PositionMap

See implementation.

Source code in madcad/hashing.py

def meshcellsize(mesh):
	''' Returns a good cell size to index primitives of a mesh with a PositionMap 

		See implementation.
	'''
	# the number of key for triangles is propotionate to the surface
	# points are placed on this surface, so sqrt(len(pts)) is a good hint for the point density on the surface
	return length(mesh.box().size) / sqrt(len(mesh.points))

PointSet(cellsize, iterable=None, manage=None)

Holds a list of points and hash them. The points are holds using indices, that allows to get the point buffer at any time, or to retrieve only a point index. cellsize defines the box size in which two points are considered to be the same

Methods are inspired from the builtin type set

Attributes defined here

:points: the point buffer (READ-ONLY PURPOSE) :cellsize: the boxing parameter (DON'T CHANGE IT IF NON-EMPTY). mendatory and is the distance at which you want to distinguish points :dict: the hashmap from box to point indices

Build parameters

:iterable: use it to build the set by inserting elements :manage: pass a list for inplace use it, only indexing will be built

Source code in madcad/hashing.py

def __init__(self, cellsize, iterable=None, manage=None):
	self.cellsize = cellsize
	self.dict = {}
	if manage is not None:
		assert iterable is None
		self.points = manage
		for i in reversed(range(len(self.points))):
			self.dict[self.keyfor(self.points[i])] = i
	else:
		self.points = typedlist(dtype=vec3)
		if iterable:	self.update(iterable)

__iadd__ = update class-attribute instance-attribute

__isub__ = difference_update class-attribute instance-attribute

keyfor(pt)

hash key for a point. points with the same key will be considered equivalent and merged in the set

Source code in madcad/hashing.py

def keyfor(self, pt):
	''' 
		hash key for a point. 
		points with the same key will be considered equivalent and merged in the set 
	'''
	return tuple(i64vec3(glm.floor(pt/self.cellsize)))

update(iterable)

add points from an iterable

Source code in madcad/hashing.py

def update(self, iterable):
	''' add points from an iterable '''
	for pt in iterable:	self.add(pt)

difference_update(iterable)

Remove the points from an iterable

Source code in madcad/hashing.py

def difference_update(self, iterable):
	''' Remove the points from an iterable '''
	for pt in iterable:	self.discard(pt)

add(pt)

add a point to the set if no equivalent point is at this position return the index of the created point or the pre-existing point at this position.

Source code in madcad/hashing.py

def add(self, pt) -> int:
	''' 
		add a point to the set if no equivalent point is at this position 
		return the index of the created point or the pre-existing point at this position.
	'''
	for key in self.keysfor(pt):
		if key in self.dict:
			return self.dict[key]
	self.dict[self.keyfor(pt)] = l = len(self.points)
	self.points.append(pt)
	return l

remove(pt)

remove the point at given position point from the set, returning its former index. raise if no point exist at this position

Source code in madcad/hashing.py

def remove(self, pt) -> int:
	''' 
		remove the point at given position point from the set, returning its former index.
		raise if no point exist at this position
	'''
	for key in self.keysfor(pt):
		if key in self.dict:
			return self.dict.pop(key)
	else:					
		raise IndexError("position doesn't exist in set")

discard(pt)

remove all points at positions equivalent to the given location (if any)

Source code in madcad/hashing.py

def discard(self, pt):
	''' remove all points at positions equivalent to the given location (if any) '''
	for key in self.keysfor(pt):
		if key in self.dict:
			del self.dict[key]

__getitem__(pt)

return the index of the point at given location in the set

Source code in madcad/hashing.py

def __getitem__(self, pt) -> int:
	''' return the index of the point at given location in the set '''
	for key in self.keysfor(pt):
		if key in self.dict:	return self.dict[key]
	raise IndexError("position doesn't exist in set")

__contains__(pt)

true if there is a point at the given location in the set

Source code in madcad/hashing.py

def __contains__(self, pt) -> bool:
	''' true if there is a point at the given location in the set '''
	for key in self.keysfor(pt):
		if key in self.dict:	return True
	return False

__add__(iterable)

Source code in madcad/hashing.py

def __add__(self, iterable):
	s = PointSet(self.cellsize)
	s.update(self.points)
	s.update(iterable)
	return s

__sub__(iterable)

Source code in madcad/hashing.py

def __sub__(self, iterable):
	s = PointSet(self.cellsize)
	s.update(self.points)
	s.difference_update(iterable)
	return s

Asso(iter=None)

Bases: object

Associative container. This is a sort dict that stores as many values as we want for each key. The return value for a key is then always an iterable of the associated values, even when the value set to the key is unique and is not an iterator.

Asso(iterable) the iterable must yields (key,value) pairs Asso(keys=[], values=[]) build form existing lists, assuming they are already sorted

Source code in madcad/hashing.py

def __init__(self, iter=None):
	if isinstance(iter, Asso):
		self._table = dict(iter.table)
	else:
		self._table = {}
		if iter:
			self.update(iter)

__getitem__(key)

return an iterable of the objects associated to the given key

Source code in madcad/hashing.py

def __getitem__(self, key):
	''' return an iterable of the objects associated to the given key '''
	i = 0
	while True:
		k = (i,key)
		if k not in self._table:
			break
		yield self._table[k]
		i += 1

__contains__(key)

return True if key is associated to something

Source code in madcad/hashing.py

def __contains__(self, key):
	''' return True if key is associated to something '''
	return (0,key) in self._table

add(key, value)

associate a new value to this key

Source code in madcad/hashing.py

def add(self, key, value):
	''' associate a new value to this key '''
	i = 0
	while True:
		k = (i,key)
		if k not in self._table:
			self._table[k] = value
			return
		i += 1

remove(key, value)

Source code in madcad/hashing.py

def remove(self, key, value):
	l = self.connexity(key)-1
	i = l
	while i>=0:
		k = (i,key)
		if self._table[k] == value:
			last = (l,key)
			self._table[k] = self._table[last]
			del self._table[last]
			return
		i -= 1
	raise KeyError('key not in table')

discard(key, value)

remove all (key,value) pair of that table

Source code in madcad/hashing.py

def discard(self, key, value):
	''' remove all (key,value) pair of that table '''
	l = self.connexity(key)-1
	i = l
	while i>=0:
		k = (i,key)
		if self._table[k] == value:
			last = (l,key)
			self._table[k] = self._table[last]
			del self._table[last]
			l -= 1
		i -= 1

update(other)

append all key,value associations to this Asso

Source code in madcad/hashing.py

def update(self, other):
	''' append all key,value associations to this Asso '''
	if isinstance(other, dict):
		other = other.items()
	for k,v in other:
		self.add(k,v)

__add__(other)

Source code in madcad/hashing.py

def __add__(self, other):
	new = Asso()
	new._table = dict(self._table)
	new.update(other)
	return new

clear()

empty the container

Source code in madcad/hashing.py

def clear(self):
	''' empty the container '''
	self._table.clear()

items()

iterator of (key, value) pairs

Source code in madcad/hashing.py

def items(self):
	''' iterator of (key, value) pairs '''
	for k,v in self._table.items():
		yield k[1],v

keys()

iterator of the keys

Source code in madcad/hashing.py

def keys(self):
	''' iterator of the keys '''
	for k,v in self._table:
		yield k[1]

values()

iterator of the values

Source code in madcad/hashing.py

def values(self):
	''' iterator of the values '''
	return self._table.values()

connexity(key)

return the number of values associated to the given key

Source code in madcad/hashing.py

def connexity(self, key):
	''' return the number of values associated to the given key '''
	i = 0
	while True:
		k = (i,key)
		if k not in self._table:
			break
		i += 1
	return i