Detailed Description

a geometric tree where every nodes has geometry information attached.

The geometry relations are as follows

Child node's geometries lie in their parents geometries.
Sibling's geometries have zero intersection.
The union of all child node's geometries equals a parent's geometry.
The geometries are of arbitrary dimension and can be defined by an arbitrary number of coordinates.

The main features of this class are

Routines to split the geometries and to create new childs are provided.
The leaf nodes can be accessed over a sorted or an unsorted index.
We can check in ${\cal O}(\log)$ -time in which node's geometry a certain coordinate lies.

details

The nodes store the following information:

a number with the ID of the first child of this node or 0 indicating a leaf node
the ncoords coordinates describing the node's geometry.

So every node has a size of 1 + ncoords * dimension.

We distinguish between three enumerations of nodes:

a "node ID" is given to every node in the tree and does not change during a refinement for nodes that are unchanged.
a "leaf element index" is a consecutive enumeration of leaf indices which does not change for unchanged leaf nodes during a refinement
a "sorted leaf element index" is a consecutive enumeration of leaf indices enumerating the leaf elements from left-to-right.

Definition at line 1 of file XPartMap.m.

List of all members.

Public Member Functions
function XPartMap copy =	copy ()
	deep copy for an XPartMap instance
	XPartMap ( dimension, ncoords, init_coords, level1_splits)
	constructor creating an XPartMap with one single root node.
function elems =	coords2elem ( tcoords)
	returns element IDs of leaf nodes whose geometries host the given coordinates.
function new_vec =	split ( iind, split_point)
	default implementation for the splitting of one node's geometry
function [ changed_ids , new_ids ] =	refine ( iinds, split_points)
	refines nodes given by indices at given points
function bary =	barycenter ( iind)
	computes the barycenter of a node's geometry
function yes =	intersect ( coords, iind)
	checks whether a geometric entity intersects with another one given by a node's ID
function ok =	is_inside ( coord, iind)
	checks whether a given coord lies in a node's geometry
function [ XPartMap sxm , old_leaf_enum ] =	sub_xpart_map ( coords)
	creates new object holding a subset of the current XPartMap lying in the region specified by `coords`
function coords =	get_coords ( iind)
	helper function rearranging the vector of node coordinates into a matrix with row vectors as coordinates.
Static Public Member Functions
static function ce =	crop_entity ( coords1, coords2)
	helper function computing the actual intersection of two geometries given by their coordinates.
Public Attributes
	dimension = 1
	dimension of geometries
	ncoords = 2
	number of coordinates defining a geometry
	intervals = "[0 0 1]"
	actual tree with attached geometries
	split_size = 2
	integer specifying how many children are created at refinement step
	leaf_ids = 0
	an `unsorted` enumeration of the leaf indices
	leaf_enum = 0
	a `sorted` enumeration of the leaf indices.
	refine_levels = 0
	A vector which stores the refinement level for every node.
	siz
	the number of the leaf nodes
	skip
	storage size of a single tree node pair `(c, coords)`
	max_level
	the maximum refinement level of the tree
	noof_ids
	the number of node IDs in the tree

Constructor & Destructor Documentation

XPartMap.XPartMap	(	dimension,
		ncoords,
		init_coords,
		level1_splits
	)

constructor creating an XPartMap with one single root node.

Parameters:

dimension	dimension of geometries
ncoords	number of coordinates defining a geometry
init_coords	initial coordinates for the root node's geometry.
level1_splits	level1 splits

Definition at line 209 of file XPartMap.m.

Member Function Documentation

function bary = XPartMap.barycenter ( iind )

computes the barycenter of a node's geometry

Parameters:

iind	node ID of the node whose gemoetry's barycenter shall be computed

Return values:

bary	coordinate vector of the barycenter.

Definition at line 453 of file XPartMap.m.

function elems = XPartMap.coords2elem ( tcoords )

returns element IDs of leaf nodes whose geometries host the given coordinates.

Parameters:

tcoords n x dimension matrix of n coordinate (row) vectors for which the enclosing entity ID shall be determined.

Return values:

elems a n vector holding the element IDs.

Definition at line 258 of file XPartMap.m.

function XPartMap copy = XPartMap.copy ( )

deep copy for an XPartMap instance

Return values:

copy	the copied object

Definition at line 189 of file XPartMap.m.

function ce = XPartMap.crop_entity	(	coords1,
		coords2
	)	`[static]`

helper function computing the actual intersection of two geometries given by their coordinates.

Parameters:

coords1	first `2 x dimension` matrix of cube extreme point coordinates.
coords2	second `2 x dimension` matrix of cube extreme point coordinates.

Return values:

ce	intersection of the two geometries given by the two arguments.

Definition at line 633 of file XPartMap.m.

function coords = XPartMap.get_coords ( iind )

helper function rearranging the vector of node coordinates into a matrix with row vectors as coordinates.

Parameters:

iind	the node's ID

Return values:

coords the rearranged coordinates. (ncoords x dimension matrix)

Definition at line 617 of file XPartMap.m.

function yes = XPartMap.intersect	(	coords,
		iind
	)

checks whether a geometric entity intersects with another one given by a node's ID

Parameters:

coords	`2 x dimension` matrix describing the geometric entity
iind	ID of other node entity

Return values:

yes	boolean flag indicating whether the intersection exists

Definition at line 468 of file XPartMap.m.

function ok = XPartMap.is_inside	(	coord,
		iind
	)

checks whether a given coord lies in a node's geometry

Parameters:

coord	the coordinate vector of length `dimension`.
iind	ID of node entity to check with

Return values:

ok	boolean flag

Definition at line 521 of file XPartMap.m.

function [ changed_ids , new_ids ] = XPartMap.refine	(	iinds,
		split_points
	)

refines nodes given by indices at given points

Parameters:

iinds	a vector of node IDs for elements that shall be refined.
split_points	a matrix with row vectors of points are given to the split() method as second argument. This argument is optional. (default = barycenter)

Return values:

changed_ids	vector of the IDs of the nodes that were changed during the refinement.
new_ids	vector of the IDs of the nodes that were newly created during the refinement.

Definition at line 366 of file XPartMap.m.

function new_vec = XPartMap.split	(	iind,
		split_point
	)

default implementation for the splitting of one node's geometry

This split works as follows

If split_size is equal to 2^(dimension), the geometry is split in each of the dimension directions.
If split_size is equal to 2, the geometry is split in the direction where the geometry has its widest extent.

Parameters:

iind	the node's ID
split_point	an optional matrix with coordinate vectors specifying where the geometry shall be split. (default=barycenter)

Return values:

new_vec vector with coordinates of new geometries.

Definition at line 312 of file XPartMap.m.

function [ XPartMap sxm , old_leaf_enum ] = XPartMap.sub_xpart_map ( coords )

creates new object holding a subset of the current XPartMap lying in the region specified by coords

Parameters:

coords a 2xdimension matrix describing the region in which all the nodes of the resulting XPartMap shall lie.

Return values:

sxm	an object holding a subset of the current map.
old_leaf_enum	old leaf enum

Generated fields of sxm:

intervals — intervals
refine_levels — refine levels
leaf_ids — leaf ids
leaf_enum — leaf enum

Definition at line 546 of file XPartMap.m.

Member Data Documentation

XPartMap.dimension = 1

dimension of geometries

Default: 1

Definition at line 44 of file XPartMap.m.

XPartMap.intervals = "[0 0 1]"

actual tree with attached geometries

This stores a list of pairs (c, coords) of the index of the first child c and the geometry coordinates coords. If c is equal to 0, the node is a leaf node. The first pair is the root node of the tree.

Default: "[0 0 1]"

Definition at line 60 of file XPartMap.m.

XPartMap.leaf_enum = 0

a sorted enumeration of the leaf indices.

This set is constructed by a deep traversal of the tree, with left-to-right enumeration of leafs.

Default: 0

Definition at line 93 of file XPartMap.m.

XPartMap.leaf_ids = 0

an unsorted enumeration of the leaf indices

If a leaf has not been refined, it keeps its position in this set.

Default: 0

Definition at line 82 of file XPartMap.m.