geometry

Module of cythonized functions for basic computational geometry in 2 and 3 dimensions. This modules requires geometric objects (e.g. polygons, polyhedra, surfaces, segments, etc.) to be described as a collection of simplices (i.e. segments or triangles). In this module, geometric objects in D-dimensional space are described with an (N, D) array of vertices and and (M, D) array describing the indices of vertices making up each simplex. As an example, the unit square in two dimensions can be described as collection of line segments:

>>> vertices = [[0.0, 0.0],
                [1.0, 0.0],
                [1.0, 1.0],
                [0.0, 1.0]]
>>> simplices = [[0, 1],
                 [1, 2],
                 [2, 3],
                 [3, 0]]

A three dimensional cube can similarly be described as a collection of triangles:

>>> vertices = [[0.0, 0.0, 0.0],
                [0.0, 0.0, 1.0],
                [0.0, 1.0, 0.0],
                [0.0, 1.0, 1.0],
                [1.0, 0.0, 0.0],
                [1.0, 0.0, 1.0],
                [1.0, 1.0, 0.0],
                [1.0, 1.0, 1.0]]
>>> simplices = [[1, 0, 4],
                 [5, 1, 4],
                 [7, 1, 5],
                 [3, 1, 7],
                 [0, 1, 3],
                 [2, 0, 3],
                 [0, 2, 6],
                 [4, 0, 6],
                 [5, 4, 7],
                 [4, 6, 7],
                 [2, 3, 7],
                 [6, 2, 7]]

This module is primarily used to find whether and where line segments intersect a geometric object and whether points are contained within a closed geometric object. For example, one can determine whether a collection of points, saved as points, are contained within a geometric object, defined by vertices and simplices with the command

>>> contains(points, vertices, simplices)

which returns a boolean array.

One can find the number of times a collection of line segments, defined by start_points and end_points, intersect a geometric object with the command

>> intersection_count(start_points, end_points, vertices, simplices)

which returns an array of the number of simplices intersected by each segment. If it is known that a collection of line segments intersect a geometric object then the intersection point can be found with the command

>> intersection(start_points, end_points, vertices, simplices)

This returns an (N, D) float array of intersection points, and an (N,) int array identifying which simplex the intersection occurred at. If a line segment does not intersect the geometric object then the above command returns a ValueError. If there are multiple intersections for a single segment then only the first detected intersection will be returned.

There are numerous other packages which can perform the same tasks as this module. For example, Shapely can perform these 2-D operations (and more robustly), but the point in polygon testing is too slow for RBF purposes. GDAL is another option and that seems to now have python bindings that are sufficiently fast. This module may eventually turn into a wrapper from some GDAL functions.

rbf.pde.geometry.contains(points, vertices, simplices)

Returns a boolean array identifying whether the points are contained within a closed simplicial complex. The simplicial complex is described by vertices and simplices. This function works for 2 and 3 spatial dimensions.

Parameters:

• points ((N, D) array) – Test points

• vertices ((M, D) array) – Vertices of the simplicial complex

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

out ((N,) bool array) – Indicates which test points are in the simplicial complex

Notes

This function does not ensure that the simplicial complex is closed. If it is not then bogus results will be returned.

This function determines whether a point is contained within the simplicial complex by finding the number of intersections between each point and an arbitrary outside point. It is possible, although rare, that this function will fail if the line segment intersects a simplex at an edge.

This function does not require any particular orientation for the simplices

rbf.pde.geometry.intersection_count(start_points, end_points, vertices, simplices)

Returns the number of simplices crossed by the line segments. The line segments are described by start_points and end_points. This function works for 2 and 3 spatial dimensions.

Parameters:

• start_points ((N, D) array) – Vertices describing one end of the line segments. N is the number of line segments and D is the number of dimensions

• end_points ((N, D) array) – Vertices describing the other end of the line segments

• vertices ((M, D) array) – Vertices within the simplicial complex. M is the number of vertices

• simplices ((P, D) array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

out ((N,) int array) – Intersection counts

rbf.pde.geometry.intersection_point(start_points, end_points, vertices, simplices)

Returns the intersection between line segments and a simplicial complex. The line segments are described by start_points and end_points, and the simplicial complex is described by vertices and simplices. This function works for 2 and 3 spatial dimensions.

Parameters:

• start_points ((N, D) float array) – Vertices describing one end of the line segments. N is the number of line segments and D is the number of dimensions

• end_points ((N, D) float array) – Vertices describing the other end of the line segments.

• vertices ((M, D) float array) – Vertices within the simplicial complex. M is the number of vertices.

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

• out ((N, D) float array) – The points where the line segments intersect the simplicial complex

• out ((N,) int array) – The index of the simplex that the line segments intersect

Notes

This function fails when a intersection is not found for a line segment. If there are multiple intersections then the intersection closest to start_point is used.

rbf.pde.geometry.nearest_point(points, vertices, simplices)

Returns the nearest point on the simplicial complex for each point in points. This works for 2 and 3 spatial dimensions.

Parameters:

• points ((N,D) array) – Test points

• vertices ((M,D) array) – Vertices of the simplicial complex

• simplices ((P,D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

• (N, D) float array – The nearest points on the simplicial complex

• (N,) int array – The simplex that the nearest point is on

rbf.pde.geometry.oriented_simplices(vertices, simplices)

Returns simplex indices that are ordered such that each simplex normal vector, as defined by the right hand rule, points outward

Parameters:

• vertices ((M, D) array) – Vertices within the simplicial complex

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

out ((P,D) int array) – Oriented simplices

Notes

If one dimensional simplices are given, then the simplices are returned unaltered.

This function does not ensure that the simplicial complex is closed. If it is not then bogus results will be returned.

rbf.pde.geometry.simplex_normals(vertices, simplices)

Returns the normal vectors for each simplex. Orientation is determined by the right hand rule

Parameters:

• vertices ((M, D) array) – Vertices within the simplicial complex

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

out ((P, D) array) – normals vectors

Notes

This is only defined for two and three dimensional simplices

rbf.pde.geometry.simplex_outward_normals(vertices, simplices)

Returns the outward normal vectors for each simplex. The sign of the returned vectors are only meaningful if the simplices enclose an area in two-dimensional space or a volume in three-dimensional space

Parameters:

• vertices ((M, D) array) – Vertices within the simplicial complex

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

Returns:

out ((P, D) array) – normals vectors

Notes

This is only defined for two and three dimensional simplices

rbf.pde.geometry.volume(vert, smp, orient=True)

Returns the volume of a polyhedra or area of a polygon

Parameters:

• vertices ((M, D) array) – Vertices within the simplicial complex

• simplices ((P, D) int array) – Connectivity of the vertices. Each row contains the vertex indices which form one simplex of the simplicial complex

• orient (bool, optional) – If true, the simplices are reordered with oriented_simplices. The time for this function increase quadratically with the number of simplices. Set to false if you are confident that the simplices are properly oriented. This does nothing for one-dimensional simplices

Returns:

out (float)

Notes

This function does not ensure that the simplicial complex is closed and does not intersect itself. If it is not then bogus results will be returned.