Polygon and polyhedron mathematical functions. More...

Collaboration diagram for Polytopes:

Files
file	math_polytope.scad
	Polygon and polyhedron mathematical functions.

Functions
function	polytope_faces2edges (f)
	List the edge coordinate index pairs of a polytope. More...

function	polytope_limits (c, f, a, d=[0:2], s=true)
	Determine the bounding limits of a polytope. More...

function	polytope_bbox_pf (c, f, a)
	Generate a bounding box polytope for another polytope in 3d or 2d. 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_vertex_av (f, i)
	List the adjacent vertices for a given polytope vertex. More...

function	polytope_vertex_af (f, i)
	List the adjacent face indexes for a polytope vertex. More...

function	polytope_edge_af (f, e, i)
	List the adjacent face indexes for a polytope edge. More...

function	polytope_vertex_n (c, f, i)
	Get a normal vector for a polytope vertex. More...

function	polytope_edge_n (c, f, e, i)
	Get a normal vector for a polytope edge. More...

function	polytope_face_n (c, f, i, l, cw=true)
	Get the normal vector of a polytope face. More...

function	polytope_face_m (c, f, i, l)
	Get the mean coordinate of all vertices of a polytope face. More...

function	polytope_face_mn (c, f, i, l, cw=true)
	Get the mean coordinate and normal vector of a polytope face. More...

function	polytope_plane (c, f, i, l, cw=true)
	Get a plane for a polytope face. More...

function	polytope_face_vcounts (f)
	List the vertex counts for all polytope faces. More...

function	polytope_face_angles (c, f)
	List the angles between all adjacent faces of a polyhedron. More...

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...

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

function	polytope_triangulate_ft (f)
	Triangulate the faces of a convex polytope using fan triangulation. More...

function	polygon2d_perimeter (c, p)
	Calculate the perimeter length of a polygon in 2d. More...

function	polygon2d_area (c, p, s=false)
	Compute the signed area of a polygon in a Euclidean 2d-space. More...

function	polygon3d_area (c, p, n)
	Compute the area of a polygon in a Euclidean 3d-space. More...

function	polygon2d_centroid (c, p)
	Compute the center of mass of a polygon in a Euclidean 2d-space. More...

function	polygon2d_is_cw (c, p)
	Test the vertex ordering of a polygon in a Euclidean 2d-space. More...

function	polygon2d_is_convex (c, p)
	Test the convexity of a polygon in a Euclidean 2d-space. More...

function	polygon2d_winding (c, p, t)
	Compute the winding number of a polygon about a point in a Euclidean 2d-space. More...

function	polygon2d_is_pip_wn (c, p, t)
	Test if a point is inside a polygon in a Euclidean 2d-space using winding number. More...

function	polygon2d_is_pip_as (c, p, t)
	Test if a point is inside a polygon in a Euclidean 2d-space using angle summation. More...

function	polyhedron_area (c, f)
	Compute the surface area of a polyhedron in a Euclidean 3d-space. More...

function	polyhedron_volume_tf (c, f)
	Compute the volume of a triangulated polyhedron in a Euclidean 3d-space. More...

function	polyhedron_centroid_tf (c, f)
	Compute the center of mass of a triangulated polyhedron in a Euclidean 3d-space. More...

function	linear_extrude_pp2pf (c, p, h=1, centroid=false, center=false)
	Convert a polygon to a polyhedron by adding a height dimension. More...

Detailed Description

Polygon and polyhedron mathematical functions.

Function Documentation

function linear_extrude_pp2pf	(	c	,
		p	,
		h	= `1`,
		centroid	= `false`,
		center	= `false`
	)

Convert a polygon to a polyhedron by adding a height dimension.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
h	<decimal> The polyhedron height.
centroid	<boolean> Center polygon centroid at z-axis.
center	<boolean> Center polyhedron height about xy-plane.

Returns: <datastruct> A structure [points, faces], where points are <coords-3d> and faces are a <integer-list-list>, that define the bounding box of the given polyhedron.

Note: When p is not given, the listed order of the coordinates c establishes the path.

function polygon2d_area	(	c	,
		p	,
		s	= `false`
	)

Compute the signed area of a polygon in a Euclidean 2d-space.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
s	<boolean> Return the vertex ordering sign.

Returns: <decimal> The area of the given polygon.

See Wikipedia for more information.

Note: When p is not given, the listed order of the coordinates c establishes the path.

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

function polygon2d_centroid	(	c	,
		p
	)

Compute the center of mass of a polygon in a Euclidean 2d-space.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.

Returns: <point-2d> The center of mass of the given polygon.

See Wikipedia for more information.

Note: When p is not given, the listed order of the coordinates c establishes the path.

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

function polygon2d_is_convex	(	c	,
		p
	)

Test the convexity of a polygon in a Euclidean 2d-space.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.

Returns: <boolean> true if the polygon is convex, false otherwise.

Note: When p is not given, the listed order of the coordinates c establishes the path.

function polygon2d_is_cw	(	c	,
		p
	)

Test the vertex ordering of a polygon in a Euclidean 2d-space.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.

Returns: <boolean> true if the vertex are ordered clockwise, false if the vertex are counterclockwise ordered, and undef if the ordering can not be determined.

Note: When p is not given, the listed order of the coordinates c establishes the path.

function polygon2d_is_pip_as	(	c	,
		p	,
		t
	)

Test if a point is inside a polygon in a Euclidean 2d-space using angle summation.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
t	<point-2d> A test point coordinate [x, y].

Returns: <boolean> true when the point is inside the polygon and false otherwise.

See Wikipedia for more information.

Note: When p is not given, the listed order of the coordinates c establishes the path.

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

function polygon2d_is_pip_wn	(	c	,
		p	,
		t
	)

Test if a point is inside a polygon in a Euclidean 2d-space using winding number.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
t	<point-2d> A test point coordinate [x, y].

Returns: <boolean> true when the point is inside the polygon and false otherwise.

Note: When p is not given, the listed order of the coordinates c establishes the path.

See also: polygon2d_winding for warning about secondary Shapes.

function polygon2d_perimeter	(	c	,
		p
	)

Calculate the perimeter length of a polygon in 2d.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.

Returns: <decimal> The sum of all polygon primary and secondary perimeter lengths.

Note: When p is not given, the listed order of the coordinates c establishes the path.

function polygon2d_winding	(	c	,
		p	,
		t
	)

Compute the winding number of a polygon about a point in a Euclidean 2d-space.

Parameters

c	<coords-2d> A list of 2d cartesian coordinates [[x, y], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
t	<point-2d> A test point coordinate [x, y].

Returns: <integer> The winding number.

Computes the winding number, the total number of counterclockwise turns that the polygon paths makes around the test point in a Euclidean 2d-space. Will be 0 iff the point is outside of the polygon. Function patterned after Dan Sunday, 2012.

Copyright

Copyright 2000 softSurfer, 2012 Dan Sunday This code may be freely used and modified for any purpose providing that this copyright notice is included with it. iSurfer.org makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application.

Note: When p is not given, the listed order of the coordinates c establishes the path.

Warning: Where there are secondary paths, the vertex ordering of each must be the same as the primary path.

function polygon3d_area	(	c	,
		p	,
		n
	)

Compute the area of a polygon in a Euclidean 3d-space.

Parameters

c	<coords-3d> A list of 3d cartesian coordinates [[x, y, z], ...].
p	<integer-list-list> An optional list of paths that define one or more closed shapes where each is a list of coordinate indexes.
n	<vector-3d> An optional normal vector, [x, y, z], to the polygon plane. When not given, a normal vector is constructed from the first three points of the primary path.

Returns: <decimal> The area of the given polygon.

Function patterned after Dan Sunday, 2012.

Note: When p is not given, the listed order of the coordinates c establishes the path.

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

function polyhedron_area	(	c	,
		f
	)

Compute the surface area of a polyhedron in a Euclidean 3d-space.

Parameters

c	<coords-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.

Returns: <decimal> The surface area of the given polyhedron.

function polyhedron_centroid_tf	(	c	,
		f
	)

Compute the center of mass of a triangulated polyhedron in a Euclidean 3d-space.

Parameters

c	<coords-3d> A list of 3d cartesian coordinates [[x, y, z], ...].
f	<integer-list-3-list> A list of triangular faces that enclose the polyhedron where each face is a list of three coordinate indexes.

Returns: <point-3d> The center of mass of the given polyhedron.

See Wikipedia for more information on centroid determined via the divergence theorem and midpoint quadrature.

Note: All faces are assumed to be a union of triangles oriented clockwise from the outside inwards.

function polyhedron_volume_tf	(	c	,
		f
	)

Compute the volume of a triangulated polyhedron in a Euclidean 3d-space.

Parameters

c	<coords-3d> A list of 3d cartesian coordinates [[x, y, z], ...].
f	<integer-list-3-list> A list of triangular faces that enclose the polyhedron where each face is a list of three coordinate indexes.

Returns: <decimal> The volume of the given polyhedron.

See Wikipedia for more information on volumes determined using the divergence theorem.

Note: All faces are assumed to be a union of triangles oriented clockwise from the outside inwards.

function polytope_bbox_pf	(	c	,
		f	,
		a
	)

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

Parameters

c	<coords-3d\|coords-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 <coords-3d> and faces are a <integer-list-list>, that define the bounding box of the given polyhedron. Or: (2) [points, path], where points are <coords-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.

function polytope_edge_af	(	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().

function polytope_edge_angles	(	c	,
		f
	)

List the adjacent edge angles for each polytope vertex.

Parameters

c	<coords-3d\|coords-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.

function polytope_edge_lengths	(	c	,
		e
	)

List the edge lengths of a polytope.

Parameters

c	<coords-3d\|coords-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.

function polytope_edge_n	(	c	,
		f	,
		e	,
		i
	)

Get a normal vector for a polytope edge.

Parameters

c	<coords-3d\|coords-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() iff the line is identified by i.

Here is the caller graph for this function:

function polytope_face_angles	(	c	,
		f
	)

List the angles between all adjacent faces of a polyhedron.

Parameters

c	<coords-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.

Returns: <decimal-list> A list of the polyhedron adjacent face angles.

See Wikipedia for more information on dihedral angles.

function polytope_face_m	(	c	,
		f	,
		i	,
		l
	)

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

Parameters

c	<coords-3d\|coords-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: <coords-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:

function polytope_face_mn	(	c	,
		f	,
		i	,
		l	,
		cw	= `true`
	)

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

Parameters

c	<coords-3d\|coords-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.
cw	<boolean> Face vertex ordering.

Returns: <plane> [mp, nv], where mp is coords-3d, the mean coordinate, and nv is vector-3d, the normal vector, of the polytope face-plane.

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.

function polytope_face_n	(	c	,
		f	,
		i	,
		l	,
		cw	= `true`
	)

Get the normal vector of a polytope face.

Parameters

c	<coords-3d\|coords-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.

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.

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:

function polytope_face_vcounts ( 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.

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:

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

Test if the faces of a polytope are all regular.

Parameters

c	<coords-3d\|coords-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 used when comparing lengths and angles.

Returns: <boolean> true when there is both a single edge length and a single edge angle and false otherwise.

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

function polytope_limits	(	c	,
		f	,
		a	,
		d	= `[0:2]`,
		s	= `true`
	)

Determine the bounding limits of a polytope.

Parameters

c	<coords-3d\|coords-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> A list with the bounding-box limits (see: table).

The returned list will be of the following form:

	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.

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

Here is the caller graph for this function:

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	<coords-3d\|coords-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 line start and end points.

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

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.

function polytope_plane	(	c	,
		f	,
		i	,
		l	,
		cw	= `true`
	)

Get a plane for a polytope face.

Parameters

c	<coords-3d\|coords-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.
cw	<boolean> Face vertex ordering.

Returns: <plane> [mp, nv], where mp is coords-3d, the mean coordinate, and nv is vector-3d, the normal vector, of the polytope face-plane.

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.

function polytope_triangulate_ft ( 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 three coordinate indexes with vertex ordering is maintained.

See Wikipedia for more information on fan triangulation.

Warning: This method does not support concave polytopes.

function polytope_vertex_af	(	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.

function polytope_vertex_av	(	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.

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

function polytope_vertex_n	(	c	,
		f	,
		i
	)

Get a normal vector for a polytope vertex.

Parameters

c	<coords-3d\|coords-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:

c	<coords-3d\|coords-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.

Files

Functions

Detailed Description

Function Documentation