Polygons

Polygon mathematical functions; 2-polytope. More...

Collaboration diagram for Polygons:

Files
file	polygon.scad
	Polygon shapes, conversions, properties, and tests functions.

Shapes
function	polygon_regular_p (n, r, a, c=origin2d, o=0, vr, cw=true)
	Compute coordinates for an n-sided regular polygon in 2D. More...
function	polygon_line_p (p1=origin2d, p2=x_axis2d_uv, l, x, y, r, fs, ft, fn=1)
	Compute coordinates along a line in 2D. More...
function	polygon_arc_p (r=1, c=origin2d, v1=x_axis2d_uv, v2=x_axis2d_uv, fn, cw=true)
	Compute coordinates of an arc with constant radius between two vectors in 2D. More...
function	polygon_elliptical_sector_p (r=1, c=origin2d, v1=x_axis2d_uv, v2=x_axis2d_uv, s=true, fn, cw=true)
	Compute coordinates for an elliptical sector in 2D. More...
function	polygon_trapezoid_p (b=1, h, l=1, a=90, o=origin2d, cw=true)
	Compute the coordinates for a rounded trapezoid in 2D space. More...

Properties
function	polygon_regular_perimeter (n, r, a)
	Compute the perimeter of an n-sided regular polygon in 2D. More...
function	polygon_regular_area (n, r, a)
	Compute the area of an n-sided regular polygon in 2D. More...
function	polygon_perimeter (c, p)
	Calculate the perimeter length of a polygon in 2d. More...
function	polygon_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	polygon_centroid (c, p)
	Compute the center of mass of a polygon in a Euclidean 2d-space. More...
function	polygon_winding (c, p, t)
	Compute the winding number of a polygon about a point in a Euclidean 2d-space. More...

Tests
function	polygon_is_clockwise (c, p)
	Test the vertex ordering of a polygon in a Euclidean 2d-space. More...
function	polygon_is_convex (c, p)
	Test the convexity of a polygon in a Euclidean 2d-space. More...
function	polygon_wn_is_p_inside (c, p, t)
	Test if a point is inside a polygon in a Euclidean 2d-space using winding number. More...
function	polygon_as_is_p_inside (c, p, t)
	Test if a point is inside a polygon in a Euclidean 2d-space using angle summation. More...

Transforms
function	polygon_linear_extrude_pf (c, p, h=1, centroid=false, center=false)
	Convert a polygon in 2D to a polyhedron by adding a height dimension. More...

Rounding
function	polygon_round_eve_p (r=1, m=1, c=origin2d, v1=x_axis2d_uv, v2=y_axis2d_uv, fn, cw=true)
	Compute coordinates for a constant radius vertex round between two edge vectors in 2D. More...
function	polygon_round_eve_all_p (c, vr=0, vrm=1, vfn, w=true, cw=true)
	Compute coordinates that round all of the vertices between each adjacent edges in 2D. More...

Interpreter
function	polygon_turtle_p (s, i=origin2d, c=0)
	Generate list of coordinate points from simple operation step notation. More...

Detailed Description

Polygon mathematical functions; 2-polytope.

Requires:
include <omdl-base.scad>;

Function Documentation

polygon3d_area()

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.

When p is not defined, the listed order of the coordinates will be used.

Warning

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

polygon_arc_p()

function polygon_arc_p	(	r	= 1,
		c	= origin2d,
		v1	= x_axis2d_uv,
		v2	= x_axis2d_uv,
		fn	,
		cw	= true
	)

Compute coordinates of an arc with constant radius between two vectors in 2D.

Parameters

r	<decimal> The arc radius.
c	<point-2d> The arc center coordinate [x, y].
v1	<line-2d | decimal> The arc start angle. A 2d line, vector, or decimal angle 1.
v2	<line-2d | decimal> The arc end angle. A 2d line, vector, or decimal angle 2.
fn	<integer> The number of [facets] (optional).
cw	<boolean> Sweep clockwise along arc from the head of vector v1 to the head of vector v2 when cw = true, and counter clockwise when cw = false.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

The arc coordinates will have radius r centered about c contained within the heads of vectors v1 and v2. The arc will start at the point coincident to v1 and will end at the point coincident to v2. When vectors v1 and v2 are parallel, the arc will be a complete circle. When fn is undefined, its value is determined by get_fn().

Here is the caller graph for this function:

polygon_area()

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

When p is not defined, the listed order of the coordinates will be used.

Warning

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

polygon_as_is_p_inside()

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

When p is not defined, the listed order of the coordinates will be used.

Warning

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

polygon_centroid()

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

When p is not defined, the listed order of the coordinates will be used.

Warning

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

Here is the caller graph for this function:

polygon_elliptical_sector_p()

function polygon_elliptical_sector_p	(	r	= 1,
		c	= origin2d,
		v1	= x_axis2d_uv,
		v2	= x_axis2d_uv,
		s	= true,
		fn	,
		cw	= true
	)

Compute coordinates for an elliptical sector in 2D.

Parameters

r	<decimal-list-2 | decimal> The elliptical radius. A list [rx, ry] of decimals or a single decimal for (rx=ry).
c	<point-2d> The center coordinate [x, y].
v1	<line-2d | decimal> The sector angle 1. A 2d line, vector, or decimal.
v2	<line-2d | decimal> The sector angle 2. A 2d line, vector, or decimal.
s	<boolean> Use signed vector angle conversions. When false, positive angle conversion will be used.
fn	<integer> The number of [facets] (optional).
cw	<boolean> The coordinate point ordering.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

The coordinates will be between angle 1 and angle 2 and will be ordered clockwise. The sector sweep direction can be controlled by the sign of the angles. When fn is undefined, its value is determined by get_fn().

Here is the caller graph for this function:

polygon_is_clockwise()

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

When p is not defined, the listed order of the coordinates will be used.

polygon_is_convex()

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

When p is not defined, the listed order of the coordinates will be used.

polygon_line_p()

function polygon_line_p	(	p1	= origin2d,
		p2	= x_axis2d_uv,
		l	,
		x	,
		y	,
		r	,
		fs	,
		ft	,
		fn	= 1
	)

Compute coordinates along a line in 2D.

Parameters

p1	<point-2d> The line initial coordinate [x, y].
p2	<point-2d> The line terminal coordinate [x, y].
l	<line-2d> The line or vector.
x	<decimal-list | decimal> A list of x coordinates [x1, x2, ...] or a single x coordinate at which to interpolate along the line.
y	<decimal-list | decimal> A list of y coordinates [y1, y2, ...] or a single y coordinate at which to interpolate along the line.
r	<decimal-list | decimal> A list of ratios [r1, r2, ...] or a single ratio r. The position ratio along line p1 (r=0) to p2 (r=1).
fs	<decimal> A fixed segment size between each point along the line.
ft	<decimal> A fixed segment size between each point, centered, beginning at p1 and terminating at p2.
fn	<integer> A fixed number of equally spaced points.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

Linear interpolation is used to compute each point along the line. The order of precedence for line specification is: l then p1 and p2. The order of precedence for interpolation is: x, y, r, fs, ft, fn.

Here is the caller graph for this function:

polygon_linear_extrude_pf()

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

Convert a polygon in 2D 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.

When p is not defined, the listed order of the coordinates will be used.

polygon_perimeter()

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

When p is not defined, the listed order of the coordinates will be used.

polygon_regular_area()

function polygon_regular_area	(	n	,
		r	,
		a
	)

Compute the area of an n-sided regular polygon in 2D.

Parameters

n	<integer> The number of sides.
r	<decimal> The vertex circumradius of the circumcircle.
a	<decimal> The inradius of the incircle.

Returns

<decimal> Area of the n-sided regular polygon.

The radius can be specified by either the circumradius r or the inradius a. If both are specified, r is used.

polygon_regular_p()

function polygon_regular_p	(	n	,
		r	,
		a	,
		c	= origin2d,
		o	= 0,
		vr	,
		cw	= true
	)

Compute coordinates for an n-sided regular polygon in 2D.

Parameters

n	<integer> The number of sides.
r	<decimal> The circumradius of the circumcircle.
a	<decimal> The inradius of the incircle.
c	<point-2d> The center coordinate [x, y].
o	<decimal> The rotational angular offset.
vr	<decimal> The vertex rounding radius.
cw	<boolean> Use clockwise point ordering.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

The radius can be specified by either the circumradius r or the inradius a. If both are specified, r is used.

Example

vr=5;
 
hull()
{
  for ( p = polygon_regular_p( r=20, n=5, vr=vr ) )
    translate( p )
    circle( r=vr );
}

See Wikipedia for more information.

Here is the caller graph for this function:

polygon_regular_perimeter()

function polygon_regular_perimeter	(	n	,
		r	,
		a
	)

Compute the perimeter of an n-sided regular polygon in 2D.

Parameters

n	<integer> The number of sides.
r	<decimal> The vertex circumradius of the circumcircle.
a	<decimal> The inradius of the incircle.

Returns

<decimal> Perimeter length of the n-sided regular polygon.

The radius can be specified by either the circumradius r or the inradius a. If both are specified, r is used.

Here is the caller graph for this function:

polygon_round_eve_all_p()

function polygon_round_eve_all_p	(	c	,
		vr	= 0,
		vrm	= 1,
		vfn	,
		w	= true,
		cw	= true
	)

Compute coordinates that round all of the vertices between each adjacent edges in 2D.

Parameters

c	<coords-2d> A list of n 2d cartesian coordinates [[x1, y1], [x2, y2], ..., [xn, yn]].
vr	<decimal-list-n | decimal> The vertices rounding radius. A list [v1r, v2r, v3r, ... vnr] of n decimals or a single decimal for (v1r=v2r=v3r= ... =vnr). Undefined vertices are not rounded.
vrm	<integer-list-n | integer> The vertices rounding mode. A list [v1rm, v2rm, v3rm, ... vnrm] of n integers or a single integer for (v1rm=v2rm=v3rm= ... =vnrm). Undefined vertices are not rounded.
vfn	<integer-list-n> The vertices arc fragment number. A list [v1fn, v2fn, v3fn, ... vnfn] of n integers or a single integer for (v1fn=v2fn=v3fn= ... =vnfn).
w	<boolean> Wrap-at-end during 3-point coordinate selection.
cw	<boolean> Polygon vertex ordering.

Returns

<coords-2d> A new list of coordinates points [[x, y], ...] that define the polygon with rounded vertices.

Assumes polygon is defined in 2D space on the x-y plane. There should be no repeating adjacent vertices along the polygon path (ie: no adjacent vertex with identical coordinates). Any vertex determined to be collinear with its adjacent previous and next vertex is returned unmodified.

Each vertex may be individually rounded using one of the following modes:

mode	name	description
0	none	return vertex unchanged
1	round	previous to next edge round
2	e-hollow / i-circle	previous to next edge inverse round
3	n-fillet	next edge pass return fillet
4	p-fillet	previous edge pass return fillet
5	chamfer	previous to next edge bevel
6	e-circle / i-hollow	previous to next edge inverse round
7	n-round	next edge pass return round
8	p-round	previous edge pass return round
9	n-chamfer	next edge pass return bevel
10	p-chamfer	previous edge pass return bevel

The following diagrams demonstrate each rounding mode by on the upper right vertex of a rectangular polygon.

Rounding modes diagram

top_1	top_2	top_3	top_4	top_5
top_6	top_7	top_8	top_9	top_10

Vertex arc fragments can be specified using vfn. When any vnfn is undef, the special variables $fa, $fs, and $fn control facet generation. Each vertex is processed using 3-point (the previous and following vertex). The resulting triangle incircles and excircles are used to create the round and fillet arc segments. All arcs and chamfers use constant radius.

Rounding example script

    include <omdl-base.scad>;
 
    $fn=36;
 
    c = [[1,1], [1,10], [10,12], [18,2]];
    r = [1, 1, 5, 8];
    m = [2, 3, 4, 3];
    n = [3, 8, undef, undef];
 
    p = polygon_round_eve_all_p(c=c, vr=r, vrm=m, vfn=n);
 
    polygon( p );
 
    // end_include

Rounding example diagram

top

Here is the caller graph for this function:

polygon_round_eve_p()

function polygon_round_eve_p	(	r	= 1,
		m	= 1,
		c	= origin2d,
		v1	= x_axis2d_uv,
		v2	= y_axis2d_uv,
		fn	,
		cw	= true
	)

Compute coordinates for a constant radius vertex round between two edge vectors in 2D.

Parameters

r	<decimal> The round radius.
m	<integer> The round mode.
c	<point-2d> The round center coordinate [x, y].
v1	<line-2d | decimal> The round start angle. A 2d line, vector, or decimal angle 1.
v2	<line-2d | decimal> The round end angle. A 2d line, vector, or decimal angle 2.
fn	<integer> The number of facets.
cw	<boolean> The coordinate point ordering.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

Normally, angle 1 should be less than angle 2. The edge coordinates will start at angle 1, end at angle 2, and will have radius r along a rounded transition from edge 1 to 2. When cw = true the coordinates will start at edge 1 and increase toward edge 2. When cw = false this ordering is reversed.

The round mode may be one of the following:

mode	name	description
1	fillet	fillet from one edge to the next
2	round	round from one edge to the next
3	chamfer	bevel from one edge to the next

Here is the caller graph for this function:

polygon_trapezoid_p()

function polygon_trapezoid_p	(	b	= 1,
		h	,
		l	= 1,
		a	= 90,
		o	= origin2d,
		cw	= true
	)

Compute the coordinates for a rounded trapezoid in 2D space.

Parameters

b	<decimal-list-2 | decimal> The base lengths. A list [b1, b2] of 2 decimals or a single decimal for (b1=b2).
h	<decimal> The perpendicular height between bases.
l	<decimal> The left side leg length.
a	<decimal> The angle between the lower base and left leg.
o	<point-2d> The origin offset coordinate [x, y].
cw	<boolean> Polygon vertex ordering.

Returns

<coords-2d> A list of coordinates points [[x, y], ...].

When both h and l are specified, h has precedence. The function generates parallelograms, rectangles, and squares with the appropriate parameter assignments. See Wikipedia for more general information on trapezoids.

Here is the caller graph for this function:

polygon_turtle_p()

function polygon_turtle_p	(	s	,
		i	= origin2d,
		c	= 0
	)

Generate list of coordinate points from simple operation step notation.

Parameters

s	<datastruct> The list of steps.
i	<point-2d> The initial coordinate [x, y].
c	<integer> (an internal recursion step count)

Returns

<point-2d-list> The list of coordinate points.

This function is a simple interpreter that converts a list of operation steps into coordinate points for the construction of polygons. It provides a convenient way to construct polygons using a simple notation. It is inspired by the implementation of the Turtle graphics geometric drawing language. Each step produces a new output point or points and follow the following schema:

Data structure schema:

name	schema
s	[ step, step, ..., step ]
step	[ operation, arguments ]
arguments	[ arg, arg, ..., arg ]

The following table summarized the available operations and their semantics.

operation	short	arguments	output coordinate point
move_xy	mxy	[x, y]	[x, y]
move_x	mx	x	[x, i.y]
move_y	my	y	[i.x, y]
delta_xy	dxy	[x, y]	i + [x, y]
delta_x	dx	x	i + [x, 0]
delta_y	dy	y	i + [0, y]
delta_xa	dxa	[x, a]	i + [ x, x * tan(a) ]
delta_ya	dya	[y, a]	i + l y / tan(a), y ]
delta_v	dv	[m, a]	i + line(m, a)
arc_pv	apv	[c, v, cw]	(see below)
arc_vv	avv	[v, v, cw]	(see below)

When an operation requires only one argument, the argument can be specified as a scalar-value or a single-element list.

Operations

arc_pv

e	data type	parameter description
c	<point-2d>	arc center point [x, y]
v	<point-2d> | <decimal>	arc stop angle [x, y] or a
cw	<boolean>	arc sweep direction

This operation constructs an arc about the center point, specified as a point coordinate. The arc begins at the angle formed by the vector [c, i] and ends at the vector formed by either [c, v] or the angle v (specified in degrees). The arc sweep direction is controlled by the parameter cw. When cw is assigned true, the arc is swept clockwise from the start angle to the stop angle.

arc_vv

e	data type	parameter description
c	<point-2d>	arc center point [m, a]
v	<point-2d> | <decimal>	arc stop angle [x, y] or a
cw	<boolean>	arc sweep direction

This operation constructs an arc about the center point, specified as a vector [m, a] beginning from the start point. The arc begins at the angle formed by the vector [c, i] and ends at the vector formed by either [c, v] or the angle v (specified in degrees). The arc sweep direction is controlled by the parameter cw. When cw is assigned true, the arc is swept clockwise from the start angle to the stop angle.

Motor mount plate design example script

    include <omdl-base.scad>;
 
    $fn=36;
 
    h1 = 7.5;   h2 = 5;     h3 = 7.5;
    w1 = 5;     w2 = 20;    w3 = 5;
    r1 = 5;     r2 = 1/2;   rr = 1;
 
    sm =
    [
      ["delta_y",  h1],
      ["delta_x",  w1],
      ["delta_y",  h2],
      ["delta_xy", [w3, h3]],
      ["delta_x",  w1+w2-w3*2],
      ["delta_xy", [w3, -h3]],
      ["move_y",   0],
      ["move_x",   0],
    ];
 
    // convert the step moves into coordinates
    pp = polygon_turtle_p( sm );
 
    // round all of the vertices
    rp = polygon_round_eve_all_p( pp, rr );
 
    difference()
    {
      polygon( rp );
 
      c = [w1+w2/2+r1/2, h1+h2/2];
      translate(c) circle(r=r1);
      for(x=[-1,1], y=[-1,1]) translate(c+[x,y]*r1) circle(r=r2);
    }
 
    // end_include

Motor mount plate design example diagram

top	diag

The corners of this example 2d design plate have been rounded with the library function polygon_round_eve_all_p().

Here is the caller graph for this function:

polygon_winding()

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

When p is not defined, the listed order of the coordinates will be used.

Warning

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

polygon_wn_is_p_inside()

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

When p is not defined, the listed order of the coordinates will be used.

See also

polygon_winding for warning about secondary Shapes.