Polytopes

Polytope mathematical functions. More...

Collaboration diagram for Polytopes:

Files
file	polytope.scad
	Polytope shapes, conversions, properties, and tests functions.

General
function	polytope_faces2edges (f)
	List the edge coordinate index pairs of a polytope. More...
function	polytope_line (c, f, e, i, l, r=false)
	Get a line from an edge or any two vetices of a polytope. More...
function	polytope_limits (c, f, a, d, s=true)
	Determine the bounding limits of a polytope. More...
function	polytope_bounding_box_pf (c, f, a)
	Generate a bounding box polytope for another polytope in 3d or 2d. More...
function	polytope_ft_triangulate (f)
	Triangulate the faces of a convex polytope using fan triangulation. More...

Adjacents
function	polytope_vertex_adjacent_vertices (f, i)
	List the adjacent vertices for a given polytope vertex. More...
function	polytope_vertex_adjacent_faces (f, i)
	List the adjacent face indexes for a polytope vertex. More...
function	polytope_edge_adjacent_faces (f, e, i)
	List the adjacent face indexes for a polytope edge. More...

Normals
function	polytope_vertex_normal (c, f, i)
	Get a normal vector for a polytope vertex. More...
function	polytope_edge_normal (c, f, e, i)
	Get a normal vector for a polytope edge. More...
function	polytope_face_normal (c, f, i, l, cw=true)
	Get the normal vector of a polytope face. More...

Faces
function	polytope_face_mean (c, f, i, l)
	Get the mean coordinate of all vertices of a polytope face. More...
function	polytope_face_mean_normal (c, f, i, l, cw=true)
	Get the mean coordinate and normal vector of a polytope face. More...
function	polytope_face_plane (c, f, i, l, cw=true)
	Get a plane defined by the mean coordinate and normal vector of a polytope face. More...
function	polytope_face_vertex_counts (f)
	List the vertex counts for all polytope faces. More...
function	polytope_face_angles (c, f, cw=true)
	List the angles between all adjacent faces of a polyhedron. More...

Edges
function	polytope_edge_lengths (c, e)
	List the edge lengths of a polytope. More...
function	polytope_edge_angles (c, f)
	List the adjacent edge angles for each polytope vertex. More...

Tests
function	polytope_faces_are_regular (c, f, e, d=6)
	Test if the faces of a polytope are all regular. More...

Usage Details

Polytope mathematical functions.

Validation Summary

file	group	script	results	no test	skipped	passed	failed	warning
math/polytope.scad	Polytopes	Script	Results	19	0	0	0	0

No Failures

See complete validation results.

Requires:
include <omdl-base.scad>;

Conventions

• Coordinates are given as [[x, y, z], ...] in 3d or [[x, y], ...] in 2d. Each face in f is an ordered list of coordinate indexes into c.
• For polygons f is optional; when omitted the listed order of c forms the single implicit path.
• Face vertex indexes are ordered clockwise when viewed from outside the solid (right-hand rule outward normal). The cw parameter defaults to true (clockwise); set it to false to negate the returned normal for counter-clockwise faces.
• Normals are derived from the first three vertices of a face only. A collinear first triple produces a zero normal vector silently. Normal vectors are not normalised to unit length unless stated.
• To identify a face, l (explicit index list) takes precedence over i (index into f). Passing both is permitted; l wins silently. Returns undef when a required identification is absent.
• Edges are represented as [[i0, i1], ...] sorted smallest-index-first. The optional e parameter is computed on-demand when omitted; callers iterating over edges must pre-compute and pass e explicitly.
• Functions whose names include the ft infix use fan triangulation, which is correct for convex faces only. Fan triangulation preserves vertex winding; use an ear-clipping triangulator for concave faces.
• Lengths and bounding-box values are in the units of c. Angles are in degrees.

Function and/or Module Documentation

polytope_faces2edges()

function polytope_faces2edges

(

f

)

List the edge coordinate index pairs of a polytope.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.

Returns

<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes that form the shape.

Note

Although the edge list is not sorted, each pair is sorted with the smallest index first.

Here is the caller graph for this function:

polytope_line()

function polytope_line	(	c	,
		f	,
		e	,
		i	,
		l	,
		r	= false
	)

Get a line from an edge or any two vetices of a polytope.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
e	<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes.
i	<integer> A line specified as an edge index.
l	<integer-list-2> A line specified as a list of coordinate index pairs.
r	<boolean> Reverse the start and end points of the line specified as an edge index i.

Returns

<line-3d | line-2d> The line as a pair of coordinates.

Two mutually exclusive methods identify the line:

• When l is defined it takes precedence over i. The line is constructed directly from the two coordinate indexes in l and neither f nor e is consulted. r has no effect in this path.
• When only i is given the edge list is used to look up the two endpoint indexes. r reverses the returned point order: when false (default) the line runs from el[i][0] to el[i][1]; when true it runs from el[i][1] to el[i][0].

Returns undef when neither l nor i is provided.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

When e is not specified, it is computed from f using polytope_faces2edges() iff the line is identified by i.

polytope_limits()

function polytope_limits	(	c	,
		f	,
		a	,
		d	,
		s	= true
	)

Determine the bounding limits of a polytope.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d cartesian coordinates [[x, y (, z)], ...].
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
a	<decimal-list-1:3 | decimal> The box padding. A list of lengths to equally pad the box dimensions.
d	<range|list|integer> The dimensions to consider. A range of dimensions, a list of dimensions, or a single dimension.
s	<boolean> Return box size rather than coordinate limits.

Returns

<datastruct> The bounding-box limits (see: table).

The returned datastruct will be one of the following forms:

	s	x	y	z	datastruct form
2d	false	[min,max]	[min,max]	-	decimal-list-2-list-2
2d	true	max-min	max-min	-	decimal-list-list-2
3d	false	[min,max]	[min,max]	[min,max]	decimal-list-2-list-3
3d	true	max-min	max-min	max-min	decimal-list-list-3

Note

When f is not specified, all coordinates are used to determine the geometric limits, which, simplifies the calculation. Parameter f is needed when a subset of the coordinates should be considered.

When d is not specified, a check will be performed to see if all coordinates of c are 3, 2, or 1 dimensional and, if so, all axes for the determined dimension will be used for d.

Warning

This function does not track secondary shapes subtraction as implemented by the polygon() function.

Here is the caller graph for this function:

polytope_bounding_box_pf()

function polytope_bounding_box_pf	(	c	,
		f	,
		a
	)

Generate a bounding box polytope for another polytope in 3d or 2d.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d cartesian coordinates [[x, y (, z)], ...].
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
a	<decimal-list-1:3 | decimal> The box padding. A list of lengths to equally pad the box dimensions.

Returns

<datastruct> A structure: (1) [points, faces], where points are <points-3d> and faces are a <integer-list-list>, that define the bounding box of the given polyhedron. Or: (2) [points, path], where points are <points-2d> and path is a <integer-list-list>, that define the bounding box of the given polygon.

Polyhedron faces will be ordered clockwise when looking from outside the shape inwards. Polygon path will be ordered clockwise when looking from the top (positive z) downwards.

Note

When f is not specified, all coordinates are used to determine the geometric limits, which, simplifies the calculation. Parameter f is needed when a subset of the coordinates should be considered.

See also

polytope_limits for warning about secondary Shapes.

polytope_ft_triangulate()

function polytope_ft_triangulate

(

f

)

Triangulate the faces of a convex polytope using fan triangulation.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.

Returns

<integer-list-3-list> A list of triangular faces that enclose the polytope, where each face is a list of exactly three coordinate indexes.

Each n-vertex face produces n-2 triangles by fanning from its first vertex: triangle k is [fi[0], fi[k], fi[k+1]] for k in [1, n-2]. Vertex winding is preserved: all output triangles inherit the winding direction of their source face, so outward normals remain consistent with the input. The total number of output triangles equals the sum of (vertex_count - 2) over all input faces.

See Wikipedia for more information on fan triangulation.

Warning

Fan triangulation is only correct for convex faces. Concave faces will produce overlapping or inverted triangles. For concave polytopes use an ear-clipping triangulator instead.

polytope_vertex_adjacent_vertices()

function polytope_vertex_adjacent_vertices	(	f	,
		i
	)

List the adjacent vertices for a given polytope vertex.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> A vertex index.

Returns

<integer-list> The list of adjacent vertex indexes for the given vertex index.

The adjacent vertices are those neighboring vertices that are directly connected to the given vertex by a common edge. The returned list contains coordinate indexes, not coordinates; pass them into c to obtain the actual points. The result is deduplicated so each adjacent vertex index appears exactly once, even when it is shared by multiple faces.

polytope_vertex_adjacent_faces()

function polytope_vertex_adjacent_faces	(	f	,
		i
	)

List the adjacent face indexes for a polytope vertex.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The vertex index.

Returns

<integer-list> The list of face indexes adjacent to the given polytope vertex.

polytope_edge_adjacent_faces()

function polytope_edge_adjacent_faces	(	f	,
		e	,
		i
	)

List the adjacent face indexes for a polytope edge.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
e	<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes.
i	<integer> The edge index.

Returns

<integer-list> The list of face indexes adjacent to the given polytope edge.

Note

When e is not specified, it is computed from f using polytope_faces2edges().

polytope_vertex_normal()

function polytope_vertex_normal	(	c	,
		f	,
		i
	)

Get a normal vector for a polytope vertex.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The vertex index.

Returns

<vector-3d> A normal vector for the polytope vertex.

The normal is computed as the mean of the adjacent faces.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

Here is the caller graph for this function:

polytope_edge_normal()

function polytope_edge_normal	(	c	,
		f	,
		e	,
		i
	)

Get a normal vector for a polytope edge.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
e	<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes.
i	<integer> The edge index.

Returns

<vector-3d> A normal vector for the polytope edge.

The normal is computed as the mean of the adjacent faces.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

When e is not specified, it is computed from f using polytope_faces2edges().

Here is the caller graph for this function:

polytope_face_normal()

function polytope_face_normal	(	c	,
		f	,
		i	,
		l	,
		cw	= true
	)

Get the normal vector of a polytope face.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The face specified as an face index.
l	<integer-list> The face-plane specified as a list of three or more coordinate indexes that are a part of the face.
cw	<boolean> Face vertex ordering. When true the face vertices are assumed to be wound clockwise when viewed from outside the solid, and the returned normal points outward (away from the interior). When false the vertices are assumed counter-clockwise and the normal is negated.

Returns

<vector-3d> The normal vector of a polytope face.

The face can be identified using either parameter i or l. When using l, the parameter f is not required.

The normal is computed from the first three vertices of the resolved face only. For triangulated faces this is exact. For higher-arity faces (quads, n-gons) the first three vertices must not be collinear; if they are, the returned vector will be a zero vector. Callers working with untriangulated meshes should ensure the face is planar and that its first three vertices form a non-degenerate triangle.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

Here is the caller graph for this function:

polytope_face_mean()

function polytope_face_mean	(	c	,
		f	,
		i	,
		l
	)

Get the mean coordinate of all vertices of a polytope face.

Face Identification Convention

Several functions in this group accept two mutually exclusive parameters for identifying a face:

• i <integer> selects the face by its index into f.
• l <integer-list> provides the face directly as an explicit list of coordinate indexes (e.g. a single face from f, or a custom subset).

When l is defined it takes precedence over i and f is not consulted. When only i is given, f must be provided (except for polygons, where the implicit single-path default applies). Passing both l and i is permitted; l wins silently.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The face specified as an face index.
l	<integer-list> The face specified as a list of all the coordinate indexes that define it.

Returns

<points-3d> The mean coordinate of a polytope face.

The face can be identified using either parameter i or l. When using l, the parameter f is not required.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

Here is the caller graph for this function:

polytope_face_mean_normal()

function polytope_face_mean_normal	(	c	,
		f	,
		i	,
		l	,
		cw	= true
	)

Get the mean coordinate and normal vector of a polytope face.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The face specified as a face index.
l	<integer-list> The face specified as a list of all the coordinate indexes that define it.
cw	<boolean> Face vertex ordering. Passed directly to polytope_face_normal(); see that function for the full description. Default true (clockwise, outward normals).

Returns

<plane> [mp, nv], where mp is a point-3d giving the mean of all face vertices, and nv is a vector-3d giving the face normal. Together they fully define the face-plane and can be passed directly to any function that expects a plane argument.

Combines polytope_face_mean() and polytope_face_normal() into a single call. The face can be identified using either i or l; see the Face Identification Convention for the precedence rule.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

This function is an alias for polytope_face_plane(). It is retained for compatibility with existing call sites. Prefer polytope_face_plane() in new code.

polytope_face_plane()

function polytope_face_plane	(	c	,
		f	,
		i	,
		l	,
		cw	= true
	)

Get a plane defined by the mean coordinate and normal vector of a polytope face.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d coordinate points.
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
i	<integer> The face specified as a face index.
l	<integer-list> The face specified as a list of all the coordinate indexes that define it.
cw	<boolean> Face vertex ordering. Passed directly to polytope_face_normal(); see that function for the full description. Default true (clockwise, outward normals).

Returns

<plane> [mp, nv], where mp is a point-3d giving the mean of all face vertices, and nv is a vector-3d giving the face normal. Together they fully define the face-plane and can be passed directly to any function that expects a plane argument.

Combines polytope_face_mean() and polytope_face_normal() into a single call. The face can be identified using either i or l; see the Face Identification Convention for the precedence rule.

Note

Parameter f is optional for polygons. When it is not given, the listed order of the coordinates c establishes the polygon path.

polytope_face_vertex_counts()

function polytope_face_vertex_counts

(

f

)

List the vertex counts for all polytope faces.

Parameters

f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.

Returns

<integer-list> A list with a vertex count of every face.

polytope_face_angles()

function polytope_face_angles	(	c	,
		f	,
		cw	= true
	)

List the angles between all adjacent faces of a polyhedron.

Parameters

c	<points-3d> A list of 3d cartesian coordinates [[x, y, z], ...].
f	<integer-list-list> A list of faces that enclose the shape where each face is a list of coordinate indexes.
cw	<boolean> Face vertex ordering. Passed directly to polytope_face_normal(); see that function for the full description. Default true (clockwise, outward normals).

Returns

<decimal-list> A list of angles (in degrees) between the normal vectors of every pair of adjacent faces. Each entry is the angle between the outward normals of two faces that share at least one vertex, which equals the supplement of the interior dihedral angle (i.e. 180° minus the interior dihedral angle for a convex edge).

For each face i, all faces that share at least one vertex are found and the angle between their respective normal vectors is computed via angle_ll(). Both normals are obtained by delegating to polytope_face_normal() with the same cw convention, so the result is consistent regardless of mesh winding.

The normal of each face is derived from its first three vertices only; see polytope_face_normal() for the implications of this for non-triangulated or degenerate faces.

See Wikipedia for more information on dihedral angles.

Warning

Each adjacent face pair appears twice in the output list (once from face i's perspective and once from face u's), so the list length equals twice the number of adjacent face pairs.

polytope_edge_lengths()

function polytope_edge_lengths	(	c	,
		e
	)

List the edge lengths of a polytope.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d cartesian coordinates [[x, y (, z)], ...].
e	<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes.

Returns

<decimal-list> A list of the polytope edge lengths.

polytope_edge_angles()

function polytope_edge_angles	(	c	,
		f
	)

List the adjacent edge angles for each polytope vertex.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d cartesian coordinates [[x, y (, z)], ...].
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.

Returns

<decimal-list> A list of the polytope adjacent edge angles.

polytope_faces_are_regular()

function polytope_faces_are_regular	(	c	,
		f	,
		e	,
		d	= 6
	)

Test if the faces of a polytope are all regular.

Parameters

c	<points-3d | points-2d> A list of 3d or 2d cartesian coordinates [[x, y (, z)], ...].
f	<integer-list-list> A list of faces (or paths) that enclose the shape where each face is a list of coordinate indexes.
e	<integer-list-2-list> A list of edges where each edge is a list of two coordinate indexes.
d	<integer> The number of significant figures to retain when rounding lengths and angles before comparing them for uniqueness. Increase d to tighten the comparison tolerance; decrease it to allow more floating-point variation. Default 6.

Returns

<boolean> true when all edge lengths are equal and all adjacent edge angles are equal (to d significant figures), false otherwise.

All edge lengths are collected via polytope_edge_lengths() and all adjacent edge angles via polytope_edge_angles(). Each list is rounded to d significant figures with round_s() and then deduplicated with unique(). The polytope is considered regular iff both deduplicated lists contain exactly one distinct value.

Note that this tests geometric regularity of the edges and vertex angles, not full face regularity. For a polyhedron with non-planar or non-congruent faces, the test may return true even though the faces are not regular polygons.

Note

When e is not specified, it is computed from f using polytope_faces2edges().