geom - Basic 2D geometry package

geom.const

Commonly used constants used in the geometry package.

The following read-only constants are defined:

EPSILON: A small floating point value which is the maximum

numeric distance between two floating point numbers for them to be considered equal.

EPSILON_PRECISION: The number of digits after the decimal point of

EPSILON.

EPSILON_FLOAT_FMT: A format string for displaying numbers that

have PRECISION number of digits after the decimal point.

The tolerance value (EPSILON) must be set once (and only once) before using the geometry package. This is enforced.

Useful values are small numbers in the range of 1e-09 to 1e-05. It depends on the application and the size of numbers used with the package.

If set_epsilon() is not called by the user then a default value will be set the first time the EPSILON attribute is accessed. It cannot then be modified.

geom.const.TAU = 6.283185307179586

Commonly used constant PI*2

geom.const.EPSILON = 1e-06

Tolerance value used for floating point comparisons

geom.const.EPSILON2 = 1e-12

Handy for comparing distance**2 when avoiding sqrt

geom.const.EPSILON_PRECISION = 6

Number of digits after decimal point

geom.const.EPSILON_FLOAT_FMT = u'%.6f'

Format string for float values that matches precision

geom.const.set_epsilon(value)

Set the global absolute error tolerance value and rounding limit for approximate floating point comparison operations. This value is accessible via the geom.EPSILON global variable.

The default value of 1e-06 is suitable for values that are in the ‘countable range’. You may need a larger epsilon when using large absolute values, and a smaller value for very small values close to zero. Otherwise approximate comparison operations may not behave as expected.

In general, this should be called only once before using any modules that refer to EPSILON.

Parameters:value – Float tolerance value.

geom.const.float_eq(value1, value2)

Compare two floats for equality. The two float are considered equal if the difference between them is less than EPSILON.

For a discussion of floating point comparisons see:

http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

Parameters:

• value1 – Float value
• value2 – Float value

Returns:

True if the two values are approximately equal.

geom.const.is_zero(value)

Determine if the float value is essentially zero.

A shortcut for float_eq(n, 0.0).

geom.const.float_round(value)

Round the value to a rounding precision corresponding to EPSILON.

geom.transform2d

Basic 2D affine transform matrix operations.

---

geom.transform2d.is_identity_transform(m)

Return True if the matrix is the identity matrix.

geom.transform2d.compose_transform(m1, m2)

Combine two matrices by multiplying them.

Parameters:

• m1 – 2X3 2D transform matrix.
• m2 – 2X3 2D transform matrix.

Note

m2 is applied before (to) m1

geom.transform2d.matrix_rotate(angle, origin=(0.0, 0.0))

Create a transform matrix to rotate about the origin.

Parameters:

• angle – Rotation angle in radians.
• origin – Optional rotation origin. Default is (0,0).

Returns:

A transform matrix as 2x3 tuple

geom.transform2d.matrix_translate(x, y)

Create a transform matrix to translate (move).

Parameters:

• x – translation along X axis
• y – translation along Y axis

Returns:

A transform matrix as 2x3 tuple

geom.transform2d.matrix_scale(scale_x, scale_y, origin=None)

Create a transform matrix to scale.

Parameters:

• scale_x – X axis scale factor
• scale_y – Y axis scale factor
• origin – Optional scale origin. Default is (0,0).

Returns:

A transform matrix as 2x3 tuple

geom.transform2d.matrix_scale_translate(scale_x, scale_y, offset_x, offset_y)

Create a transform matrix to scale and translate.

Parameters:

• scale_x – X axis scale factor
• scale_y – Y axis scale factor
• offset_x – translation along X axis
• offset_y – translation along Y axis

Returns:

A transform matrix as 2x3 tuple

geom.transform2d.matrix_skew_x(angle)

Create a transform matrix to skew along X axis by angle.

Parameters:angle – Angle in radians to skew. Returns:A transform matrix as 2x3 tuple

geom.transform2d.matrix_skew_y(angle)

Create a transform matrix to skew along Y axis by angle.

Parameters:angle – Angle in radians to skew. Returns:A transform matrix as 2x3 tuple

geom.transform2d.matrix_apply_to_point(matrix, p)

Return a copy of p with the transform matrix applied to it.

geom.transform2d.canonicalize_point(p, origin, theta)

Canonicalize the point so that the origin is (0, 0) and axis rotation is zero.

This just rotates then translates the point.

Parameters:

• p – The point to canonicalize (x, y).
• origin – The origin offset as a 2-tuple (X, Y).
• theta – The axis rotation angle.

Returns:

A point as 2-tuple

geom.point

Basic 2D point/vector.

class geom.point.P

Two dimensional immutable point (vector).

Represented as a simple tuple (x, y) so that it is compatible with many other libraries.

If y is None x is assumed to be a tuple or list containing both x and y.

Parameters:

• x – X coordinate. Type float.
• y – Y coordinate. Type float.

x

The X (horizontal) coordinate.

y

The Y (vertical) coordinate.

static max_point()

Create a point with max X and Y values.

static min_point()

Create a point with min X and Y values.

static from_polar(r, angle)

Create a Cartesian point from polar coordinates.

See http://en.wikipedia.org/wiki/Polar_coordinate_system

Parameters:

• r – Magnitude (radius)
• angle – Angle in radians

Returns:

A point.

to_polar()

Return the polar coordinates of this vector as a tuple containing the magnitude (radius) and angle respectively (r, a).

is_zero()

Return True if X and Y are both within EPSILON distance to zero.

almost_equal(other, tolerance=None)

Compare points for geometric equality.

Parameters:

• other – Vector (point) being compared. A 2-tuple (x, y).
• tolerance – Max distance between the two points. Default is EPSILON.

Returns:

True if distance between the points < tolerance.

length()

The length or scalar magnitude of the vector.

Returns:Distance from (0, 0).

length2()

The square of the length of the vector.

unit()

The vector scaled to unit length. If the vector length is zero, a null (0, 0) vector is returned.

Returns:A copy of this vector scaled to unit length. Return type:P

normal(left=True)

Return a vector perpendicular to this one.

Parameters:left – left of vector if True, otherwise right. Default is True.

mirror()

This vector flipped 180d

dot(other)

Compute the dot product with another vector.

Equivalent to |p1|*|p2|*cos(theta) where theta is the angle between the two vectors.

See:

http://en.wikipedia.org/wiki/Dot_product

Parameters:other – The vector with which to compute the dot product. A 2-tuple (x, y). Returns:A scalar dot product.

cross(other)

Compute the cross product with another vector. Also called the perp-dot product for 2D vectors. Also called determinant for 2D matrix.

See:

http://mathworld.wolfram.com/PerpDotProduct.html http://www.gamedev.net/topic/441590-2d-cross-product/

From Woodward: The cross product generates a new vector perpendicular to the two that are being multiplied, with a length equal to the (ordinary) product of their lengths.

Parameters:other – The vector with which to compute the cross product. Returns:A scalar cross product.

angle()

The angle of this vector relative to the x axis in radians.

Returns:A float value between -pi and pi.

angle2(p1, p2)

The angle formed by p1->self->p2.

The angle is negative if p1 is to the left of p2.

Parameters:

• p1 – First point as 2-tuple (x, y).
• p2 – Second point as 2-tuple( x, y).

Returns:

The angle in radians between -pi and pi. Returns 0 if points are coincident.

ccw_angle2(p1, p2)

The counterclockwise angle formed by p1->self->p2.

Parameters:

• p1 – First point as 2-tuple (x, y).
• p2 – Second point as 2-tuple( x, y).

Returns:

An angle in radians between 0 and 2*math.pi.

bisector(p1, p2)

The bisector between the angle formed by p1->self->p2.

Parameters:

• p1 – First point as 2-tuple (x, y).
• p2 – Second point as 2-tuple (x, y).

Returns:

A unit vector with origin at self.

distance(p)

Euclidean distance from this point to another point.

Parameters:p – The other point as a 2-tuple (x, y). Returns:The Euclidean distance.

distance2(p)

Euclidean distance squared to other point. This can be used to compare distances without the expense of a sqrt.

distance_to_line(p1, p2)

Euclidean distance from this point to it’s normal projection on a line that intersects the given points.

See:

http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/

Parameters:

• p1 – First point on line.
• p2 – Second point on line.

Returns:

Normal distance to line.

normal_projection(p)

The unit distance from the origin that corresponds to the projection of the specified point on to the line described by this vector.

Parameters:p – A vector (point) as 2-tuple (x, y).

inside_triangle2D(A, B, C)

Test if this point lies inside the triangle defined by points A, B, and C. Where ABC is clockwise or counter-clockwise.

See http://www.sunshine2k.de/stuff/Java/PointInTriangle/PointInTriangle.html

Parameters:

• A – First point of triangle as 2-tuple (x, y)
• B – Second point of triangle as 2-tuple (x, y)
• C – Third point of triangle as 2-tuple (x, y)

Returns:

True if this point lies within the triangle ABC.

orientation(p2, p3)

Determine the direction defined by the three points p1->p2->p3. p1 being this point.

Parameters:

• p2 – Second point as 2-tuple (x, y).
• p3 – Third point as 2-tuple (x, y).

Returns:

Positive if self->p2->p3 is clockwise (right), negative if counterclockwise (left), zero if points are colinear.

transform(matrix)

Return a copy of this point with the transform matrix applied to it.

rotate(angle, origin=(0.0, 0.0))

Return a copy of this point rotated about the origin by angle.

mag()

The length or scalar magnitude of the vector.

Returns:Distance from (0, 0).

normalized()

The vector scaled to unit length. If the vector length is zero, a null (0, 0) vector is returned.

Returns:A copy of this vector scaled to unit length. Return type:P

perpendicular(left=True)

Return a vector perpendicular to this one.

Parameters:left – left of vector if True, otherwise right. Default is True.

geom.line

Basic 2D line/segment geometry.

class geom.line.Line

Two dimensional immutable line segment defined by two points.

Parameters:

• p1 – Start point as 2-tuple (x, y).
• p2 – End point as 2-tuple (x, y).

static from_polar(startp, length, angle)

Create a Line given a start point, magnitude (length), and angle.

p1

The start point of this line segment.

p2

The end point of this line segment.

length()

Return the length of this line segment.

slope()

Return the slope of this line.

slope_intercept()

The slope-intercept equation for this line. Where the equation is of the form: y = mx + b, where m is the slope and b is the y intercept.

Returns:Slope and intercept as 2-tuple (m, b)

general_equation()

Compute the coefficients of the general equation of this line. Where the equation is of the form ax + by + c = 0.

See: http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml

Returns:A 3-tuple (a, b, c)

angle()

The angle of this line segment in radians.

start_tangent_angle()

The direction of this line segment from the start point in radians. This is the same as the angle. For Lines the start and end tangent angle are the same.

end_tangent_angle()

The direction of this line segment from the end point in radians. This is the same as the angle. For Lines the start and end tangent angle are the same.

bounding_box()

Bounding box.

transform(matrix)

Returns:A copy of this line with the transform matrix applied to it.

midpoint()

Returns:The midpoint of this line segment.

bisector()

Returns:A line that is perpendicular to and passes through the midpoint of this line. Also called the perpendicular bisector. Essentially this line segment is rotated 90deg about its midpoint.

offset(distance)

Offset of this line segment. :param distance: The distance to offset the line by.

Returns:A line segment parallel to this one and offset by distance. If offset is < 0 the offset line will be to the right of this line, otherwise to the left. If offset is zero or the line segment length is zero then this line is returned.

mu(p)

The unit distance from the first end point of this line segment to the specified collinear point. It is assumed that the point is collinear, but this is not checked.

subdivide(mu)

Subdivide this line into two lines at the given unit distance from the start point.

Parameters:mu – location of subdivision, where 0.0 < mu < 1.0 Returns:A tuple containing two Lines.

point_at(mu)

Return the point that is unit distance mu from this segment’s first point. The segment’s first point would be at mu=0.0 and the second point would be at mu=1.0.

Parameters:mu – Unit distance from p1 Returns:The point at mu

normal_projection(p)

Return the unit distance from this segment’s first point that corresponds to the projection of the specified point on to this line.

Parameters:p – point to project on to line Returns:A value between 0.0 and 1.0 if the projection lies between the segment endpoints. The return value will be < 0.0 if the projection lies south of the first point, and > 1.0 if it lies north of the second point.

normal_projection_point(p, segment=False)

Return the point on this line segment that corresponds to the projection of the specified point.

Parameters:

• p – point to project on to line
• segment – if True and if the point projection lies outside the two end points that define this line segment then return the closest endpoint. Default is False.

distance_to_point(p, segment=False)

Return the Euclidian distance from the specified point and its normal projection on to this line or segment.

See http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html http://paulbourke.net/geometry/pointlineplane/

Parameters:

• p – point to project on to line
• segment – if True and if the point projection lies outside the two end points that define this line segment then return the shortest distance to either of the two endpoints. Default is False.

intersection_mu(other, segment=False, seg_a=False, seg_b=False)

Line intersection.

http://paulbourke.net/geometry/pointlineplane/ and http://mathworld.wolfram.com/Line-LineIntersection.html

Parameters:

• other – line to test for intersection. A 4-tuple containing line endpoints.
• segment – if True then the intersection point must lie on both segments.
• seg_a – If True the intersection point must lie on this line segment.
• seg_b – If True the intersection point must lie on the other line segment.

Returns:

The unit distance from the segment starting point to the point of intersection if they intersect. Otherwise None if the lines or segments do not intersect.

intersection(other, segment=False, seg_a=False, seg_b=False)

Return the intersection point (if any) of this line and another line.

See:

<http://paulbourke.net/geometry/pointlineplane/> and <http://mathworld.wolfram.com/Line-LineIntersection.html>

Parameters:

• other – line to test for intersection. A 4-tuple containing line endpoints.
• segment – if True then the intersection point must lie on both segments.
• seg_a – If True the intersection point must lie on this line segment.
• seg_b – If True the intersection point must lie on the other line segment.

Returns:

A point if they intersect otherwise None.

intersects(other, segment=False)

Return True if this segment intersects another segment.

is_coincident(other, tolerance=None)

Return True if this line segment is coincident with another segment.

Parameters:

• other (tuple) – Another line segment as a 2-tuple of end point tuples.
• tolerance (float) – A floating point comparison tolerance. Default is geom.const.EPSILON.

is_parallel(other, inline=False)

Determine if this line segment is parallel with another line.

Parameters:

• other (tuple) – The other line as a tuple of two points.
• inline (bool) – The other line must also be inline with this segment.

Returns:

True if the other segment is parallel. If inline is

True then the other segment must also be inline. Otherwise False.

Return type:

bool

extend(amount, from_midpoint=False)

Return a Line segment that is longer (or shorter) than this line by amount amount.

Parameters:

• amount – The distance to extend the line. The line length will be increased by this amount. If amount is less than zero the length will be decreased.
• from_midpoint – Extend the line an equal amount on both ends relative to the midpoint. The amount length on both ends will be amount/2. Default is False.

Returns:

A new Line.

shift(amount)

Shift this segment forward or backwards by amount.

Parameters:amount – The distance to shift the line. If amount is less than zero the segment will be shifted backwards. Returns:A copy of this Line shifted by the specified amount.

which_side(p, inline=False)

Determine which side of this line a point lies.

Parameters:

• p – Point to test
• inline – If True return 0 if the point is inline. Default is False.

Returns:

1 if the point lies to the left of this line else -1. If inline is True and the point is inline then 0.

which_side_angle(angle, inline=False)

Determine which side of this line lies a vector from the second end point with the specified direction angle.

Parameters:

• angle – Angle in radians of the vector
• inline – If True return 0 if the point is inline.

Returns:

1 if the vector direction is to the left of this line else -1. If inline is True and the point is inline then 0.

same_side(pt1, pt2)

Return True if the given points lie on the same side of this line.

point_on_line(p, segment=False)

Return True if the point lies on the line defined by this segment.

Parameters:

• p (geom.Point) – the point to test
• segment – If True, the point must be collinear AND lie between the two endpoints. Default is False.

reversed()

Return a Line segment with start and end points reversed.

flipped()

Return a Line segment flipped 180deg around the first point.

to_svg_path()

Return a string with the SVG path ‘d’ attribute that corresponds with this line.

geom.arc

Basic 2D arc geometry.

Arc	Two dimensional immutable circular arc segment.

---

class geom.arc.Arc

Two dimensional immutable circular arc segment.

Parameters:

• p1 – Start point.
• p2 – End point.
• radius – Arc radius.
• angle – Arc angle described by p1->center->p2.
• center – Optional center of arc. Will be computed if not specified. Default is None.

static from_two_points_and_center(p1, p2, center, large_arc=False)

Create an Arc given two end points and a center point.

Since this would be ambiguous, a hint must be given as to which way the arc goes.

Parameters:

• p1 – Start point.
• p2 – End point.
• center – Center of arc.
• large_arc – If True the Arc will be on the large side (angle > pi). Default is False.

static from_two_points_and_tangent(p1, ptan, p2, reverse=False)

Create an Arc given two points and a tangent vector from p1->ptan.

Parameters:

• p1 – Start point.
• ptan – Tangent vector with origin at p1.
• p2 – End point.
• reverse – Reverse the resulting arc direction if True. Default is False.

Returns:

An Arc or None if the arc parameters are degenerate (i.e. if the endpoints are coincident or the start point and tangent vector are coincident.)

static calc_center(p1, p2, radius, angle)

Calculate the center point of an arc given two endpoints, the radius, and a central angle. This method is static so that it can be used by __new__.

Parameters:

• p1 – Start point
• p2 – End point
• radius – Radius of arc
• angle – The arc’s central angle

Returns:

The center point as a tuple (x, y).

See:

Thanks to Christian Blatter for this elegant solution: https://people.math.ethz.ch/~blatter/ http://math.stackexchange.com/questions/27535/how-to-find-center-of-an-arc-given-start-point-end-point-radius-and-arc-direc

p1

The start point of the arc.

p2

The end point of the arc.

radius

The radius of the arc.

angle

The central angle (AKA sweep angle) of this arc. The sign of the angle determines its direction.

center

The center point of this arc.

start_angle()

The angle from the arc center between the x axis and the first point.

length()

Returns:The length of this arc segment.

area()

Returns:The area inside the central angle between the arc and the center.

segment_area()

Returns:The area of the shape limited by the arc and a straight line forming a chord between the two end points.

is_clockwise()

Returns:True if arc direction is clockwise from first point to end point.

start_tangent_angle()

Returns:The start direction of this arc segment in radians. This is the angle of a tangent vector at the arc segment’s first point. Unlike a chord tangent angle this angle is from the x axis. Value is between -PI and PI.

end_tangent_angle()

Returns:The end direction of this arc segment in radians. This is the angle of a tangent vector at the arc segment’s end point. Value is between -PI and PI.

height()

Returns:The distance between the chord midpoint and the arc midpoint. Essentially the Hausdorff distance between the chord and the arc.

transform(matrix)

Parameters:

• matrix – An affine transform matrix. The arc will remain
• circular. –

Returns:

A copy of this arc with the transform matrix applied to it.

offset(distance, preserve_center=True)

Return a copy of this Arc that is offset by distance. If offset is < 0 the offset line will be towards the center otherwise to the other side of this arc. The central angle will be preserved.

Parameters:

• distance – The distance to offset the line by.
• preserve_center – If True the offset arc will have the same center point as this one. Default is True.

Returns:

An Arc offset by distance from this one.

distance_to_point(p, segment=True)

Parameters:

• p – The point to measure distance to
• segment – The point normal projection must lie on this the arc segment if True. Default is True.

Returns:

The minimum distance from this arc segment to the specified point, or -1 if segment is True and the point normal projection does not lie on this arc segment.

which_side_angle(angle, inline=False)

Determine which side of a line tangent to the end point of this arc lies a vector from the end point with the specified direction angle.

Parameters:

• angle – Angle in radians of the vector
• inline – If True return 0 if the point is inline.

Returns:

1 if the vector direction is to the left of arc tangent else -1. If inline is True and the point is inline then 0.

mu(p)

The unit distance from the first point of this arc segment to the specified point on the arc segment.

Parameters:p – A point on this arc segment. Returns:The unit distance mu where mu >=0 and <= 1.0. If p is does not lie on this arc segment mu may be < 0 or > 1.

point_at(mu)

Parameters:mu – Unit distance along central arc from first point. Returns:mu: along this arc from the start point. Return type:The point at unit distance

midpoint()

Returns:The point at the middle of the arc segment.

subdivide(mu)

Subdivide this arc at unit distance :mu: from the start point.

Parameters:mu – Unit distance along central arc from first point. Returns:A tuple containing one or two Arc objects. If mu is zero or 1 then a tuple containing just this arc is returned.

subdivide_at_angle(angle)

Split this arc into two arcs at the point on this arc given by the specified positive arc angle (0-2pi) from the start point.

Parameters:angle – A central angle the arc start point, in radians. Returns:A tuple containing one or two Arc objects. If the angle is zero or greater than this arc’s angle then a tuple containing just this arc will be returned.

subdivide_at_point(p)

Split this arc into two arcs at the specified point.

Parameters:p – A point on this arc. Returns:A tuple containing one or two Arc objects.

point_at_angle(angle, segment=False)

Get a point on this arc given an angle.

Parameters:

• angle – A central angle from start point.
• segment – The point must lie on the arc segment if True. Default is False.

Returns:

The point on this arc given the specified angle from the start point of the arc segment. If segment is True and the point would lie outside the segment then None. Otherwise, if angle is negative return the first point, or if angle is greater than the central angle then return the end point.

point_on_arc(p)

Determine if a point lies on this arc.

Parameters:p – Point to test. Returns:True if the point lies on this arc, otherwise False.

intersect_line(line, on_arc=False, on_line=False)

Find the intersection (if any) of this Arc and a Line.

See <http://mathworld.wolfram.com/Circle-LineIntersection.html>

Parameters:

• line – A line defined by two points (as a 2-tuple of 2-tuples).
• on_arc – If True the intersection(s) must lie on the arc between the two end points. Default is False.
• on_line – If True the intersection(s) must lie on the line segment between its two end points. Default is False.

Returns:

A list containing zero, one, or two intersections as point (x, y) tuples.

intersect_arc(arc, on_arc=False)

The intersection (if any) of this Arc and another Arc.

See:

<http://mathworld.wolfram.com/Circle-CircleIntersection.html>

Parameters:

• arc – An Arc.
• on_arc – If True the intersection(s) must lie on both arc segments, otherwise the arcs are treated as circles for purposes of computing the intersections. Default is False.

Returns:

A list containing zero, one, or two intersections.

reversed()

Returns:A copy of this Arc with direction reversed.

to_svg_path()

Returns:A string with the SVG path ‘d’ attribute value that corresponds to this arc.

geom.ellipse

Two dimensional ellipse and elliptical arc.

class geom.ellipse.Ellipse(center, rx, ry=None, phi=0.0)

Two dimensional ellipse.

For the parametric function the parameter t is the parametric angle (aka eccentric anomaly) from the semi-major axis of the ellipse before stretch and rotation (i.e. as if this ellipse were a circle.)

The ellipse will be normalized so that the semi-major axis is aligned with the X axis (i.e. rx >= ry.) The ellipse rotation (phi) will be adjusted 90deg to compensate if necessary.

See:

https://en.wikipedia.org/wiki/Ellipse http://www.spaceroots.org/documents/ellipse/ http://www.w3.org/TR/SVG11/implnote.html#ArcImplementationNotes https://en.wikipedia.org/wiki/Eccentric_anomaly

Parameters:

• center – The center of the ellipse.
• rx – Semi-major axis length.
• ry – Semi-minor axis length. Default is rx if None.
• phi – Rotation angle of the ellipse.

is_circle()

theta2t(theta)

Compute parametric angle from geometric angle.

Parameters:theta – The geometrical angle from the semi-major axis and a point on the ellipse. Returns:t - the parametric angle - 0 < t < 2*PI.

pointt(p)

Compute t given a point on the ellipse.

Parameters:p – A point on the ellipse. Returns:t - the parametric angle - 0 < t < 2*PI.

point_at(t)

Return the point on the ellipse at t.

This is the parametric function for this ellipse.

Parameters:t – Parametric angle - 0 < t < 2*PI. Returns:A point at t

point_inside(p)

Test if point is inside ellipse or not.

Parameters:p – Point (x, y) to test. Returns:True if the point is inside the ellipse, otherwise False.

all_points_inside(points)

Return True if all the given points are inside this circle.

focus()

The focus of this ellipse.

Returns:Distance from center to focus points.

focus_points()

Return the two focus points.

Returns:A tuple of two focus points along major axis.

area()

The area of this ellipse.

eccentricity()

The eccentricity e of this ellipse.

curvature(p)

The curvature at a given point.

derivative(t, d=1)

First and second derivatives of the parametric ellipse function.

Parameters:

• t – Parametric angle - 0 < t < 2*PI.
• d – 1 => First derivative, 2 => Second derivative. Default is 1.

Returns:

(dx, dy)

Return type:

A 2-tuple

class geom.ellipse.EllipticalArc(center, p1, p2, rx, ry, start_angle, sweep_angle, large_arc, sweep_flag, phi=0.0)

Two dimensional elliptical arc. A section of an ellipse.

See:

http://www.w3.org/TR/SVG11/implnote.html#ArcImplementationNotes

Create an elliptical arc. If only center parameters or endpoint parameters are known the static factory methods can be used instead.

Parameters:

• p1 – The start point of the arc.
• p2 – The end point of the arc.
• rx – Semi-major axis length.
• ry – Semi-minor axis length.
• start_angle – Parametric start angle of the arc.
• sweep_angle – Parametric sweep angle of the arc.
• large_arc – The large arc flag.
• sweep_flag – The sweep flag.
• phi – Rotation angle, in radians, of the ellipse. Default is 0.

static from_center(center, rx, ry, start_angle, sweep_angle, phi=0.0)

Create an elliptical arc from center parameters.

Parameters:

• center – The center point of the arc.
• rx – Semi-major axis length.
• ry – Semi-minor axis length.
• start_angle – Start angle of the arc.
• sweep_angle – Sweep angle of the arc.
• phi – The angle from the X axis to the semi-major axis of the ellipse.

Returns:

An EllipticalArc

static from_endpoints(p1, p2, rx, ry, large_arc, sweep_flag, phi=0.0)

Create an elliptical arc from SVG-style endpoint parameters. This will correct out of range parameters as per SVG spec. The center, start angle, and sweep angle will also be calculated.

See:

https://www.w3.org/TR/SVG11/implnote.html#ArcSyntax https://www.w3.org/TR/SVG11/implnote.html#ArcOutOfRangeParameters

Parameters:

• p1 – The start point of the arc.
• p2 – The end poin of the arc.
• rx – Semi-major axis length.
• ry – Semi-minor axis length.
• large_arc – The large arc flag.
• sweep_flag – The sweep flag.
• phi – The angle in radians from the X axis to the semi-major axis of the ellipse. Default is 0.

Returns:

An EllipticalArc or None if rx or ry is 0.

transform(matrix)

Transform this using the specified affine transform matrix.

geom.ellipse.ellipse_in_parallelogram(vertices, eccentricity=1.0)

Inscribe a parallelogram with an ellipse.

See: Horwitz 2008, http://arxiv.org/abs/0808.0297

Vertices:The four vertices of a parellelogram as a list of 2-tuples. Eccentricity:The eccentricity of the ellipse. Where 0.0 >= eccentricity <= 1.0. If eccentricity == 1.0 then a special eccentricity value will be calculated to produce an ellipse of maximal area. The minimum eccentricity of 0.0 will produce a circle. Returns:A tuple containing the semi-major and semi-minor axes respectively.

geom.ellipse.intersect_circle(c1_center, c1_radius, c2_center, c2_radius)

The intersection (if any) of two circles.

See:

<http://mathworld.wolfram.com/Circle-CircleIntersection.html>

Parameters:

• c1_center – Center of first circle.
• c1_radius – Radius of first circle.
• c2_center – Center of second circle.
• c2_radius – Radius of second circle.

Returns:

A tuple containing two intersection points if the circles intersect. A tuple containing a single point if the circles are only tangentially connected. An empty tuple if the circles do not intersect or if they are coincident (infinite intersections).

geom.bezier

Cubic bezier curve.

Includes biarc approximation.

class geom.bezier.CubicBezier

Two dimensional immutable cubic bezier curve.

For information about Bezier curves see: https://pomax.github.io/bezierinfo

Parameters:

• p1 – Start point as 2-tuple (x, y).
• c1 – First control point as 2-tuple (x, y).
• c2 – Second control point as 2-tuple (x, y).
• p2 – End point as 2-tuple (x, y).

static from_quadratic(qp1, qp2, qp3)

Create a CubicBezier from the control points of a quadratic Bazier curve.

Parameters:

• qp1 – Start point as 2-tuple (x, y).
• qp2 – Control point as 2-tuple (x, y).
• qp3 – End point as 2-tuple (x, y).

p1

The start point of curve.

c1

The first control point of curve.

c2

The second control point of curve.

p2

The end point of curve.

transform(matrix)

Return a copy of this curve with the transform matrix applied to it.

start_tangent_angle()

Return the tangent direction of this curve in radians at the start (first) point. This would normally be the same as the angle of the first control point vector, unless the control point is coincident with the first point. -PI < angle < PI.

end_tangent_angle()

Return the tangent direction of this curve in radians at the end (second) point. -PI < angle < PI.

point_at(t)

A point on the curve corresponding to <t>.

This is the parametric function Bezier(t).

Returns:A point as 2-tuple (x, y).

tangent(t)

The tangent unit vector at the point on the curve corresponding to t.

normal(t)

Normal unit vector at t.

flatness()

Return the flatness of this curve.

The maximum distance between the control points and the line segment defined by the start and end points of the curve. This is known as convex hull flatness and is robust regarding degenerate curves.

subdivide(t)

Subdivide this curve at the point corresponding to <t> into two cubic bezier curves, where 0<=t<=1. Uses De Casteljaus’s algorithm.

Returns:A tuple of one or two CubicBezier objects.

subdivide_inflections()

Subdivide this curve at the inflection points, if any.

Returns:A list containing one to three curves depending on whether there are no inflections, one inflection, or two inflections.

find_inflections(imaginary=False)

Find (t1, t2) where the curve changes direction, has a cusp, or a loop. There may be none, one, or two inflections on the curve. A loop will have two inflections.

These inflection points can be used to subdivide the curve.

See http://www.caffeineowl.com/graphics/2d/vectorial/cubic-inflexion.html

Parameters:imaginary – If True find imaginary inflection points. These are useful for subdividing curves with loops. Default is False. Returns:A tuple containing the parametric locations of the inflections, if any. The location values will be 0 if no inflection.

find_extrema_align(calc_bbox=True)

Find the extremities of the curve as if a chord connecting the end points is parallel to the X axis. This can be used to find the height of the curve if the curve has no inflections..

This also returns the bounding box since it needs to be rotated to match the curve alignment.

Parameters:calc_bbox – Calculate an aligned bounding box. This can be performed slightly more efficiently here since the alignment rotation is known. Returns:A tuple where the first item is a list of zero to four points and the second is the bounding box (as a list of four points) or None if no extrema can be found.

find_extrema_points()

Find the extremities of this curve.

See:

https://pomax.github.io/bezierinfo/#extremities

Returns:A list of zero to four points.

find_extrema()

Find the extremities of this curve.

See:

https://pomax.github.io/bezierinfo/#extremities

Returns:A list of zero to four parametric (t) values.

controlpoints_at(t)

Get the point on this curve corresponding to t plus control points.

Useful for subdividing the curve at t.

Parameters:t – location on curve. A value between 0.0 and 1.0 Returns:A tuple of the form (C0, C1, P, C2, C3) where C1 and C2 are the control points tangent to P and C0 and C3 would be the new control points of the endpoints where this curve to be subdivided at P.

derivative1(t)

Calculate the 1st derivative of this curve at t.

Returns:The first derivative at t as 2-tuple (dx, dy).

derivative2(t)

Calculate the 2nd derivative of this curve at t.

Returns:The second derivative at t as 2-tuple (dx, dy).

derivative3()

Calculate the 3rd derivative of this curve.

Returns:The third derivative as 2-tuple (dx, dy).

curvature_at(t)

Calculate the curvature at t.

See http://www.spaceroots.org/documents/ellipse/node6.html

Returns:A scalar value K representing the curvature at t. Negative if curving to the right or positive if curving to the left when t increases.

length(tolerance=None)

Calculate the approximate arc length of this curve within the specified tolerance. The resulting computed arc length will be cached so that subsequent calls are not expensive.

Uses a simple and clever numerical algorithm described/invented by Jens Gravesen.

See:

http://steve.hollasch.net/cgindex/curves/cbezarclen.html

Parameters:tolerance – The approximation tolerance. Default is const.EPSILON. Returns:The approximate arc length of this curve.

biarc_approximation(tolerance=0.001, max_depth=4, line_flatness=0.001, _recurs_depth=0)

Approximate this curve using biarcs.

This will recursively subdivide the curve into a series of G1 (tangential continuity) connected arcs or lines until the Hausdorff distance between the approximation and this bezier curve is within the specified tolerance.

Parameters:

• tolerance – Approximation tolerance. A lower value increases accuracy at the cost of time and number of generated biarc segments.
• max_depth – Maximum recursion depth. This limits how many times the Bezier curve can be subdivided.
• line_flatness – Segments flatter than this value will be converted to straight line segments instead of arcs with huge radii. Generally this should be a small value (say <= 0.01) to avoid path distortions.

Returns:

A list of Arc and/or Line objects. The list will be empty if the curve is degenerate (i.e. if the end points are coincident).

reversed()

Return a CubicBezier with control points (direction) reversed.

to_svg_path()

Return a string with the SVG path ‘d’ attribute value that corresponds with this curve.

geom.bezier.bezier_circle(center=(0, 0), radius=1.0)

Create an approximation of a circle with a cubic Bezier curve.

Parameters:

• center (tuple) – The center point of the circle. Default is (0,0).
• radius (float) – The radius of the circle. Default is 1.

Returns:

A tuple with four bezier curves for each circle quadrant. Circle will be counterclockwise from the positive x axis relative to the center point.

Return type:

tuple

See:

https://pomax.github.io/bezierinfo/#circles_cubic

geom.bezier.bezier_circular_arc(arc)

Create a cubic Bezier approximation of a circular arc. The central arc must be less than PI/2 radians (90deg).

Parameters:arc (geom.Arc) – A circular arc. Returns:A bezier curve. Return type:CubicBezier

geom.bezier.bezier_ellipse(ellipse)

Approximate this elliptical arc segment with Bezier curves.

If the sweep angle is greater than PI/2 the arc will be subdivided so that no segment has a sweep angle larger than PI/2.

Parameters:ellipse – An Ellipse or EllipticalArc Returns:A list containing one to four BezierCurves.

geom.bezier.bezier_elliptical_arc(ellipse, t1, t2)

Compute a BezierCurve that can approximate the elliptical arc between t1 and t2.

This does not subdivide the arc to reduce errors so if t2-t1 > PI/2 then the results may be less than ideal.

Parameters:

• ellipse – An Ellipse
• t1 – Parametric angle from semi-major axis to first location.
• t2 – Parametric angle from semi-major axis to second location.

Returns:

A cubic bezier curve (as CubicBezier).

See:

http://www.spaceroots.org/documents/ellipse/node22.html

geom.bezier.bezier_sine_wave(amplitude, wavelength, cycles=1, origin=(0.0, 0.0))

Create an approximation of a sine wave using a cubic Bezier curve.

Parameters:

• amplitude (float) – The amplitude (vertical scale) of the sine wave. This is one half the vertical distance from the trough to the peak.
• wavelength (float) – The horizontal length of one complete cycle.
• cycles (int) – The number of cycles. Default is one.
• origin (tuple) – Location of start point as a tuple (x,y). Default is (0, 0).

Returns:

A list of BezierCurve instances that describe the sine wave. Each curve will be one quarter of a sine wave, so one cycle will return a list four BezierCurves, two cycle will be eight, etc…

Return type:

list

geom.bezier.smoothing_curve(seg1, seg2, cp1=None, smoothness=0.5, match_arcs=True)

Create a smoothing Bezier curve between two segments that are not currently G1 continuous. The resulting Bezier curve will connect the two endpoints of the first segment.

Parameters:

• seg1 – First path segment containing first and second points. Can be a geom.Line or geom.Arc.
• seg2 – Second path segment containing second and third points. Can be a geom.Line or geom.Arc.
• cp1 (tuple) – First control point computed from previous invocation. If cp1 is None then the first endpoint of the first segment will be used as the initial control point. Default is None.
• smoothness (float) – Affects the magnitude of the smoothing curve control points. A value between 0 and 1. Default is 0.5
• match_arcs (bool) – Try to better match arc connections.

Returns:

A tuple containing CubicBezier and the control point for the next curve.

Return type:

tuple

See:

Maxim Shemanarev http://www.antigrain.com/agg_research/bezier_interpolation.html http://hansmuller-flex.blogspot.com/2011/04/approximating-circular-arc-with-cubic.html

geom.bezier.smooth_path(path, smoothness=0.5)

Create a smooth approximation of the path using Bezier curves.

Parameters:

• path (list) – A list of Line/Arc segments.
• smoothness (float) – Smoothness value (usually between 0 and 1). .5 is a reasonable default.

Returns:

A list of CubicBezier segments.

Return type:

list

geom.box

Basic 2D bounding box geometry.

class geom.box.Box

Two dimensional immutable rectangle defined by two points, the lower left corner and the upper right corner respectively.

The sides are always assumed to be aligned with the X and Y axes.

Useful as clipping rectangle or bounding box.

static from_points(points)

Create a Box from the bounding box of the given points.

Returns:A geom.Box or None if there are zero points.

p1

The lower left corner of the box rectangle.

p2

The upper right corner of the box rectangle.

topleft

The upper left corner of the box recangle.

bottomright

The bottom right corner of the box recangle.

xmin

Minimum X value of bounding box.

xmax

Maximum X value of bounding box.

ymin

Minimum Y value of bounding box.

ymax

Maximum X value of bounding box.

vertices()

Get the four vertices of the box as a tuple of four points.

center()

Return the center point of this rectangle.

height()

Height of rectangle. (along Y axis)

width()

Width of rectangle. (along X axis)

diagonal()

Length of diagonal

point_inside(p)

Return True if the point is inside this rectangle.

line_inside(line)

Return True if the line segment is inside this rectangle.

all_points_inside(points)

Return True if the given set of points lie inside this rectangle.

buffered(distance)

Return a copy of this box with it’s boundaries expanded or shrunk by the specified distance. Also known as buffering.

Parameters:distance – The distance to offset. The box will shrink if the distance is negative.

transform(matrix)

Return a copy of this box with the transform matrix applied to it.

Note: rotations just scale since a Box is always aligned to

the X and Y axes.

clip_line(line)

If the given line segment is clipped by this rectangle then return a new line segment with clipped end-points.

If the line segment is entirely within the rectangle this returns the same (unclipped) line segment.

If the line segment is entirely outside the rectangle this returns None.

Uses the Liang-Barsky line clipping algorithm. Translated C++ code from: http://hinjang.com/articles/04.html

Parameters:line – The line segment to clip. Returns:A new clipped line segment or None if the segment is outside this clipping rectangle.

clip_arc(arc)

If the given circular arc is clipped by this rectangle then return a new arc with clipped end-points.

This only returns a single clipped arc even if the arc could be clipped into two sub-arcs… For now this is considered a pathological condition.

Parameters:arc – The arc segment to clip. Returns:A new clipped arc or None if the arc segment is entirely outside this clipping rectangle. If the arc segment is entirely within the rectangle this returns the same (unclipped) arc segment.

start_tangent_angle()

Return the angle in radians of a line tangent to this shape beginning at the first point. It’s pretty obvious this will always be PI/2…

This is just to provide an orthogonal interface for geometric shapes…

The corner point order for rectangles is clockwise from lower left.

bounding_box()

Bounding box - self.

intersection(other)

Return a Box that is the intersection of this rectangle and another.

Returns None if the rectangles do not intersect.

union(other)

Return a Box that is the union of this rectangle and another.

geom.polygon

Some handy polygon tools such as convex hull, area, and centroid calculations.

---

Some references: http://paulbourke.net/geometry/ http://geomalgorithms.com/index.html

geom.polygon.turn(p, q, r)

Returns -1, 0, 1 if p,q,r forms a right, straight, or left turn.

Parameters:

• p – Point from which initial direction is determined. A 2-tuple (x, y) point.
• q – Point from which turn is determined. A 2-tuple (x, y) point.
• r – End point which determines turn direction. A 2-tuple (x, y) point.

geom.polygon.convex_hull(points)

Returns points on convex hull of an array of points in CCW order.

Uses the Graham Scan algorithm.

Parameters:points – a list of 2-tuple (x, y) points. Returns:The convex hull as a list of 2-tuple (x, y) points.

geom.polygon.convex_hull_chan(points)

Returns the points on the convex hull of points in CCW order.

Uses Chan’s algorithm. May be faster than Graham scan on large point collections.

See http://tomswitzer.net/2010/12/2d-convex-hulls-chans-algorithm/

Parameters:points – a list of 2-tuple (x, y) points. Returns:The convex hull as a list of 2-tuple (x, y) points.

geom.polygon.bounding_box(points)

Simple bounding box of a collection of points.

Parameters:points – an iterable collection of point 2-tuples (x,y).

geom.polygon.area(vertices)

Return the area of a simple polygon.

Parameters:vertices – the polygon vertices. A list of 2-tuple (x, y) points.

Returns (float):

The area of the polygon. The area will be negative if the vertices are ordered clockwise.

geom.polygon.area_triangle(a, b=None, c=None)

Area of a triangle.

This is just a slightly more efficient specialization of the more general polygon area.

Parameters:

• a – The first vertex of a triangle or an iterable of three vertices.
• b – The second vertex or None if a is iterable.
• c – The third vertex or None if a is iterable.

Returns (float):

The area of the triangle.

geom.polygon.centroid(vertices)

Return the centroid of a simple polygon.

See http://paulbourke.net/geometry/polygonmesh/

Parameters:vertices – The polygon vertices. A list of 2-tuple (x, y) points. Returns:The centroid point as a 2-tuple (x, y)

geom.polygon.point_inside(vertices, p)

Return True if point p is inside the polygon defined by vertices.

See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html Also: http://paulbourke.net/geometry/polygonmesh/ Also: http://geomalgorithms.com/a03-_inclusion.html

Parameters:

• vertices – polygon vertices. A list of 2-tuple (x, y) points.
• p – Point to test.

Returns:

True if the point lies inside the polygon, else False.

geom.polygon.intersect_line(vertices, line)

Compute the intersection(s) of a polygon and a line segment.

Parameters:

• vertices – the polygon vertices. An iterable of 2-tuple (x, y) points.
• line – a line possibly intersecting the polygon. A 2-tuple of line end points, each a 2-tuple ((x1, y1), (x2, y2)).

Returns:

a list of one or more line segments that intersect the polygon or that lie completely within the polygon. Returns an empty list if there are no intersections.

geom.polygon.is_closed(vertices)

Return True if the polygon is closed. I.e. if the first vertice matches the last vertice.

geom.polygon.offset_polygons(poly, offset, jointype=0, limit=0.0)

Offset a polygon by offset amount. This is also called polygon buffering.

See:

http://www.angusj.com/delphi/clipper.php

Parameters:

• poly – A polygon as a list of 2-tuple vertices.
• offset – The amount to offset (can be negative).
• jointype – The type of joins for offset vertices.
• limit – The max distance to a offset vertice before it will be squared off.

Returns:

Zero or more offset polygons as a list of 2-tuple vertices. If the specified offset cannot be performed for the input polygon an empty list will be retured.

geom.polygon.poly2clipper(poly)

Convert a polygon (as a list of float 2-tuple vertices) to a Clipper polygon (a list of integer 2-tuples).

geom.polygon.clipper2poly(clipper_poly)

Convert a Clipper polygon (a list of integer 2-tuples) to a polygon (as a list of float 2-tuple vertices).

geom.polygon.simplify_polyline_rdp(points, tolerance)

Simplify a polyline (a list of line segments given as a list of points).

Uses Ramer-Douglas-Peucker algorithm.

See:

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Parameters:

• points (list) – A list of segment endpoints
• tolerance (float) – Line flatness tolerance

Returns:

A list of points defining the vertices of the simplified polyline.

geom.polygon.simplify_polyline_vw(points, tolerance)

Simplify a polyline (a list of line segments given as a list of points).

Uses Visvalingam-Whyatt algorithm.

See:

Visvalingam, M., and Whyatt, J.D. (1992) “Line Generalisation by Repeated Elimination of Points”, Cartographic J., 30 (1), 46 - 51

Parameters:

• points (list) – A list of segment endpoints
• tolerance (float) – Line flatness tolerance

Returns:

A list of points defining the vertices of the simplified polyline.

geom.planargraph

Simple planar graph data structure.

class geom.planargraph.GraphNode(vertex, edge_nodes=None)

Graph node.

A node has a vertex and a list of outgoing nodes that define the outgoing edges that connect to other nodes in the graph.

Graph node.

Parameters:vertex – The vertex associated with this node.

degree()

Number of incident graph edges. I.e. number of edges that share this node’s vertex.

See:

http://mathworld.wolfram.com/VertexOrder.html

add_edge_node(edge_node)

Add an outgoing edge node.

sort_edges()

Sort outgoing edges in CCW order.

ccw_edge_node(ref_node, skip_spikes=True)

The most CCW edge node from the reference edge defined by ref_node->this_node.

Parameters:

• ref_node – The edge node reference.
• skip_spikes – Skip over edges that connect to nodes of order one.

Returns:

The counter-clockwise edge node closest to the reference node by angular distance. If all edges nodes are dead ends the reference node will be returned.

class geom.planargraph.Graph(edges=None)

Simple connected undirected 2D planar graph.

Parameters:edges – An iterable collection of line segments that define the graph edges. Each edge connects two nodes. An edge being a 2-tuple of endpoints of the form: ((x1, y1), (x2, y2)).

edges = None

Set of graph edges

nodemap = None

Map of vertex points to graph nodes.

add_edge(edge)

Parameters:edge – A line segment that defines a graph edge. An edge being a 2-tuple of endpoints of the form: ((x1, y1), (x2, y2)).

remove_edge(edge)

Remove and unlink the specified edge from the graph.

Parameters:edge – A line segment that defines a graph edge connecting two nodes. An edge being a 2-tuple of endpoints of the form: ((x1, y1), (x2, y2)).

add_poly(vertices, close_poly=True)

Add edges from the line segments defined by the vertices of a polyline/polygon.

Parameters:

• vertices – A list of polyline/polygon vertices as 2-tuples (x, y).
• close_poly – If True a closing segment will be automatically added if absent. Default is True.

order()

Number of graph nodes (vertices.)

size()

Number of edges.

vertices()

A collection view of node vertex points.

boundary_polygon()

A polygon defining the outer edges of this segment graph.

peel_boundary_polygon(boundary_polygon)

Similar to convex hull peeling but with non-convex boundary polygons.

Parameters:boundary_polygon – The initial graph polygon hull to peel. Returns:A list of peeled inner polygons. Possibly empty.

cull_open_edges()

Remove edges that have one or two disconnected endpoints.

get_face_polygons()

Graph face polygons.

Returns:A list of face polygons.

class geom.planargraph.GraphPathBuilder(graph)

Given a Graph, build a set of paths made of connected graph edges.

build_paths(start_edge=None, path_strategy=0)

Given the starting edge, find the set of edge paths that completely fill the graph…

Parameters:

• start_edge – The graph edge that starts the path.
• path_strategy –

  How paths will be constructed. Possible path strategies are:

  PATH_STRAIGHTEST, PATH_SQUIGGLY, PATH_RANDOM, and PATH_RANDOM2

Returns:

A list of paths sorted by descending order of path length.

build_longest_paths(path_strategy=0)

Find the longest paths in this graph.

PATH_RANDOM = 2

PATH_RANDOM2 = 3

PATH_SQUIGGLY = 1

PATH_STRAIGHTEST = 0

class geom.planargraph.MarkedEdge(edge)

A graph edge that is used to keep track of graph traversal direction.

Parameters:edge – A graph edge (a Line segment).

visited_p1 = None

True if traversed in direction p2->p1, CCW winding

visited_p2 = None

True if traversed in direction p1->p2, CCW winding

visited_left(dest_vertex)

True if this edge has been visited with a CCW winding. The edge will be marked as visited.

Parameters:dest_vertex – The destination vertex. Determines which side of the edge has been visited (i.e. direction). Returns:True if this edge has been visited during a counter-clockwise traversal. I.e. the left side given the direction. Otherwise False.

class geom.planargraph.MarkedEdgeMap(edges)

lookup(p1, p2)

mark_edge(p1, p2)

geom.planargraph.make_face_polygons(edges, nodemap)

Given a graph, make polygons from graph faces delineated by edges.

Parameters:nodemap – A mapping of edges to nodes.

geom.planargraph.make_face(edgemap, start_node, next_node)

geom.planargraph.find_free_edge_node(edgemap, start_node)

geom.voronoi

Voronoi diagram / Delaunay triangulation.

Compute a Voronoi diagram and optional Delaunay triangulation for a set of 2D input points.

Based on Steve Fortune’s original code:

http://ect.bell-labs.com/who/sjf/

Derek Bradley’s fixes for memory leaks:

http://zurich.disneyresearch.com/derekbradley/voronoi.html

Shane O’Sullivan’s updates:

http://mapviewer.skynet.ie/voronoi.html

Translated to Python by Bill Simons September, 2005:

(not sure where this original translation can be found anymore)

Nicely refactored version by Manfred Moitzi at:

https://bitbucket.org/mozman/geoalg

This version was based on the Bill Simons version and refactored with some of Moitzi’s cleanups.

Derived from code bearing the following notice:

The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T
Bell Laboratories.

Permission to use, copy, modify, and distribute this software for any
purpose without fee is hereby granted, provided that this entire notice
is included in all copies of any software which is or includes a copy
or modification of this software and in all copies of the supporting
documentation for such software.
THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.

Comments were incorporated from Shane O’Sullivan’s translation of the original code into C++:

http://mapviewer.skynet.ie/voronoi.html

This module has no dependencies besides standard Python libraries.

---

geom.voronoi.EPSILON = 1e-09

Tolerance for floating point comparisons

class geom.voronoi.VoronoiEdge

A Voronoi edge. The dual of a corresponding This is a line segment that bisects a line between nearest neighbor sites.

If one end point of the edge is None it means the line extends to infinity. If the first end point is None the edge extends to the left. If the second end point is None the edge extends to the right.

p1

First point of edge segment.

p2

Second point of edge segment.

equation

The line equation for this segment in the form a*x + b*y = c as a 3-tuple (a, b, c)

delaunay_edge

The dual of this Voronoi edge.

class geom.voronoi.DelaunayEdge

A Delaunay edge. The dual of a corresponding Voronoi segment that bisects this Delaunay segment. This is a line segment between nearest neighbor sites.

p1

First point of edge segment.

p2

Second point of edge segment.

class geom.voronoi.DelaunayTriangle

A Delaunay triangle. This a 3-tuple of 2-tuple (x, y) points.

p1

First point of triangle.

p2

Second point of triangle.

p3

Third point of triangle.

class geom.voronoi.VoronoiDiagram(input_points, do_delaunay=False, jiggle_points=False)

Voronoi diagram and Delaunay triangulation.

Parameters:

• input_points – An indexable collection of points as (x, y) 2-tuples
• do_delaunay – True if Delaunay edges and triangles are to be generated. Default is False.
• jiggle_points – Jiggle the input points by a small random distance to mitigate problems caused by degenerate point sets (such as collinear or coincident points). Default is False.

vertices

List of the Voronoi diagram vertices as 2-tuple (x, y) coordinates.

edges

List of VoronoiEdges.

triangles

List of DelaunayTriangles.

delaunay_edges

List of DelaunayEdges.

geom.voronoi.jiggle(point)

Move a point in a random direction by a small random distance.

Useful for when input is degenerate (i.e. when points are collinear.)

Parameters:point – The point as a 2-tuple of the form (x, y) Returns:A new jiggled point as a 2-tuple

geom.voronoiclip

geom.voronoiclip.clip_voronoi_segments(self, diagram, clip_rect)

Clip a voronoi diagram to a clipping rectangle.

Parameters:

• diagram – A VoronoiDiagram.
• A Box. Clipping rectangle. (clip_rect.) –

Returns:

A list of (possibly) clipped voronoi segments.

geom.voronoiclip.clip_voronoi_segments_poly(self, voronoi_segments, clip_polygon)

Clip voronoi segments to a polygon.

Parameters:voronoi_segments –

geom.voronoiclip.clipped_delaunay_segments(self, voronoi_diagram, clip_polygon)

geom.voronoiclip.line_inside_hull(self, points, line, allow_hull=False)

Test if line is inside or on the polygon defined by points.

This is a special case…. basically the line segment will lie on the hull, have one endpoint on the hull, or lie completely within the hull, or be completely outside the hull. It will not intersect. This works for the Delaunay triangles and polygon segments…

Parameters:

• points – polygon vertices. A list of 2-tuple (x, y) points.
• line – line segment to test.
• allow_hull – allow line segment to lie on hull

Returns:

True if line is inside or on the polygon defined by points. Otherwise False.

geom.quasi

Python port of quasi.c which was originally written by Eric Weeks weeks@physics.emory.edu

See: http://www.physics.emory.edu/~weeks/software/quasic.html

This algorithm implements the “Generalized Dual Method” or GDM. See [Socolar, Steinhardt, Levine] 1985.

Mostly unchanged except to make it a little more pythonic and:

• Removed Postscript output and main()
• Fixed divide by zero exception for even symmetries
• Added segment connection to vertices options
• Removed coloring - should be done in plotter

---

class geom.quasi.QuasiPlotter

Quasi plotter base class. Subclass this to produce output.

Does nothing by default.

plot_polygon(vertices, color)

Draw a polygon.

Parameters:

• vertices – A list of tuples containing the (x,y) coordinates of the polygon vertices.
• color – Fill color. A value between 0.0 and 1.0 or None if no fill.

Returns:

True if the polygon is not clipped, otherwise False.

plot_segment(p1, p2)

Draw a line segment.

Parameters:

• p1 – Segment start point as tuple containing (x,y) coordinates.
• p2 – Segment end point as tuple containing (x,y) coordinates.

plot_segpoly(vertices, color)

Draw a line segment box.

Parameters:

• vertices – A list of tuples containing the (x,y) coordinates of the polygon vertices.
• color – Fill color. A value between 0.0 and 1.0 or None if no fill.

class geom.quasi.Quasi(symmetry=5, segtype_skinny=0, segtype_fat=0, plotter=None, tolerance=1e-08)

Parameters:

• symmetry – Degrees of symmetry. Must be at least two.
• segtype_skinny – Segment connection type for skinny rhombuses. Default is SEG_NONE.
• segtype_fat – Segment connection type for fat rhombuses. Default is SEG_NONE.
• plotter – Plotter to draw output. Default is None.
• tolerance – Tolerance for floating point comparisons. Default is 1e-08.

SEG_NONE = 0

No segment connection.

SEG_MIDP_ACUTE = 1

Connect midpoints of polygon edges that meet at an acute angle.

SEG_MIDP_OBTUSE = 2

Connect midpoints of polygon edges that meet at an obtuse angle.

SEG_MIDP_CROSS = 3

Connect midpoints of polygon edges to form a cross.

SEG_MIDP_RECT = 4

Connect midpoints of polygon edges to form a rectangle.

SEG_VERT_ACUTE = 5

Connect polygon vertices whose edges form an acute angle.

SEG_VERT_OBTUSE = 6

Connect polygon vertices whose edges form an obtuse angle.

SEG_VERT_CROSS = 7

Connect polygon vertices to form a cross.

tolerance = None

Tolerance for floating point comparisons

plotter = None

Plotter to draw output.

symmetry = None

Degrees of quasi symmetry.

segment_split_cross = None

Split crossed segments

offset_salt_x = None

Random-ish offset to avoid more than two lines intersecting.

offset_salt_y = None

Random-ish offset to avoid more than two lines intersecting.

segment_ratio = None

Ratio that determines edge midpoint.

skinnyfat_ratio = None

Ratio that determines whether a rhombus is fat or skinny

numlines = None

Number of lines. A larger number enables more tiles to be generated.

color_fill = None

Color fill polygons. Default is False.

color_by_polytype = None

Fill color by rhombus type.

quasi()

Draw tiling.

geom.fillet

Connect Line/Arc segments with a fillet arc.

geom.fillet.fillet_path(path, radius, fillet_close=True)

Attempt to insert a circular arc of the specified radius to connect adjacent path segments.

Parameters:

• path – A list of Line or Arc segments.
• radius – The radius of the fillet arc.
• fillet_close – If True and the path is closed then add a terminating fillet. Default is False.

Returns:

A new path with fillet arcs. If no fillets are created then the original path will be returned.

geom.fillet.fillet_polygon(poly, radius, fillet_close=True)

Attempt to insert a circular arc of the specified radius connecting adjacent polygon segments.

Parameters:

• poly – A list of polygon vertices.
• radius – The radius of the fillet arc.
• fillet_close – If True and the path is closed then add a terminating fillet. Default is True.

Returns:

A new path with fillet arcs as a list of Line and Arc segments. If no fillets are created then the original path will be returned.

geom.fillet.insert_fillet(seg1, seg2, radius)

Try to create a fillet between two segments. Any GCode rendering hints attached to the segments will be preserved.

Parameters:

• seg1 – First segment, an Arc or a Line.
• seg2 – Second segment, an Arc or a Line.
• radius – Fillet radius.

Returns:

(seg1, fillet_arc, seg2) Returns an empty tuple if the segments cannot be connected with a fillet arc (either they are too small or somehow degenerate.)

Return type:

A tuple containing the adjusted segments and fillet arc

geom.fillet.connect_fillet(seg1, farc, seg2)

Connect two segments with a fillet arc. This will adjust the lengths of the segments to accommodate the fillet.

geom.fillet.create_fillet_arc(seg1, seg2, radius)

Try to create a fillet between two segments.

Parameters:

• seg1 – First segment, an Arc or a Line.
• seg2 – Second segment, an Arc or a Line.
• radius – Fillet radius.

Returns:

A fillet arc or None if the segments cannot be connected with a fillet arc (either they are too small, already G1 continuous, or are somehow degenerate.)

geom.fillet.fillet_line_line(line1, line2, fillet_radius)

Create a fillet arc between two line segments.

Parameters:

• line1 – A Line.
• line2 – A Line connected to line1.
• fillet_radius – The radius of the fillet.

Returns:

An Arc, or None if the fillet radius is too big to fit or if the two segments are not connected.

geom.fillet.fillet_arc_arc(arc1, arc2, fillet_radius)

Create a fillet arc between two connected arcs.

Parameters:

• arc1 – First arc.
• arc2 – Second arc.
• fillet_radius – The radius of the fillet.

Returns:

An Arc, or None if the fillet radius is too big to fit or if the two segments are not connected.

geom.fillet.fillet_line_arc(line, arc, fillet_radius)

Create a fillet arc between a line segment and a connected arc. The fillet arc end point order will match the line-arc order.

Parameters:

• line – A Line.
• arc – An Arc.
• fillet_radius – The radius of the fillet.

Returns:

An Arc, or None if the fillet radius is too big to fit or if the two segments are not connected.

geom.util

Basic 2D utility functions.

geom.util.normalize_angle(angle, center=3.141592653589793)

Normalize angle (in radians) about a 2*PI interval centered at center.

For angle between 0 and 2*PI (default):

normalize_angle(angle, center=math.pi)

For angle between -PI and PI:

normalize_angle(angle, center=0.0)

Parameters:

• angle – Angle to normalize
• angle – float
• center – Center value about which to normalize. Default is math.pi.
• center – float

geom.util.calc_rotation(start_angle, end_angle)

Calculate the amount of rotation required to get from start_angle to end_angle.

Parameters:

• start_angle – Start angle in radians.
• end_angle – End angle in radians.

Returns:

Rotation amount in radians where -PI <= rotation <= PI.

geom.util.segments_are_g1(seg1, seg2, tolerance=None)

Determine if two segments have G1 continuity (are tangentially connected.) G1 implies G0 continuity.

Parameters:

• seg1 – First segment. Can be geom.Line, geom.Arc, geom.CubicBezier.
• seg2 – Second segment. Can be geom.Line, geom.Arc, geom.CubicBezier.
• tolerance – G0/G1 tolerance. Default is geom.const.EPSILON.

Returns:

True if the two segments have G1 continuity within the specified tolerance. Otherwise False.

geom.util.reverse_path(path)

Reverse in place the order and direction of path segments.

geom.debug

Debug output support for geometry package.

geom.debug.svg_context()

The SVG context used for debug output.

geom.debug.set_svg_context(svg_context)

Initialize this module with an SVGContext that can be used for debug output by draw…() methods.

geom.debug.draw_point(point, radius=3, color=u'#000000', parent=None)

Draw a dot. Useful for debugging and testing.

geom.debug.draw_line(line, color=u'#c00000', width=u'1px', opacity=1, verbose=False, parent=None)

Draw an SVG line segment for debugging/testing

geom.debug.draw_poly(vertices, color=u'#c00000', width=u'1px', verbose=False, parent=None, close_poly=True)

Draw an SVG polygon.

geom.debug.draw_arc(arc, color=u'#cccc99', width=u'1px', verbose=False, parent=None)

Draw an SVG arc for debugging/testing

geom.debug.draw_circle(center, radius, color=u'#cccc99', width=u'1px', verbose=False, parent=None)

Draw an SVG circle.

geom.debug.draw_ellipse(ellipse, color=u'#cccc99', width=u'1px', verbose=False, parent=None)

Draw an SVG arc for debugging/testing

geom.debug.draw_bezier(curve, color=u'#cccc99', verbose=False, parent=None)

Draw an SVG version of this curve for debugging/testing. Include control points, inflection points, and tangent lines.