vegesvgplot.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
#-------------------------------------------------------------------------------
# vegesvgplot.py
# http://pastebin.com/6Aek3Exm
#-------------------------------------------------------------------------------


u'''VegeSVGPlot, a Python SVG plotting and maths module for vegetables

Description:
  The VegeSVGPlot module is a collection of simple mathematics, geometry
  and SVG output functions. The module makes it easy to write simple Python
  scripts to produce 2D graphical output such as function plots.

Author:
  Daniel Neville (Blancmange), creamygoat@gmail.com

Copyright:
  None

Licence:
  Public domain


INDEX


Imports

Shape constants:

  Pt_Break
  Pt_Anchor
  Pt_Control

  PtCmdWithCoordsSet
  PtCmdSet

Legendre–Gauss quadrature tables:

  LGQWeights25
  LGQAbscissae25

Exceptions:

  Error

tIndentTracker:

  __init__([IndentUnitStr], [StartingLevel], [LineTerminator])
  __call__(*StringArgs)
  Clone()
  StepIn([LevelIncrement])
  StepOut([LevelDecrement])
  LineTerminator
  IndentUnitStr
  Level
  LIStr

tAffineMtx:

  __init__(Origin, BasisVectors)
  __repr__()
  MultV(Vector)
  MultVectors(Vectors)
  MultAM(AM)
  B
  T

Affine matrix creation functions:

  AffineMtxTS(Translation, Scale)
  AffineMtxTRS2D(Translation, Angle, Scale)
  Affine2DMatrices(Origin, X)

Utility functions:

  ValidatedRange(ARange, Length)
  MergedDictionary(Original, Patch)
  Save(Data, FileName)

Array access functions:

  ArrayDimensions(MDArray)
  NewArray(Dimensions, Value)
  CopyArray(Source, [CopyDepth])
  At(MDArray, Indices)
  SetAt(MDArray, Indices, Value)
  EnumerateArray(MDArray, [Depth])

Basic vector functions:

  VZeros(n)
  VOnes(n)
  VStdBasis(Dimensions, Index, [Scale])
  VDim(A, n)
  VAug(A, x)
  VMajorAxis(A)
  VNeg(A)
  VSum(A, B...)
  VDiff(A, B)
  VSchur(A, B...)
  VDot(A, B)
  VLengthSquared(A)
  VLength(A)
  VManhattan(A)
  VScaled(A, scale)
  VNormalised(A)
  VPerp(A)
  VRevPerp(A)
  VCrossProduct(A, B)
  VCrossProduct4D(A, B, C)
  VScalarTripleProduct(A, B, C)
  VVectorTripleProduct(A, B, C)
  VProjectionOnto(Axis, Vector)
  VDiagonalMAV(Diagonals)
  VTransposedMAV(BasisVectors)
  VRectToPol(A)
  VPolToRect(DistanceAngle)
  VLerp(A, B, Progress)

Mathematical functions:

  BinomialCoefficient(n, k)
  BinomialRow(n)
  NextBinomialRow(Row)
  ApproxSaggita(ArcLength, ChordLength)
  LGQIntegral25(Interval, Fn, InitalParams, FinalParams)
  IntegralFunctionOfPLF(Vertices, C=0.0)
  EvaluatePQF(PQF, x)
  EvaluateInvPQF(PQF, y)

Linear intersection functions:

  LineParameter(Point, Line)
  XInterceptOfLine(Line)
  UnitXToLineIntersection(Line2)
  LineToLineIntersectionPoint(Line1, Line2)
  LineToLineIntersection(Line1, Line2)

Bézier functions:

  CubicBezierArcHandleLength(AngleSweep)
  BezierPoint(Curve, t)
  BezierPAT(Curve, t)
  SplitBezier(Curve, t)
  BezierDerivative(Curve)
  ManhattanBezierDeviance(Curve)
  BezierLength(Curve, [Interval])

Bézier intersection functions:

  UnitXToBezierIntersections(Curve, [Tolerance])
  LineToBezierIntersections(Line, Curve, [Tolerance])

Shape functions:

  ShapeDim(Shape, n)
  ShapeFromVertices(Vertices, Order)
  ShapePoints(Shape, [Range])
  ShapeSubpathRanges(Shape)
  ShapeCurveRanges(Shape, [Range])
  ShapeLength(Shape)
  LineToShapeIntersections(Line, Shape, [Tolerance])
  TransformedShape(AM, Shape)
  PiecewiseArc(Centre, Radius, AngleRange, NumPieces)

Output formatting functions:

  MaxDP(x, n)
  GFListStr(L)
  GFTupleStr(T)
  HTMLEscaped(Text)
  AttrMarkup(Attributes, PrependSpace)
  ProgressColourStr(Progress, [Opacity])

SVG functions:

  SVGStart(IT, Title, [SVGAttributes])
  SVGEnd(IT)
  SVGPathDataSegments(ShapePoints)
  SVGPath(IT, ShapePoints, [Attributes])
  SVGText(IT, Position, Text, [Attributes])
  SVGGroup(IT, [Attributes])
  SVGGroupEnd(IT)
  SVGGrid(IT, Grid)

'''


#-------------------------------------------------------------------------------
# Imports
#-------------------------------------------------------------------------------


import math

from math import (
  pi, sqrt, hypot, sin, cos, tan, asin, acos, atan, atan2, radians, degrees,
  floor, ceil
)


#-------------------------------------------------------------------------------
# Shape constants
#
# A “Shape” is a list of (PointType, Point) pairs intended to represent paths
# in the matter of Postscript or SVG but in a way which allows a path segment
# to be very easily reversed.
#
#-------------------------------------------------------------------------------


Pt_Break = 0
Pt_Anchor = 1
Pt_Control = 2

PtCmdWithCoordsSet = set([Pt_Anchor, Pt_Control])
PtCmdSet = set([Pt_Break, Pt_Anchor, Pt_Control])


#-------------------------------------------------------------------------------
# Legendre–Gauss quadrature tables
#
# The following tables were adapted from Mike "Pomax" Kamermans’s tables,
# which were computed to 295 decimal places and given for orders up to 64.
#
#-------------------------------------------------------------------------------


# Legendre–Gauss quadrature weights for
# the 25th order Legendre polynomial

LGQWeights25 = [
  0.1222424429903100416889595189458515058351, # −12
  0.1222424429903100416889595189458515058351, # +12
  0.1194557635357847722281781265129010473902, # −11
  0.1194557635357847722281781265129010473902, # +11
  0.1148582591457116483393255458695558086409, # −10
  0.1148582591457116483393255458695558086409, # +10
  0.1085196244742636531160939570501166193401, #  −9
  0.1085196244742636531160939570501166193401, #  +9
  0.1005359490670506442022068903926858269885, #  −8
  0.1005359490670506442022068903926858269885, #  +8
  0.0910282619829636498114972207028916533810, #  −7
  0.0910282619829636498114972207028916533810, #  +7
  0.0801407003350010180132349596691113022902, #  −6
  0.0801407003350010180132349596691113022902, #  +6
  0.0680383338123569172071871856567079685547, #  −5
  0.0680383338123569172071871856567079685547, #  +5
  0.0549046959758351919259368915404733241601, #  −4
  0.0549046959758351919259368915404733241601, #  +4
  0.0409391567013063126556234877116459536608, #  −3
  0.0409391567013063126556234877116459536608, #  +3
  0.0263549866150321372619018152952991449360, #  −2
  0.0263549866150321372619018152952991449360, #  +2
  0.0113937985010262879479029641132347736033, #  −1
  0.0113937985010262879479029641132347736033, #  +1
  0.1231760537267154512039028730790501424382  #   0
]

# Legendre–Gauss quadrature abscissae (x-values)
# for the 25th order Legendre polynomial

LGQAbscissae25 = [
 -0.1228646926107103963873598188080368055322, # −12
  0.1228646926107103963873598188080368055322, # +12
 -0.2438668837209884320451903627974515864056, # −11
  0.2438668837209884320451903627974515864056, # +11
 -0.3611723058093878377358217301276406674221, # −10
  0.3611723058093878377358217301276406674221, # +10
 -0.4730027314457149605221821150091920413318, #  −9
  0.4730027314457149605221821150091920413318, #  +9
 -0.5776629302412229677236898416126540673957, #  −8
  0.5776629302412229677236898416126540673957, #  +8
 -0.6735663684734683644851206332476221758834, #  −7
  0.6735663684734683644851206332476221758834, #  +7
 -0.7592592630373576305772828652043609763875, #  −6
  0.7592592630373576305772828652043609763875, #  +6
 -0.8334426287608340014210211086935695694610, #  −5
  0.8334426287608340014210211086935695694610, #  +5
 -0.8949919978782753688510420067828049541746, #  −4
  0.8949919978782753688510420067828049541746, #  +4
 -0.9429745712289743394140111696584705319052, #  −3
  0.9429745712289743394140111696584705319052, #  +3
 -0.9766639214595175114983153864795940677454, #  −2
  0.9766639214595175114983153864795940677454, #  +2
 -0.9955569697904980979087849468939016172576, #  −1
  0.9955569697904980979087849468939016172576, #  +1
  0                                           #   0
]


#-------------------------------------------------------------------------------
# Exceptions
#-------------------------------------------------------------------------------


class Error (Exception):
  pass;


#-------------------------------------------------------------------------------
# tIndentTracker
#-------------------------------------------------------------------------------


class tIndentTracker (object):

  u'''Keeper of current indentation levels for text output

  Functions which output strings of nicely indented markup can be made
  especially easy to use when an object like this keeps track of the
  current indenting level and the caller’s preference for the character
  or string used for indenting.

  The default method returns indented and line-terminated text given one
  or more string arguments, one argument per line of text. (Use the “*”
  list or tuple unpacking operator to work with lists or tuples.)

  For convenience when writing custom markup, the LIStr field may
  be used to begin each line of output.

  Functions which produce markup which imply a change in indentation
  level should update both the Level and LIStr fields.

  Methods:

    __init__([IndentUnitStr], [StartingLevel], [LineTerminator])
    __call__(*StringArgs)
    Clone()
    StepIn([LevelIncrement])
    StepOut([LevelDecrement])

  Fields:

    IndentUnitStr
    LineTerminator
    Level
    LIStr

  '''

  #-----------------------------------------------------------------------------

  def __init__(self, IndentUnitStr='  ', StartingLevel=0, LineTerminator='\n'):

    u'''Construct a keeper for the current indentation level for text output.

    All three arguments are optional.

    IndentUnitStr is the string used for each level of indentation.
    This string is typically two spaces (to emulate the em-square of
    typography), four spaces or a tab control character.

    StartingLevel, which defaults to zero, sets the current indentation
    level.

    LineTerminator is the character or string appended to each string
    argument supplied to the default method, a function which returns
    indented and line-terminated text.

    '''

    self.IndentUnitStr = IndentUnitStr
    self.LineTerminator = LineTerminator
    self.Level = StartingLevel
    self.LIStr = IndentUnitStr * StartingLevel

  #-----------------------------------------------------------------------------

  def __call__(self, *StringArgs):

    u'''Return a block of text with lines indented and terminated.

    Each argument is taken to be a line of text which is to be indented
    at the current level and terminated with LineTerminator. If a list
    or tuple of strings is to be processed, use the list or tuple unpacking
    operator “*”.

    '''

    IndentedLines = []
    for Line in StringArgs:
      ILine = Line.rstrip()
      if len(Line) > 0:
        ILine = self.LIStr + ILine
      IndentedLines.append(ILine)

    Result = self.LineTerminator.join(IndentedLines) + self.LineTerminator

    return Result

  #-----------------------------------------------------------------------------

  def Clone(self):

    u'''Create a clone of this tIndentTracker instance.

    A clone is handy for temporarily going into deeper nesting levels when
    the supplied tIndentTracker instance must be treated as immutable.

    '''

    Result = tIndentTracker()

    # Return an exact copy, even if it is internally inconsistent.
    # The user probably knows what they’re doing.

    Result.IndentUnitStr = self.IndentUnitStr
    Result.LineTerminator = self.LineTerminator
    Result.Level = self.StartingLevel
    Result.LIStr = self.LIStr

    return Result

  #-----------------------------------------------------------------------------

  def StepIn(self, LevelIncrement=1):

    u'''Increase the indentation level.

    The fields Level and the convenience string LIStr are updated.

    '''

    self.Level += LevelIncrement
    self.LIStr = self.IndentUnitStr * max(0, self.Level)

  #-----------------------------------------------------------------------------

  def StepOut(self, LevelDecrement=1):

    u'''Decrease the indentation level.

    The fields Level and the convenience string LIStr are updated.

    '''

    self.Level -= LevelDecrement
    self.LIStr = self.IndentUnitStr * max(0, self.Level)

  #-----------------------------------------------------------------------------

#-------------------------------------------------------------------------------
# tAffineMtx
#-------------------------------------------------------------------------------


class tAffineMtx (object):

  u'''Affine matrix for transforming non-homogeneous vectors

  An affine matrix is the usual square transformation matrix augmented
  with a translation vector. Thus uniform and non-uniform scaling,
  shearing, rotation and translation transformations can be combined
  in any order. Using the convention that vectors are written as columns,
  an affine matrix is like a homogeneous matrix without the bottom row and
  is used to transform non-homogeneous vectors or other affine matrices.

  Methods:

    __init__(Origin, BasisVectors)
    __repr__()
    MultV(Vector)
    MultVectors(Vectors)
    MultAM(AM)

  Fields:

    B - Basis vectors (rotation, scaling, skewing)
    T - Translation (Local origin)

  '''

  #-----------------------------------------------------------------------------

  def __init__(self, Origin, BasisVectors):

    u'''Construct an affine matrix.

    The origin is loaded into the translation part and is measured in terms
    of the reference frame outside the local frame constructed by the basis
    vectors and the origin.

    '''

    self.B = tuple(tuple(Bi) for Bi in BasisVectors)
    self.T = tuple(Origin)

  #-----------------------------------------------------------------------------

  def __repr__(self):

    u'''Return a Python code string representation of this affine matrix.'''

    Name = self.__class__.__name__
    return Name + '(' + repr(self.T) + ', ' + repr(self.B) + ')'

  #-----------------------------------------------------------------------------

  def MultV(self, Vector):

    u'''Return a vector transformed by this matrix.

    The vector is permitted to have a number of dimensions that differ to
    the number of basis vectors represented in the affine matrix. Excess
    basis vectors or excess vector components are ignored.

    If the vector is None or has a length of zero, the vector is returned
    untransformed. This behaviour is convenient for processing Shapes, which
    may include items like (Pt_Break, None).

    '''

    if (Vector is not None) and (len(Vector) > 0):

      Result = self.T

      for i, Basis in enumerate(self.B):
        if i < len(Vector):
          Result = VSum(Result, VScaled(Basis, Vector[i]))

    else:

      Result = Vector

    return Result

  #-----------------------------------------------------------------------------

  def MultVectors(self, Vectors):

    u'''Return a tuple of vectors transformed by this affine matrix.

    The vectors are each permitted to have a number of dimensions
    different to the number of basis vectors represented in the
    affine matrix. Excess basis vectors or excess vector components
    are ignored.

    Any vector that is None or has a length of zero is appears in
    the result untransformed.

    '''

    Result = []

    for V in Vectors:

      if (V is not None) and (len(V) > 0):

        VPrime = self.T

        for i, Basis in enumerate(self.B):
          if i < len(V):
            VPrime = VSum(VPrime, VScaled(Basis, V[i]))

      else:

        VPrime = V

      Result.append(VPrime)

    Result = tuple(Result)

    return Result

  #-----------------------------------------------------------------------------

  def MultAM(self, AM):

    u'''Return the product of this and a second affine matrix.

    When the resulting affine matrix is applied to vertices, the effect is as
    if the second matrix was applied first and the first matrix applied last.
    From the point of view of nested transformed reference frames in the manner
    of SVG and OpenGL, the transformations are nested in left-to-right order.

    Considering the vectors to be transformed as column vectors, the nesting of
    reference frames is performed by postmultiplying the current affine matrix
    with successive (affine) transformation matrices. The composite matrix is
    then premultiplied to each vector to be transformed.

    '''

    d = len(self.T)
    dr = range(d)

    B1t = VTransposedMAV(self.B)
    T1 = self.T
    B2 = AM.B
    T2 = AM.T

    BasisVectors = tuple(tuple(VDot(B1t[j], B2[i]) for j in dr) for i in dr)
    Traslation = tuple(VDot(B1t[j], T2) + T1[j] for j in DimRange)

    return tAffineMtx(Translation, BasisVectors)

  #-----------------------------------------------------------------------------


#-------------------------------------------------------------------------------
# Affine matrix creation functions
#-------------------------------------------------------------------------------


def AffineMtxTS(Translation, Scale):

  u'''Return an affine matrix given a translation and a scale.

  When the tAffineMtx returned is applied to vertices, the translation
  is performed last. From the point of view of transformed reference
  frames in the manner of SVG and OpenGL, the translation is performed
  first.

  The dimension of the resulting affine matrix is made to match the
  dimension of Translation, which defines a local origin relative to
  the origin of the ambient frame.

  If Scale is or contains only a single number, the scaling is uniform.
  If Scale is a list or tuple, say, the scaling can be different for
  each axis. Negative scales are permissible. Excess scale components
  are ignored and unspecified scale components are assumed to be 1.0.

  '''

  #-----------------------------------------------------------------------------

  d = len(Translation)
  dr = range(d)

  if hasattr(Scale, '__iter__'):
    S = tuple(Scale)[:d]
    S += (1.0,) * max(0, d - len(S))
  else:
    S = (Scale,) * d

  BasisVectors = VDiagonalMAV(S)

  return tAffineMtx(Translation, BasisVectors)


#-------------------------------------------------------------------------------


def AffineMtxTRS2D(Translation, Angle, Scale):

  u'''Return an affine matrix given a translation, rotation angle and a scale.

  Translation must be a vector of at least two dimensions, More dimensions
  are permitted but the rotation is performed only in the plane of the first
  two.

  Angle is measured in radians from the +x axis to the +y axis of the ambient
  frame.

  The transformation is applied to vectors in the order scaling, rotation
  and translation. From the point of view of nested reference frames in
  the manner of OpenGL and SCG, the order of nested transformations is
  translation, rotation and scaling.

  '''

  d = len(Translation)
  AM = AffineMtxTS(Translation, Scale)

  c = cos(Angle)
  s = sin(Angle)

  xs = AM.B[0][0]
  ys = AM.B[1][1]
  B = ((xs * c, xs * s), (ys * -s, ys * c))

  return tAffineMtx(AM.T, B)


#-------------------------------------------------------------------------------


def Affine2DMatrices(Origin, X):

  u'''Create matrices for mapping a line in 2D space to (0,0)–(1,0) and back.

  The line’s endpoints lie at Origin and Origin + X. This function gives the
  scale, rotation and translation necessary to map the line onto the x-axis
  between 0 and 1, thus aiding quick intersection and rejection tests.

  The result is in the form (M, InvM) where:

    M is the affine matrix to transform points so Line maps to (0,0)–(1,0) and
    InvM restores points from the UnitX frame back to the original frame.

  If the vector X is too small, an overflow or a divide-by-zero exception
  may be raised.

  '''

  Y = VPerp(X)

  # The scale to use in forming the inverse matrix’s basis vectors is
  # is the inverse square of the length of the X basis vector, not just
  # the inverse length. This is because the lengths of the basis vectors
  # of one matrix must be the reciprocals of those of the other.
  # ‖(‖X‖⁻²X)‖ × ‖X‖ = 1.

  s2 = 1.0 / VLengthSquared(X)

  MX = (s2 * X[0], s2 * Y[0])
  MY = (s2 * X[1], s2 * Y[1])
  MT = (
    -(MX[0] * Origin[0] + MY[0] * Origin[1]),
    -(MX[1] * Origin[0] + MY[1] * Origin[1]),
  )
  M = tAffineMtx(MT, (MX, MY))
  InvM = tAffineMtx(Origin, (X, Y))

  return (M, InvM)


#-------------------------------------------------------------------------------
# Utility functions
#-------------------------------------------------------------------------------


def ValidatedRange(ARange, Length):

  u'''Return a validated range for a given array length.

  The validated range may have a span of zero and it may lie at the end of
  a zero-based array (at an index of Length). It will, however, be sure to
  not be reversed or include intervals beyond either end of the array.

  if ARange is None, the range (0, Length) is returned. This behaviour
  makes it convenient to use this function on optional range arguments.

  '''

  if ARange is None:

    Start, End = (0, Length)

  else:

    Start, End = ARange

    Start = min(Length, Start) if Start >= 0 else max(0, Length + Start)
    End = min(Length, End) if End >= 0 else Length + End
    End = max(Start, End)

  return (Start, End)


#-------------------------------------------------------------------------------


def MergedDictionary(Original, Patch):

  u'''Return the union of two Python dictionaries.

  In the case of a key appearing in both dictionaries, Patch takes
  precedence over Original.

  For the convenience of easily providing defaults or immutable
  attributes to HTML or SVG tags, either argument may be None.
  In any case, the result is a (shallow) copy.

  '''

  if Original is not None:
    if Patch is not None:
      return dict(list(Original.items()) + list(Patch.items()))
    else:
      return dict(Original)
  else:
    if Patch is not None:
      return dict(Patch)
    else:
      return dict()


#-------------------------------------------------------------------------------


def Save(Data, FileName):

  u'''Save data to a new file.

  Data is usually a string. If a file with the given name already exists,
  it is overwritten.

  If the string is a Unicode string, it should be encoded:

    Save(Data.encode('utf_8'), FileName)

  Encoding will fail if Data is a non-Unicode string which contains a
  character outside of the 7-bit ASCII range. This can easily occur
  when an ordinary byte string contains a Latin-1 character such as
  the times symbol (“×”, code 215). Take care to prefix non-ASCII
  string constants with “u”.

  '''

  f = open(FileName, 'wb')

  try:
    f.write(Data)
  finally:
    f.close()


#-------------------------------------------------------------------------------
# Array access functions
#-------------------------------------------------------------------------------


def ArrayDimensions(MDArray):

  u'''Measure the size of the array in each dimension.

  If the given array is three dimensional and indexed with subscripts
  [0…5][0…7][0…2], the result will be (6, 8, 3).

  The array, which in Python is really an array of arrays if it is
  multidimensional, is assumed to be linear, rectangular, cuboid or
  similarly regular for higher dimensions.

  An empty array has a dimension of zero.

  '''

  Result = []
  Axis = MDArray
  while hasattr(Axis, '__iter__'):
    Result.append(len(Axis))
    if len(Axis) < 1:
      break
    Axis = Axis[0]
  Result = tuple(Result)
  return Result


#-------------------------------------------------------------------------------


def NewArray(Dimensions, Value):

  u'''Return a new array of the given dimensions, filled with a given value.

  Dimensions may either be a tuple or a list. When creating one-dimensional
  arrays, remember that the tuple or list constructor is needed around a
  bare integer and that the syntax for a one-element tuple has a comma to
  distinguish a tuple from an parenthesised number.

    NewArray((5,), 42) = [42, 42, 42, 42, 42]

  '''

  n = len(Dimensions)
  if n < 2:
    Result = [Value] * Dimensions[0]
  else:
    Result = []
    for i in range(Dimensions[0]):
      Result.append(NewArray(Dimensions[1:], Value))
  return Result


#-------------------------------------------------------------------------------


def CopyArray(Source, CopyDepth=None):

  u'''Create an arbitrarily deep copy of an array.

  If CopyDepth is 0, the result is another reference to the same array,
  not a copy. If CopyDepth is 1, a shallow copy is made. Higher values of
  CopyDepth result in deeper copies. This allows one to create separately
  mutable multidimensional arrays to refer to objects shared between them.

  Negative values for CopyDepth work in the manner of negative slice
  indices in python: A value of -1, for example, causes the entries of
  the final dimension to be shared.

  If CopyDepth is None (the default), the result will be a completely
  distinct copy.

  The behaviour of this function with CopyDepth set to None is subtly
  different to that for negative values of CopyDepth. A value of -1
  or lower causes the ArrayDimensions() function to be invoked. The
  measurement then makes the assumption of the array being regular
  important.

  This function cannot be used with arrays which contain circular
  references.

  '''

  #-----------------------------------------------------------------------------

  def CopyArray_Recursive(Source, d):
    if d == 0 or not hasattr(Source, '__iter__'):
      Result = Source
    elif d == 1:
      Result = [x for x in Source]
    else:
      Result = [CopyArray_Recursive(x, d - 1) for x in Source]
    return Result

  #-----------------------------------------------------------------------------

  if CopyDepth is None:
    d = -1
  else:
    d = CopyDepth
    if d < 0:
      d = max(0, len(ArrayDimensions(Source)) + d)

  return CopyArray_Recursive(Source, d)


#-------------------------------------------------------------------------------


def At(MDArray, Indices):

  u'''Return an array element of the given indices.

  An array element that would be accessed as A[3][1][0], say, can
  be accessed as At(A, (3, 1, 0)) or as At(A, X) where X = (3, 1, 0).
  This is handy for writing code that is agnostic in regard to the
  number of dimensions being used.

  Remember that Indices must be a tuple, a list or something similar
  and that the Python syntax for a single-element tuple is “(x,)”.

  '''

  Result = MDArray
  for i in Indices:
    Result = Result[i]
  return Result


#-------------------------------------------------------------------------------


def SetAt(MDArray, Indices, Value):

  u'''Set an array element at the given indices.

  An array element that would be set with the statement A[1][5][2] = x,
  say, can be set with SetAt(A, Pos, x) where Pos is (1, 5, 2).

  Remember that Indices must be a tuple, a list or something similar
  and that the Python syntax for a single-element tuple is “(x,)”.

  '''

  Target = MDArray
  for i in Indices[:-1]:
    Target = Target[i]
  Target[Indices[-1]] = Value


#-------------------------------------------------------------------------------


def EnumerateArray(MDArray, Depth=None):

  u'''Enumerate the indices and the elements of a multidimensional array.

  The result is a generator which can be used in the following manner:

    for Pos, Element in EnumerateArray(MDArray):
      ...

  Pos is a tuple of the indices required to access the array using At
  (reading) or SetAt (writing). Element is already set to At(MDArray, Pos).

  Depth, an optional argument in the constructor, allows the traversal
  to be restricted to the major dimensions. In the manner of Python
  array indices, Depth may be given a negative value.

  A value of -1 for Depth causes all but the last dimension to be
  traversed. This can be handy for efficiently updating the contents
  of a multidimensional array. If Depth is zero, the enumeration yields
  nothing.

  '''

  Dim = ArrayDimensions(MDArray)

  if Depth is None:
    d = len(Dim)
  else:
    d = Depth
    if d < 0:
      d += len(Dim)
    Dim = Dim[:d]

  Pos = [0] * len(Dim)
  i = len(Pos) - 1

  while i >= 0:
    yield (tuple(Pos), At(MDArray, Pos))
    while i >= 0:
      x = (Pos[i] + 1)
      if x < Dim[i]:
        Pos[i] = x
        i = len(Pos) - 1
        break
      else:
        Pos[i] = 0
        i -= 1


#-------------------------------------------------------------------------------
# Basic vector functions
#
# For serious work with linear algebra, the numpy module is useful, though
# it’s handy to have basic vector functions which work with the tuples or
# lists commonly used as vectors.
#
# Vectors are assumed to be column vectors represented by zero-based tuples
# such that
#
#       ⎡x⎤
#   A = ⎢y⎥ implies A[0] = x, A[1] = y and A[2] = z.
#       ⎣z⎦
#
# In program code, A = (x, y, z). Though lists are acceptable as arguments,
# tuples are preferred because they consume less memory, are handled much
# more quickly than lists and most importantly, are free from the risk of
# aliasing bugs. Some aliasing bugs, such as which result from using a list
# as a default argument in a function can be surprising.
#
# The vector functions here assume the vector operands have the correct or
# consistent number of dimensions.
#
#-------------------------------------------------------------------------------


def VZeros(n):

  u'''Return an n-dimensional vector of zeros.'''

  return (0.0,) * n


#-------------------------------------------------------------------------------


def VOnes(n):

  u'''Return an n-dimensional vector of ones.'''

  return (1.0,) * n


#-------------------------------------------------------------------------------


def VStdBasis(Dimensions, Index, Scale=1.0):

  u'''Return a standard basis vector, optionally scaled.

  The result is a vector with Dimension elements, all zero except
  for a 1 at the given (zero-based) index. If the argument Scale
  is specified, Scale is used instead of the 1.

  VStdBasis(4, 2, 5) returns

    ⎡0⎤
    ⎢0⎥
    ⎢5⎥
    ⎣0⎦.

  Note that it’s common to use a one-based subscript to identify the
  basis vectors: The basis vectors e₁, e₂, e₃ correspond to x, y, z.
  This function uses zero-based indices to be compatible with the
  zero-based indices of lists and tuples in Python.

  '''

  return((0.0,) * Index) + (Scale,) + ((0.0,) * (Dimensions - 1 - Index))


#-------------------------------------------------------------------------------


def VDim(A, n):

  u'''Procrastinate a vector to the required number of dimensions.'''

  d = len(A)
  if n > d:
    # To the rack!
    Result = tuple(A) + (0.0,) * (n - d)
  elif n < d:
    # To the guillotine!
    Result = tuple(A)[:n]
  else:
    # No help is needed from Procrastus.
    Result = tuple(A)
  return Result


#-------------------------------------------------------------------------------


def VAug(A, *x):

  u'''Return vector augmented with one or more extra components.

  The extra components are supplied with one or more arguments after the
  given vector. If the extra componenets are to come from a vector, use
  the tuple unpacking operator “*”.

  Though Python’s array handling functions make this a trivial operation,
  it’s nice to avoid the use of the "+" operator in a way that might imply
  arithmetic addition to a bleary-eyed programmer.

  '''

  return tuple(A) + x


#-------------------------------------------------------------------------------


def VMajorAxis(A):

  u'''Return the index of the largest component of a vector.

  This function is handy for choosing numerically robust Cartesian-to-Euler
  conversion functions.

  '''

  MajorAbsValue = 0
  MajorIx = 0

  Ix = 0

  while Ix < len(A):
    AbsValue = abs(A[Ix])
    if AbsValue > MajorAbsValue:
      MajorAbsValue = AbsValue
      MajorIx = Ix
    Ix += 1

  return MajorIx


#-------------------------------------------------------------------------------


def VNeg(A):

  u'''Return −A, the negative of a vector.

  A negated vector has the same size as the original, but points in the
  opposite direction.

  '''

  return tuple(-x for x in A)


#-------------------------------------------------------------------------------


def VSum(*VectorArgs):

  u'''Return the sum of vectors.

  The result of the sum of vectors can be described as the result of
  moving in the direction and by the distance implied by each vector
  in turn. Thus if A is 4m due east and B is 3m due north, the sum of
  A and B is 4m east and 3m north (5m at a nautical bearing of 53.13°).

  Vector addition is both commutative and associative.

  In the manner of the built-in function max(), this function can take
  either two or more vector arguments or a single argument which contains
  a list or tuple of vectors.

  '''

  if len(VectorArgs) == 1:
    Vectors = VectorArgs[0]
  else:
    Vectors = VectorArgs
  Result = tuple(Vectors[0])
  for i in range(1, len(Vectors)):
    Result = tuple(a + b for a, b in zip(Result, Vectors[i]))
  return Result


#-------------------------------------------------------------------------------


def VDiff(A, B):

  u'''Return A − B, the difference between two vectors.

  Just as in ordinary arithmetic, A − B = A + −B. If A and B are position
  vectors, the result is the position of A relative to B. Likewise, if A
  and B are velocity vectors, the result is the velocity of A relative
  to B.

  '''

  return tuple(x - y for x, y in zip(A, B))


#-------------------------------------------------------------------------------


def VSchur(*VectorArgs):

  u'''Return the Schur product of vectors.

  The Schur or Hadamard product of two vectors is the element-wise
  product of the vectors.

    ⎡4⎤ ⎡ 3⎤   ⎡ 12⎤
    ⎢7⎥○⎢−2⎥ = ⎢−14⎥
    ⎣3⎦ ⎣ 3⎦   ⎣ 9 ⎦

  In the manner of the built-in function max(), this function can take
  either two or more vector arguments or a single argument which contains
  a list or tuple of vectors.

  '''

  if len(VectorArgs) == 1:
    Vectors = VectorArgs[0]
  else:
    Vectors = VectorArgs
  Result = tuple(Vectors[0])
  for i in range(1, len(Vectors)):
    Result = tuple(a * b for a, b in zip(Result, Vectors[i]))
  return Result


#-------------------------------------------------------------------------------


def VDot(A, B):

  u'''Return A·B, the dot product of two vectors.

  The dot product of two vectors is a scalar (a number from the set of reals)
  that is a product of each of lengths of the two vectors and of the cosine
  of the angle between them. If one vector is a unit vector (a vector whose
  length is exactly 1), the dot product of that and the other vector will
  indicate the length of the projection along the unit vector cast by the
  other vector.

  The dot product of two unit vectors gives the cosine of the angle between
  them. Thus:

    +1 ⇒ Parallel
     0 ⇒ Perpendicular
    −1 ⇒ Antiparallel

  Similarly, the sign of the dot product of any two vectors indicates
  whether they are at an acute, right or obtuse angle.

  The dot product of two (Cartesian) vectors is the sum of the elements
  of the Schur product of those vectors.

  '''

  return sum(x * y for x, y in zip(A, B))


#-------------------------------------------------------------------------------


def VLengthSquared(A):

  u'''Return ‖A‖², the square of the length of a vector.

  The square of the length of a vector A is A·A and thus requires no
  transcendental functions to compute whereas computing the length of
  a vector requires a call to the square root function.

  It is usually more efficient to test the square of a vector’s length
  against the square of a threshold than to test that vector’s length
  against the threshold.

  '''

  return sum(x * x for x in A)


#-------------------------------------------------------------------------------


def VLength(A):

  u'''Return ‖A‖, the length of a vector.

  The length of a vector is the square root of the sum of the squares of its
  Cartesian components in the manner of Pythagoras. Very often, ‖A‖² is
  needed. To save calling the (transcendental) square root function and
  squaring the result, use the VLengthSquared() function wherever possible.

  '''

  return sqrt(VLengthSquared(A))


#-------------------------------------------------------------------------------


def VManhattan(A):

  u'''Return the Manhattan (or taxicab) length of a vector.

  The Manhattan length is the sum of the absolute value of the vector’s
  components. It represents the distance from the origin one must travel
  to reach a given location when only north-south and east-west travel
  is permitted.

  This function is often used to find a rough approximation to the length
  of a vector.

  '''

  return sum(abs(x) for x in A)


#-------------------------------------------------------------------------------


def VScaled(A, Scale):

  u'''Return the scalar multiple of a vector.

  A scalar multiple of a vector is one that is parallel to the original
  vector (antiparallel in the case of a negative scale) but whose length
  is the original vector’s length multiplied by the absolute value of scale.

  Often a vector of a desired length is constructed from a unit vector
  and a scalar. A vehicle with a position P and an orientation given by
  a unit heading vector H made to travel a distance d in a straight line
  will arrive at P + d(H) where d(H) is H scaled by d.

  '''

  return tuple(x * Scale for x in A)


#-------------------------------------------------------------------------------


def VNormalised(A):

  u'''Return ‖A‖⁻¹(A), a unit vector parallel to the given vector.

  Unit vectors are vectors with a length (or "norm") of one. They are often
  used as basis vectors for defining coordinate systems or for indicating
  direction without magnitude.

  No exception is raised if the vector is null or an overflow results.
  Instead, a sensible-looking, made-up unit vector is returned.

  '''

  try:
    Result = VScaled(A, 1.0 / VLength(A))
  except (ZeroDivisionError, OverflowError):
    Result = VStdBasis(len(A), VMajorAxis(A))
  return Result


#-------------------------------------------------------------------------------


def VPerp(A):

  u'''Return the original 2D vector rotated by positive 90 degrees.

  Rotation is always positive when a point lying on the positive
  half of the first axis moves in the direction of the positive
  half of the second axis. On a graph where x is right and y is
  up, the perpendicular vector returned is anticlockwise from the
  original vector.

  The operator is written as superscript “up tack” to the right of
  the vector. In a manner similar to that of the 3D cross product
  operator, a mnemonic for the calculation is a construct resembling
  the determinant of a matrix:

    Perp(A) = ⎢ Ax  Ay  ⎥
              ⎢ <x> <y> ⎥

  '''

  return (-A[1], A[0])


#-------------------------------------------------------------------------------


def VRevPerp(A):

  u'''Return the original 2D vector rotated by negative 90 degrees.

  See VPerp().

  '''

  return (A[1], -A[0])


#-------------------------------------------------------------------------------


def VCrossProduct(A, B):

  u'''Return A × B, the vector cross product of two 3D vectors.

  The returned vector is perpendicular to both A and B, in the direction
  given by the left hand rule or the right hand rule, depending on the
  hand of the coordinate system used. The length of the resulting vector
  is proportional to the length of A, the length of B and the sine of the
  angle between A and B.

  The length of the cross product is the area of a parallelogram spanned
  by A and B. The area of a triangle spanned by A and B is half this value,
  a useful thing to know when it comes to calculating the area of a polygon.

  A mnemonic for calculating the cross product is a construction resembling
  the determinant of a matrix:

            ⎢ Ax  Ay  Az  ⎥
    A × B = ⎢ Bx  By  Bz  ⎥
            ⎢ <x> <y> <z> ⎥

   Some linear algebra textbooks have the standard basis vectors along the
   top row rather than the bottom row. Although that form of the determinant
   mnemonic yields the correct result in 3D or higher odd-numbered dimensions,
   the form shown above works just as well when it is applied to 2D or higher
   even-numbered dimensions.

   Remember that the cross product operator is neither commutative nor
   associative. In fact, A × B = −(B × A).

  '''

  return (
    (A[1] * B[2]) - (A[2] * B[1]),
    (A[2] * B[0]) - (A[0] * B[2]),
    (A[0] * B[1]) - (A[1] * B[0])
  )


#-------------------------------------------------------------------------------


def VCrossProduct4D(A, B, C):

  u'''Return the four-dimensional cross product of three 4D vectors.

  Explaining this function would require four dimensional hands or the help
  of one of the Centaurs in Greg Egan’s book Diaspora but the result can be
  calculated from this determinant-shaped mnemonic:

    ⎢ Ax  Ay  Az  Aw  ⎥
    ⎢ Bx  By  Bz  Bw  ⎥
    ⎢ Cx  Cy  Cz  Cw  ⎥
    ⎢ <x> <y> <z> <w> ⎥

  '''

  x = -(
    A[1] * (B[2] * C[3] - B[3] * C[2]) -
    A[2] * (B[1] * C[3] - B[3] * C[1]) +
    A[3] * (B[1] * C[2] - B[2] * C[1])
  )

  y = (
    A[0] * (B[2] * C[3] - B[3] * C[2]) -
    A[2] * (B[0] * C[3] - B[3] * C[0]) +
    A[3] * (B[0] * C[2] - B[2] * C[0])
  )

  z = -(
    A[0] * (B[1] * C[3] - B[3] * C[1]) -
    A[1] * (B[0] * C[3] - B[3] * C[0]) +
    A[3] * (B[0] * C[1] - B[1] * C[0])
  )

  w = (
    A[0] * (B[1] * C[2] - B[2] * C[1]) -
    A[1] * (B[0] * C[2] - B[2] * C[0]) +
    A[2] * (B[0] * C[1] - B[1] * C[0])
  )

  return (x, y, z, w)


#-------------------------------------------------------------------------------


def VScalarTripleProduct(A, B, C):

  u'''Return A·B×C, the scalar triple product of three 3D vectors.

  The result is a scalar whose absolute value happens to be the volume of a
  parallelepiped spanned by the three vectors. The volume of a tethrahedron
  spanned by the same vectors is 1/6 of this value, a useful thing to know
  when it comes to finding the volume of a polyhedron.

  The effect of reordering the arguments is only a possible change of sign
  of the result. If A, B and C follow the right-hand rule in a right-handed
  coordinate system, the result will be positive.

  If the result is zero, two or all three of the vectors are co-planar.

  u'''

  return VDot(A, VCrossProduct(B, C))


#-------------------------------------------------------------------------------


def VVectorTripleProduct(A, B, C):

  u'''Return A×(B×C), the vector triple product of three vectors.

  This function is included to keep VScalarTripleProduct from getting
  lonely. Apparently it has some meaning in physics.

  There are two forms of the vector triple product:

    A×(B×C) = B(A·C) − C(A·B)
    (A×B)×C = B(A·C) − A(C·B)

  This function returns the first one, Lagrange’s form.

  u'''

  return VDiff(
    VScaled(B, VDot(A, C)),
    VScaled(C, VDot(A, B))
  )


#-------------------------------------------------------------------------------


def VProjectionOnto(Axis, Vector):

  u'''Return the component of Vector that lies along Axis.

  Axis need not be normalised.

             A·V
  Proj (V) = ―――(A)
      A      A·A

  Note that no square root calculation is necessary.

  The component of Vector that is perpendicular to Axis can be
  found by subtracting the result of this function from Vector.

  If Axis is null or an overflow occurs, no exception is raised.
  Instead, a null vector is returned.

  '''

  try:
    Result = VScaled(
      Axis,
      VDot(Vector, Axis) / (1.0 * VLengthSquared(Axis))
    )
  except (ZeroDivisionError, OverflowError):
    Result = VZeros(len(Vector))
  return Result


#-------------------------------------------------------------------------------


def VDiagonalMAV(Diagonals):

    u'''Create a matrix-as-vectors with the entries for the main diagonal set.

                              ⎡1 0 0⎤   ⎛⎡1⎤ ⎡0⎤ ⎡0⎤⎞
    VDiagonalMAV((1, 3, 7)) = ⎢0 3 0⎥ = ⎜⎢0⎥,⎢3⎥,⎢0⎥⎟
                              ⎣0 0 7⎦   ⎝⎣0⎦ ⎣0⎦ ⎣7⎦⎠

    Because a diagonal matrix is its own transpose, the result can be thought
    of as either an array of column vectors or an array of row vectors. Here,
    the convention is that vectors are considered column vectors and matrices
    are arrays of column vectors.

    '''

    return tuple(
      VStdBasis(len(Diagonals), i, x) for i, x in enumerate(Diagonals)
    )


#-------------------------------------------------------------------------------


def VTransposedMAV(MtxAsVectors):

  u'''Return the transpose of a square matrix defined as a bunch of vectors.

  A matrix entry at i,j corresponds to the entries j,i in the transpose.

                  ⎛⎡a⎤ ⎡d⎤ ⎡g⎤⎞   ⎛⎡a⎤ ⎡b⎤ ⎡c⎤⎞
    VTransposedMAV⎜⎢b⎥,⎢e⎥,⎢h⎥⎟ = ⎜⎢d⎥,⎢e⎥,⎢f⎥⎟
                  ⎝⎣c⎦ ⎣f⎦ ⎣i⎦⎠   ⎝⎣g⎦ ⎣h⎦ ⎣i⎦⎠

  Note that matrix subscripts like i,j in maths refers to row i, column j
  (even where column vectors are used) while indexing elements of a matrix
  made of column vectors in Python requires subscripts of the form [j][i]
  (though i and j would both start at zero instead of one).

  '''

  DimRange = range(len(MtxAsVectors))
  return tuple(tuple(MtxAsVectors[j][i] for j in DimRange) for i in DimRange)


#-------------------------------------------------------------------------------


def VRectToPol(A):

  u'''Return the polar (distance, angle) form of a Cartesian (x, y) vector.

  The angle is given in radians y-from-x and ranges from −pi to +pi.
  If the given vector is null (0, 0), the result is also (0, 0).

  '''

  Distance = VLength(A)
  Angle = atan2(A[1], A[0])
  return (Distance, Angle)


#-------------------------------------------------------------------------------


def VPolToRect(DistanceAngle):

  u'''Return the Cartesian (x, y) form of a polar (distance, angle) vector.

  The angle is taken to be in radians y-from-x.

  '''

  c = cos(DistanceAngle[1])
  s = sin(DistanceAngle[1])
  return (DistanceAngle[0] * c, DistanceAngle[0] * s)


#-------------------------------------------------------------------------------


def VLerp(A, B, Progress):

  u'''Linearly interpolate between two vectors.

  If Progress is 0.0, A is returned. If Progress is 1.0, B is returned.
  A value of Progress between 0.0 and 1.0 yields a result that is a linear
  interpolation of A and B.

  This function can be used to blend colours, though if non-linear RGB
  values (such as stored in computer frame buffers) are used, it is
  important to convert them to linear RGB values in order to perform
  interpolation (blending) or indeed any meaningful colour arithmetic.

  Progress is not restricted to the range 0.0 to 1.0. The result of using
  a value for Progress that is less than zero or greater than one is a
  linear extrapolation.

  '''

  return VSum(
    VScaled(A, 1.0 - Progress),
    VScaled(B, Progress)
  )


#-------------------------------------------------------------------------------
# Mathematical functions
#-------------------------------------------------------------------------------


def BinomialCoefficient(n, k):

  u'''Return n-choose-k.

          k
      0 1 2 3 4⋯
     ┌─────────
    0│1
    1│1 1
  n 2│1 2 1
    3│1 3 3 1
    4│1 4 6 4 1
       ⋮

  The binomial coefficients are the coefficients that result from
  the expansion of (x + 1)ⁿ, e.g., 1x⁴ + 4x³ + 6x² + 4x + 1 for n = 4.

  '''

  if k >= 0 and k <= n:

    # The basic algorithm is now sufficiently guarded. All
    # the other “if” statements are merely for optimisation.

    if k == 0 or k == n:

      Result = 1

    else:

      if n < 4:

        Result = n

      else:

        if k <= (n // 2):
          j = k
        else:
          j = n - k

        # The basic algorithm begins here (but using j instead of k).

        Numerator = 1
        Divisor = 1
        i = 1

        while i <= j:
          Numerator *= (n - j + i)
          Divisor *= i
          i += 1

        Result = Numerator / Divisor

  else:

    Result = 0

  return Result


#-------------------------------------------------------------------------------


def BinomialRow(n):

  u'''Return an entire row of binomial coefficients.'''

  if n < 1:

    if n == 0:
      Result = (1,)
    else:
      Result = ()

  else:

    R = [1] + n * [0]
    i = 1

    while i <= n:
      j = i - 1
      while j >= 1:
        R[j] = R[j] + R[j - 1]
        j -= 1
      R[i] = 1
      i += 1

    Result = tuple(R)

  return Result


#-------------------------------------------------------------------------------


def NextBinomialRow(Row):

  u'''Return the successive row of binomial coefficients.

  The given row must be a tuple or list of valid binomial coefficients.
  The first valid row, then, is a list containing 1 (or 1.0).

  '''

  w = len(Row)

  if w > 0:

    R = [1]
    k = 1

    while k < len(Row):
      R.append(Row[k - 1] + Row[k])
      k += 1
    R.append(Row[0])

    Result = tuple(R)

  else:

    Result = (1,)

  return Result



#-------------------------------------------------------------------------------


def ApproxSaggita(ArcLength, ChordLength):

  u'''Approximate the saggita of a circular arc, given arc and chord lengths.

  The saggita is the distance between the midpoint of the arc and
  the midpoint of the chord, the line connecting the arc’s endpoints.
  If the arc is imagined as a bow and the chord the string, the saggita
  is the arrow. (“Saggita” means arrow.)

  '''

  return sqrt(0.1875 * (ArcLength * ArcLength - ChordLength * ChordLength))


#-------------------------------------------------------------------------------


def LGQIntegral25(Interval, Fn, InitalParams, FinalParams):

  u'''Perform 25-point Legendre–Gauss quadrature integration on a function.

  Interval is the range of integration in the form (x-start, x-finish).
  Fn is the function to be integrated, called with varying values of x,
  as determined by a table of Legendre–Gauss quadrature abscissae.
  InitialParams, x and FinalParams form the arguments for the function Fn.

  '''

  # The Gauss quadrature rule only integrates ∫f(x).dx over [−1,+1].
  # To integrate over [a,b], we must use ½(b−a)∫f(½(b−a)x + ½(b+a)).dx.
  # Thus to integrate over [0,t], we use ½t∫f(½tx + ½t).dx.

  a, b = Interval
  Scale = 0.5 * (b - a)
  Offset = 0.5 * (b + a)

  # Assemble the parameters. Just so the parameters don’t have to be
  # repeatedly concatenated, a single entry in the composite argument
  # list is marked for repeated overwriting with the value of x.

  IP = list(InitalParams)
  FP = list(FinalParams)
  Params = IP + [None] + FP
  XParamIx = len(IP)

  WFSum = 0.0
  i = 25

  while i > 0:
    i -= 1
    x = Scale * LGQAbscissae25[i] + Offset;
    Params[XParamIx] = x
    WFSum += LGQWeights25[i] * Fn(*Params)

  return Scale * WFSum

#-------------------------------------------------------------------------------


def IntegralFunctionOfPLF(Vertices, C=0.0):

  u'''Return QPF data for the integral of a piecewise linear function.

  The piecewise linear function is specified with a list of (x,y) vertices,
  the x components of which must be monotonically increasing. The result is
  a more complicated structure representing a piecewise quadratic function
  that is the integral of the given function.

  The linear function is assumed to be zero outside of the domain implied
  by the list of vertices. Thus C is both the integration constant and the
  value of the integral for the minimum value of x in the domain.

  The result is a list of ((x₀, S₀), (x₁, S₁), (a, b, c)) tuples where
  (x₀, S₀) is the start point of a segment, (x₁, S₁) is the segment’s
  end point and a, b and c are the coefficients of the polynomial
  S(x) = ax² + bx + c for that segment.

  '''

  Result = []
  S0 = C
  i = 0

  while i + 1 < len(Vertices):

    x0, y0 = Vertices[i]
    x1, y1 = Vertices[i + 1]
    dx = x1 - x0
    dy = y1 - y0

    if dx > 0.0:

      g = float(dy) / float(dx)

      # Find a, b and c in the expression ax² + bx + c.
      a = 0.5 * g
      b = y0 - g * x0
      c0 = x0 * (x0 * a + b)
      c = S0 - c0

      S1 = x1 * (x1 * a + b) + c
      Result.append(((x0, S0), (x1, S1), (a, b, c)))
      S0 = S1

    i += 1

  return Result


#-------------------------------------------------------------------------------


def EvaluatePQF(PQF, x):

  u'''Evaluate a piecewise quadratic function at x.

  The function is specified with a list of ((x₀, y₀), (x₁, y₁), (a, b, c))
  tuples where (x₀, y₀) is the start point of a segment, (x₁, y₁) is the
  segment’s end point and a, b and c are the coefficients of the polynomial
  y = ax² + bx + c for that segment.

  The segments must be continuous and monotonically increasing in x.

  '''

  FirstPoint = PQF[0][0]

  if x <= FirstPoint[0]:

    Result = FirstPoint[1]

  else:

    FinalPoint = PQF[-1][1]

    if x >= FinalPoint[0]:

      Result = FinalPoint[1]

    else:

      # Start with initial inclusive index bounds.
      LowIx = 0
      HighIx = len(PQF) - 1

      while HighIx > LowIx:
        MidIx = LowIx + ((HighIx - LowIx) // 2)
        x1 = PQF[MidIx][1][0]
        if x1 <= x:
          LowIx = MidIx + 1
        else:
          HighIx = MidIx
      # Whatever happens, LowIx = HighIx

      # The quadratic function is given as the coefficients in ax² + bx + c.
      QF = PQF[LowIx]
      a, b, c = QF[2]
      Result = x * (x * a + b) + c

  return Result


#-------------------------------------------------------------------------------


def EvaluateInvPQF(PQF, y):

  u'''Evaluate at y, the inverse of a piecewise quadratic function.

  The (non-inverted) function is specified with a list of ((x₀, y₀),
  (x₁, y₁), (a, b, c)) tuples where (x₀, y₀) is the start point of a
  segment, (x₁, y₁) is the segment’s end point and a, b and c are the
  coefficients of the polynomial y = ax² + bx + c for that segment.

  The segments must be continuous and monotonically increasing in both
  x and y.

  '''

  FirstPoint = PQF[0][0]

  if y <= FirstPoint[1]:

    Result = FirstPoint[0]

  else:

    FinalPoint = PQF[-1][1]

    if y >= FinalPoint[1]:

      Result = FinalPoint[0]

    else:

      # Start with initial inclusive index bounds.
      LowIx = 0
      HighIx = len(PQF) - 1

      while HighIx > LowIx:
        MidIx = LowIx + ((HighIx - LowIx) // 2)
        y1 = PQF[MidIx][1][1]
        if y > y1:
          LowIx = MidIx + 1
        else:
          HighIx = MidIx
      # Whatever happens, LowIx = HighIx

      QF = PQF[LowIx]

      # The formula for roots of quadratics is x = (−b ± √(b² - 4ac))/(2a)
      # so x = (−b ± √(b² - 4a(c - y)))/(2a).

      a, b, c = QF[2]

      if abs(a) < 1e-6:
        # The segment is close to linear.
        Result = (y - c) / b
      else:
        # The segment is parabolic.
        det = max(0.0, b * b - 4 * a * (c - y))
        Result = (-b + sqrt(det)) / (2 * a)

  return Result


#-------------------------------------------------------------------------------
# Linear intersection functions
#-------------------------------------------------------------------------------


def LineParameter(Point, Line):

  u'''Return a point’s corresponding parameter of a linear parametric function.

  The line is specified with two points, the first of which maps to
  parameter t = 0 and the second of which maps to t = 1. The point’s
  projection onto the line rather than the point itself is measured.

  The line is considered to be infinite in extent and the result may
  have a value less thank zero or greater than one.

  If the length of the line is zero or is very small, an exception is
  likely to be raised.

  '''

  K = VDiff(Point, Line[0])
  L = VDiff(Line[1], Line[0])
  t = VDot(K, L) / VLengthSquared(L)

  return t


#-------------------------------------------------------------------------------


def XInterceptOfLine(Line):

  u'''Return where an infinitely long line crosses the x axis.

  The line is described with two points. If no intersection with
  the x axis is found (because the line is horizontal, say), None
  is returned.

  If an intersection is found, The result is the value of x at the
  intersection rather than a coordinate pair.

  '''

  P1, P2 = Line

  x1, y1 = P1
  x2, y2 = P2

  try:
    Result = (x1 * y2 - y1 * x2) / float(y2 - y1)
  except (ZeroDivisionError, OverflowError):
    Result = None

  return Result


#-------------------------------------------------------------------------------


def UnitXToLineIntersection(Line2):

  u'''Return a [0..1] x-intercept as a pair of line parameters.

  The first line segment lies on the x-axis from x = 0 to x = 1. The
  second line, given by the argument Line2 is defined with two endpoints.
  The result is of the form (t1, t2) where t1 and t2 are parameters
  between 0 and 1 for UnitX and Line2 respectively. If the intersection
  point lies outside either of the line segments or the lines are parallel
  or degenerate, None is returned.

  '''

  Result = None

  x1, y1 = Line2[0]
  x2, y2 = Line2[1]

  if y1 <= 0.0 <= y2 or y2 <= 0.0 <= y1:

    try:

      t2 = max(0.0, min(1.0, y1 / (y1 - y2)))
      t1 = (1.0 - t2) * x1 + t2 * x2

      if 0.0 <= t1 <= 1.0:
        Result = (t1, t2)

    except (ZeroDivisionError, OverflowError):

      MinX, MaxX = (x1, x2) if x1 <= x2 else (x2, y1)

      if MinX <= 1.0 and MaxX >= 0.0:

        t1 = 0.5 * (max(MinX, 0.0) + min(MaxX, 1.0))

        try:
          t2 = (t1 - x1) / (x2 - x1)
        except (ZeroDivisionError, OverflowError):
          t2 = 0.5

        Result = (t1, t2)

  return Result


#-------------------------------------------------------------------------------


def LineToLineIntersectionPoint(Line1, Line2):

  u'''Return the intersection of two infinitely long lines.

  Each line is described with two points. If no intersection is found
  (because the lines are parallel or close to parallel, say), None is
  returned.

  '''

  P1, P2 = Line1
  P3, P4 = Line2

  x1, y1 = P1
  x2, y2 = P2
  x3, y3 = P3
  x4, y4 = P4

  #            ⎛                                      ⎞
  #            ⎜ ⎢⎢x1 y1⎥ ⎢x1 1⎥⎥    ⎢⎢x1 y1⎥ ⎢y1 1⎥⎥ ⎟
  #            ⎜ ⎢⎢x2 y2⎥ ⎢x2 1⎥⎥    ⎢⎢x2 y2⎥ ⎢y2 1⎥⎥ ⎟
  #            ⎜ ⎢              ⎥    ⎢              ⎥ ⎟
  #            ⎜ ⎢⎢x3 y3⎥ ⎢x3 1⎥⎥    ⎢⎢x3 y3⎥ ⎢y3 1⎥⎥ ⎟
  #            ⎜ ⎢⎢x4 y4⎥ ⎢x4 1⎥⎥    ⎢⎢x4 y4⎥ ⎢y4 1⎥⎥ ⎟
  # (x, y)  =  ⎜――――――――――――――――――, ――――――――――――――――――⎟
  #            ⎜ ⎢⎢x1 1⎥  ⎢y1 1⎥⎥    ⎢⎢x1 1⎥  ⎢y1 1⎥⎥ ⎟
  #            ⎜ ⎢⎢x2 1⎥  ⎢y2 1⎥⎥    ⎢⎢x2 1⎥  ⎢y2 1⎥⎥ ⎟
  #            ⎜ ⎢              ⎥    ⎢              ⎥ ⎟
  #            ⎜ ⎢⎢x3 1⎥  ⎢y3 1⎥⎥    ⎢⎢x3 1⎥  ⎢y3 1⎥⎥ ⎟
  #            ⎜ ⎢⎢x4 1⎥  ⎢y4 1⎥⎥    ⎢⎢x4 1⎥  ⎢y4 1⎥⎥ ⎟
  #            ⎝                                      ⎠

  c = x1 - x2
  d = x3 - x4
  e = y1 - y2
  f = y3 - y4

  #            ⎛                ⎞
  #            ⎜ ⎢a c⎥    ⎢a e⎥ ⎟
  #            ⎜ ⎢b d⎥    ⎢b f⎥ ⎟
  # (x, y)  =  ⎜―――――――, ―――――――⎟
  #            ⎜ ⎢c e⎥    ⎢c e⎥ ⎟
  #            ⎜ ⎢d f⎥    ⎢d f⎥ ⎟
  #            ⎝                ⎠

  try:

    z = 1.0 / (c * f - e * d)

    a = x1 * y2 - y1 * x2
    b = x3 * y4 - y3 * x4

    x = (a * d - c * b) * z
    y = (a * f - e * b) * z

    Result = (x, y)

  except (ZeroDivisionError, OverflowError):

    Result = None

  return Result


#-------------------------------------------------------------------------------


def LineToLineIntersection(Line1, Line2):

  u'''Return an intersection point as a vector and as line parameters.

  Each line segment is described with two endpoints. The result is of the
  form (Point, t1, t2) where t1 and t2 are parameters between 0 and 1 for
  Line1 and Line2 respectively. If the intersection point lies outside
  either of the line segments or the lines are parallel or degenerate,
  None is returned.

  '''

  Result = None

  P = LineToLineIntersectionPoint(Line1, Line2)

  if P is not None:

    try:
      t1 = LineParameter(P, Line1)
      if 0.0 <= t1 <= 1.0:
        t2 = LineParameter(P, Line2)
        if 0.0 <= t2 <= 1.0:
          Result = (P, t1, t2)
    except (ZeroDivisionError, OverflowError):
      pass

  return Result


#-------------------------------------------------------------------------------
# Bézier functions
#-------------------------------------------------------------------------------


def CubicBezierArcHandleLength(AngleSweep):

  u'''Return the handle length to use for an approximately circular arc.

  “Handle length” refers to the distance of a cubic Bézier curve’s (inner)
  control point to the anchor (endpoint) nearest to it.

  '''

  return 4.0 / 3.0 * tan(AngleSweep / 4.0)


#-------------------------------------------------------------------------------


def BezierPoint(Curve, t):

  u'''Return the point on a Bézier curve at parameter t.

  The Bézier curve may be of any order and is specified by a list of
  control points, the first and last of which are anchors.

  The parameter t normally ranges from 0.0 to 1.0. Values outside this
  range result in extrapolations of the Bézier curve.

  '''

  # A point on a Bézier curve is a blend of all control points. The first
  # and last of those are anchor points. For a given parameter t, Each
  # successive control point is weighted with the product of a binomial
  # coefficient, an ascending power of t and a descending power of (1 − t).
  #
  # A point at parameter t on a cubic Bézier curve is thus
  #
  #   1s³𝐏₀ + 3s²t𝐏₁ + 3st²𝐏₂ + 1t³𝐏₃
  #
  # where s = (1 − t).

  # Evaluating a Bézier curve directly with a Bernstein polynomial, however
  # leads to numerical problems due to small numbers being raised to high
  # powers.

  # NumTerms = len(Curve)
  # Order = NumTerms - 1
  #
  # s = 1 - t
  #
  # SPowers = [1.0]
  # TPowers = [1.0]
  #
  # for i in range(Order):
  #   SPowers.append(s * SPowers[i])
  #   TPowers.append(t * TPowers[i])
  #
  # Result = VZeros(len(Curve[0]))
  #
  # for i in range(NumTerms):
  #   w = BinomialCoefficient(Order, i) * SPowers[Order - i] * TPowers[i]
  #   Result = VSum(Result, VScaled(Curve[i], w))

  # deCasteljau’s method is superior.

  C = Curve

  while len(C) > 1:
    D = []
    i = 1
    while i < len(C):
      D.append(VLerp(C[i - 1], C[i], t))
      i += 1
    C = D

  Result = C[0]

  return Result


#-------------------------------------------------------------------------------


def BezierPAT(Curve, t):

  u'''Return both the point and a tangent on a Bézier curve at parameter t.

  The Bézier curve may be of any order and is specified by a list of
  control points, the first and last of which are anchors.

  The parameter t normally ranges from 0.0 to 1.0. Values outside this
  range result in extrapolations of the Bézier curve.

  The result is in the form (Point, Tangent). Tangent is not normalised.

  '''

  # deCasteljau’s method

  C = Curve

  while len(C) > 2:
    D = []
    i = 1
    while i < len(C):
      D.append(VLerp(C[i - 1], C[i], t))
      i += 1
    C = D

  Point = VLerp(C[0], C[1], t)
  Tangent = VDiff(C[1], C[0])

  return (Point, Tangent)


#-------------------------------------------------------------------------------


def SplitBezier(Curve, t):

  u'''Split a Bézier curve into two parts.

  The Bézier curve may be of any order and is specified by a list of
  control points, the first and last of which are anchors.

  The parameter t normally ranges from 0.0 to 1.0. Values of t outside
  this range lie on the extrapolated curve and cause the returned curves
  to overlap and to run in opposite directions to each other.

  '''

  # The implementation of deCasteljau’s algorithm is surprisingly
  # straightforward:
  #
  # Successive lists of points describing Bézier curves of successively
  # lower orders are each formed from the linearly interpolated intermediate
  # points at parameter t for each line segment of the immediately previous
  # list. The last list to be generated contains just one point, which is
  # point at parameter t.
  #
  # The first curve segment of the split Bézier curve is formed from the
  # start point of each of the original and successive lists.
  #
  # The second curve segment is formed from the end point of each of the
  # original and successive lists. The second curve is reversed so that
  # its endpoint is the original curve’s endpoint.

  C = Curve

  C1 = []
  C2 = []

  while len(C) > 0:

    C1.append(C[0])
    C2.append(C[-1])

    D = []
    i = 1

    while i < len(C):
      D.append(VLerp(C[i - 1], C[i], t))
      i += 1

    C = D

  C2.reverse()

  return C1, C2


#-------------------------------------------------------------------------------


def BezierDerivative(Curve):

  u'''Return the first derivative of a given Bézier curve.

  Curve must have at least two points.

  The resulting curve, evaluated at parameter t, gives the derivative with
  respect to t of the original curve at evaluated at t.

  The plot of the resulting curve is called a hodograph.

  '''

  Order = len(Curve) - 1

  if Order < 1:
   raise Error(
     'Cannot compute the derivative of a Bézier curve ' +
       'with fewer than two control points.'
   )

  Result = []
  i = 0

  while i < Order:
    Result.append(VScaled(VDiff(Curve[i + 1], Curve[i]), Order))
    i += 1

  return Result


#-------------------------------------------------------------------------------


def ManhattanBezierDeviance(Curve):

  u'''Approximately measure a Bézier curve’s deviation from flatness.

  This function considers a Bézier curve flat if all the control points are
  spaced evenly between the endpoints, representing a line progressing at
  uniform velocity.

  The Manhattan distance, used to avoid a square root calculation, can
  overestimate the deviance by a factor of up to about 1.414.

  The deviance is useful for indicating the maximum distance a point on
  the curve at parameter t could be from a point parameter t on a line
  segment connecting the curve’s endpoints.

  Though strictly lateral deviance is sometimes used, the manner of
  deviance used here is far better for dealing with the small but
  easily perceptible lobes caused by inner control points lying close
  to or beyond the axial extents of the anchor control points. Lateral
  deviances on axially steady curves can be comparatively large before
  they are noticed unless there is an adjacent curve to be tracked.
  In such a case, the tolerance to use can be easily and precisely
  specified.

  '''

  Result = 0.0
  Order = len(Curve) - 1

  if Order >= 2:

    InvOrder = 1.0 / Order
    First = Curve[0]
    Last = Curve[-1]

    i = 1

    while i < Order:

      IdealCP = VLerp(First, Last, i * InvOrder)
      Deviation = VManhattan(VDiff(Curve[i], IdealCP))
      Result = max(Result, Deviation)

      i += 1

  return Result


#-------------------------------------------------------------------------------


def BezierLength(Curve, Interval=(0.0, 1.0)):

  u'''Estimate the length of a Bézier curve over a given parameter interval.

  This function uses 25-point Legendre–Gauss quadrature integration and
  deCasteljau’s algorithm over the curves’s derivative. It should be rather
  accurate and numerically stable for all but absurdly high order curves.

  If Interval is reversed, the result will be negative. As deCasteljau’s
  algorithm can both interpolate and extrapolate Bézier curves, Interval
  need not be confined to the range [0,1].

  '''

  Result = 0.0

  Order = len(Curve) - 1

  if Order < 2:

    if Order == 1:
      Result = VLength(VDiff(Curve[1], Curve[0])) * (Interval[1] - Interval[0])

  else:

    # The function to be integrated is ‖d𝐏/dt‖ where 𝐏 is the curve.
    # In the 2D case, that translates to √((d𝐏x/dt)²+(d𝐏y/dt)²).
    # Because evaluating ∫(√((d𝐏x(t)/dt)²+(d𝐏y(t)/dt)²).dt directly
    # will summon both Great Cthulhu and a great big non-Euclidean
    # jar of K-Y Jelly, the Legendre–Gauss quadrature numerical method
    # is used instead.

    def LenDerivative(H, t):
      # 𝐇(t) = d𝐏/dt, so ‖𝐇(t)‖ = ‖d𝐏/dt‖, the function to be integrated.
      D = BezierPoint(H, t)
      return VLength(D)

    H = BezierDerivative(Curve)
    Result = LGQIntegral25(Interval, LenDerivative, [H], [])

  return Result


#-------------------------------------------------------------------------------
# Bézier intersection functions
#-------------------------------------------------------------------------------


def UnitXToBezierIntersections(Curve, Tolerance=0.0):

  u'''Find intersections between (0, 0)–(1, 0) and a Bézier curve of any order.

  For arbitrary line segments, both the line and the curve will have to be
  scaled and translated so that the line maps to (0, 0)–(1, 0).

  The result is a list with zero or more intersection records. Each record
  is in the form (LParam, CParam) where LParam and CParam are the parameters
  for the line (0, 0)–(1, 0) and Curve respectively.

  '''

  #-----------------------------------------------------------------------------

  # Guard against an excessively small value of Tolerance. If it’s too
  # small, the subdivision will never end.

  MIN_REL_TOLERANCE = 1e-15
  MIN_ABS_TOLERANCE = 1e-315

  mUp = 0x08
  mDown = 0x04
  mLeft = 0x02
  mRight = 0x01

  #---------------------------------------------------------------------------

  def MinimumPermissibleTolerance(Points):

    u'''Determine a safe tolerance for the largest value found in points.'''

    return max(
      MIN_REL_TOLERANCE * max(VManhattan(P) for P in Points),
      MIN_ABS_TOLERANCE
    )

  #---------------------------------------------------------------------------

  def MayIntersect(Curve):

    u'''Quickly test if the curve has any chance of intersecting UnitX.'''

    Result = False
    ClipFlags = 0

    for P in Curve:
      if P[1] >= 0.0:
        ClipFlags |= mUp
      elif P[1] <= 0.0:
        ClipFlags |= mDown
      if ClipFlags == mUp | mDown:
        Result = True
        break

    if Result:

      ClipFlags = 0

      for P in Curve:
        if P[0] <= 0.0:
          ClipFlags |= mLeft
        elif P[0] >= 1.0:
          ClipFlags |= mRight
        else:
          Result = True
          break
        if ClipFlags == mLeft | mRight:
          Result = True
          break

    return Result

  #-----------------------------------------------------------------------------

  def UnitXToBezier_Recursive(Curve, Tolerance):

    u'''Find UnitX-to-Bézier intersections given validated arguments.

    Not only are the arguments taken to be valid, the trivial cases of
    a Bézier curve with an order of less than two is assumed to have
    already been excluded.

    The result is a list containing zero or more (LParam, CParam) pairs.

    '''

    #---------------------------------------------------------------------------

    def UnitXToCurveSegment(Curve, ParentStart, ParentEnd):

      u'''Find intersections expressed with parameters for the parent curve.

      The result is a list containing zero or more (LParam, CParam) pairs.
      LParam still refers to the line (0, 0)–(1, 0) but CParam is measured
      in terms of the Bézier curve of which Curve is a segment.

      '''

      Result = []
      Intercepts = UnitXToBezier_Recursive(Curve, Tolerance)

      for LParam, CParam in Intercepts:
        ParentCParam = (1.0 - CParam) * ParentStart + CParam * ParentEnd
        Result.append((LParam, ParentCParam))

      return Result

    #---------------------------------------------------------------------------

    Result = []

    # Here would be the obvious place to call the quick test function,
    # MayIntersect but it is instead called by this function’s parent
    # and for each of the subcurves below.

    Line2 = (Curve[0], Curve[-1])
    StraightIntercept = UnitXToLineIntersection(Line2)
    Deviance = ManhattanBezierDeviance(Curve)

    if Deviance < Tolerance:

      # The curve is close enough to being a line to be considered a line.

      if StraightIntercept is not None:
        Result.append(StraightIntercept)

    else:

      # The curve must be subdivided. Ideally the curve would be split
      # at a point such that the largest possible subcurve is easily
      # rejected by the quick test function MayIntersect.

      t = 0.5

      if StraightIntercept is not None:

        # The line connecting the endpoints of the curve, the curve’s
        # baseline is used as a guide to determining a good parameter
        # t at which the curve is to be be split. If the the baseline
        # parameter already calculated were used for t, it would likely
        # overshoot the true intersection point and cause only tiny
        # subcurves to be easily rejected, greatly slowing down the
        # convergence.
        #
        # The baseline parameter t0 is modified by a margin which varies
        # according to the deviance of the curve and the slope of the
        # curve’s baseline to the line (0, 0)–(1, 0). Grazing lines
        # require larger margins.

        try:

          t0 = StraightIntercept[1]
          D = VDiff(Line2[1], Line2[0])
          Shallowness = abs(D[0] / D[1])

          # A fudge factor partially accounts for the overestimation
          # of a control point’s ability to impart deviance. Occasional
          # overshoots are acceptable.

          AbsMargin = 0.4 * Deviance * (1.0 + Shallowness)
          Margin = AbsMargin / VManhattan(D)

          if t0 < 0.5:
            t = max(0.001, min(0.5, t0 + Margin))
          else:
            t = min(0.999, max(0.5, t0 - Margin))

        except (ZeroDivisionError, OverflowError):
          t = 0.5

      Curve1, Curve2 = SplitBezier(Curve, t)

      # The quick test is performed on the subcurves here rather than
      # at the start of this function in order to avoid the overhead of
      # calling the intermediate curve parameter-mapping function and
      # then this one again only to find the line obviously misses the
      # subcurve.

      if MayIntersect(Curve1):
        Result += UnitXToCurveSegment(Curve1, 0.0, t)
      if MayIntersect(Curve2):
        Result += UnitXToCurveSegment(Curve2, t, 1.0)

    return Result

  #-----------------------------------------------------------------------------

  Result = []
  Order = len(Curve) - 1

  # Handle the trivial cases.

  if Order < 2:

    if Order == 1:

      Intercept = UnitXToLineIntersection(Curve)

      if Intercept is not None:
        Result = [Intercept]

  else:

    ValTolerance = max(MinimumPermissibleTolerance(Curve), Tolerance)

    if MayIntersect(Curve):
      Result = UnitXToBezier_Recursive(Curve, ValTolerance)

  return Result


#-------------------------------------------------------------------------------


def LineToBezierIntersections(Line, Curve, Tolerance=0.0):

  u'''Find intersections between a line segment and a Bézier curve of any order.

  The result is a list with zero or more intersection records. Each record
  is in the form (Point, Tangent, LParam, CParam) where Point is the location
  of the intersection, Tangent is an unnormalised forward tangent to the curve
  and LParam and CParam are the parameters for Line and Curve respectively.

  '''

  Result = []
  Order = len(Curve) - 1

  # Handle the trivial cases.

  if Order < 2:
    if Order == 1:
      Intercept = LineToLineIntersection(Line, Curve)
      if Intercept is not None:
        Point, LParam, CParam = Intercept
        Tangent = VDiff(Line[1], Line[0])
        Result = [(Point, Tangent, LParam, CParam)]
    return Result

  # Now for the interesting cases.

  try:

    # Transform the curve so the line corresponds to the x-axis between
    # x=0 and x=1.

    Origin = Line[0]
    X = VDiff(Line[1], Origin)
    M, InvM = Affine2DMatrices(Origin, X)
    C = M.MultVectors(Curve)
    Scale = 1.0 / VLength(X)

    Intersections = UnitXToBezierIntersections(C, Scale * Tolerance)

    for LParam, CParam in Intersections:
      Point, Tangent = BezierPAT(Curve, CParam)
      Result.append((Point, Tangent, LParam, CParam))

  except (ZeroDivisionError, OverflowError):

    pass

  return Result


#-------------------------------------------------------------------------------
# Shape functions
#-------------------------------------------------------------------------------


def ShapeDim(Shape, n):

  u'''Return a Shape with vertices of n dimenions.

  Vertices set to None in Shape are left as None in the result.

  '''

  return [(PtType, None if P is None else VDim(P, n)) for PtType, P in Shape]


#-------------------------------------------------------------------------------


def ShapeFromVertices(Vertices, Order):

  u'''Create a poly-Bézier from a list of vertices.

  A poly-Bézier is a piecewise curve of Bézier curves. The poly-Bézier
  returned by this function are all of the same order except perhaps
  for the last one in the case of the number of vertices falling short.

  If Order is 1, a polyline is returned.

  '''

  Result = []

  LastIx = len(Vertices) - 1
  CPIx = 0

  Ix = 0

  while Ix < LastIx:

    PtType = Pt_Anchor if CPIx == 0 else Pt_Control
    Result.append((PtType, Vertices[Ix]))

    CPIx += 1
    if CPIx >= Order:
      CPIx = 0

    Ix += 1

  if LastIx >= 0:
    Result.append((Pt_Anchor, Vertices[LastIx]))

  return Result


#-------------------------------------------------------------------------------


def ShapePoints(Shape, ShapeRange=None):

  u'''Return the bare coordinates of a Shape or a part of one,

  The shape is defined as a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  ShapeRange, if set, selects only a portion of the Shape.

  '''

  RangeStart, RangeEnd = ValidatedRange(ShapeRange, len(Shape))
  Result = [Coords for Point, Coords in Shape[RangeStart:RangeEnd]]

  return Result


#-------------------------------------------------------------------------------


def ShapeSubpathRanges(Shape):

  u'''List the ranges of each subpaths in a Shape.

  The shape is defined as a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  A subpath is defined by a contiguous run of Shape points without any
  marked with Pt_Break. The ranges are suitable for use with the slice
  operator.

  '''

  Result = []
  SubpathStart = None

  for i, ShapePt in enumerate(Shape):

    PtType = ShapePt[0]

    if SubpathStart is None:
      if PtType != Pt_Break:
        SubpathStart = i
    else:
      if PtType == Pt_Break:
        Result.append((SubpathStart, i))
        SubpathStart = None

  if SubpathStart is not None:
    Result.append((SubpathStart, len(Shape)))

  return Result


#-------------------------------------------------------------------------------


def ShapeCurveRanges(Shape, ShapeRange=None):

  u'''List the ranges of each line segment or Bézier curve in a Shape.

  The Shape can be one contiguous piecewise curve or polyline or it
  can be several. A list of curve ranges is returned without regard
  to the Pt_Break items which are used to separate subpaths.

  ShapeRange, if set, selects only a portion of the Shape.

  '''

  Result = []

  RangeStart, RangeEnd = ValidatedRange(ShapeRange, len(Shape))

  SubpathStart = None
  CurveStart = None

  i = RangeStart

  while i < RangeEnd:

    PtType = Shape[i][0]

    if i + 1 < RangeEnd:
      IsEndOfSubpath = Shape[i + 1][0] == Pt_Break
    else:
      IsEndOfSubpath = True

    if SubpathStart is None:
      if PtType != Pt_Break:
        SubpathStart = i
        CurveStart = i
    else:
      if PtType == Pt_Anchor:
        Result.append((CurveStart, i + 1))
        if IsEndOfSubpath:
          CurveStart = None
        else:
          CurveStart = i
      elif PtType == Pt_Break:
        Result.append((CurveStart, i))
        SubpathStart = None
        CurveStart = None

    i += 1

  return Result


#-------------------------------------------------------------------------------


def ShapeLength(Shape):

  u'''Estimate the path length of a Shape.

  A Shape is defined by a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  The discontinuities implied by points tagged with Pt_Break do not
  contribute to the measured length.

  '''

  Result = 0.0

  Ranges = ShapeCurveRanges(Shape)

  for Range in Ranges:
    Curve = ShapePoints(Shape[Range[0]:Range[1]])
    Result += BezierLength(Curve)

  return Result


#-------------------------------------------------------------------------------


def LineToShapeIntersections(Line, Shape, Tolerance=0.0):

  u'''Find intersections between a line segment and a Shape.

  A Shape is defined by a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  The result is a list with zero or more intersection records. Each record
  is in the form (Point, Tangent, LParam, SubpathIx, CurveIx, CParam) where:

    Point is the location of the intersection;
    Tangent is an unnormalised (forward) tangent of the Shape at Point;
    LParam is the parameter for Line;
    SubpathIx is a zero-based index of subpath, a run (or loop) of curves;
    CurveIx is a zero-based index of a line or Bézier curve in a run; and
    CParam is the parameter for that line or curve.

  If no intersection is found, None is returned.

  '''

  Result = []

  try:

    # Transform the curve so that the line corresponds to the x-axis
    # between x = 0 and x = 1.

    Origin = Line[0]
    X = VDiff(Line[1], Origin)
    M, InvM = Affine2DMatrices(Origin, X)
    Scale = 1.0 / VLength(X)

    for SubpathIx, SPRange in enumerate(ShapeSubpathRanges(Shape)):

      for CurveIx, CRange in enumerate(ShapeCurveRanges(Shape, SPRange)):

        Curve = ShapePoints(Shape, CRange)
        TransformedCurve = M.MultVectors(Curve)
        Intersections = UnitXToBezierIntersections(
          TransformedCurve, Scale * Tolerance
        )

        for LParam, CParam in Intersections:
          Point, Tangent = BezierPAT(Curve, CParam)
          Result.append((Point, Tangent, LParam, SubpathIx, CurveIx, CParam))

  except (ZeroDivisionError, OverflowError):

    pass

  return Result


#-------------------------------------------------------------------------------


def TransformedShape(AM, Shape):

  u'''Return a Shape transformed by an affine matrix.

  The shape is defined as a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  '''

  Result = []

  for PtType, Coords in Shape:
    Result.append((PtType, AM.MultV(Coords)))

  return Result


#-------------------------------------------------------------------------------


def PiecewiseArc(Centre, Radius, AngleRange, NumPieces):

  u'''Return a Shape consisting of Bézier curves approximating a circular arc.

  The shape is defined as a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  '''

  Result = []

  StartAngle, EndAngle = AngleRange
  AngleStep = (EndAngle - StartAngle) / float(NumPieces)

  if EndAngle > StartAngle:
    h = CubicBezierArcHandleLength(AngleStep)
  else:
    h = -CubicBezierArcHandleLength(-AngleStep)

  SegStart = VPolToRect((Radius, StartAngle))
  Result.append((Pt_Anchor, VSum(Centre, SegStart)))

  for i in range(NumPieces):

    H1 = VSum(SegStart, VScaled(VPerp(SegStart), h))
    SegEndAngle = EndAngle - (NumPieces - 1 - i) * AngleStep
    SegEnd = VPolToRect((Radius, SegEndAngle))
    H2 = VSum(SegEnd, VScaled(VPerp(SegEnd), -h))
    SegStart = SegEnd

    Result.append((Pt_Control, VSum(Centre, H1)))
    Result.append((Pt_Control, VSum(Centre, H2)))
    Result.append((Pt_Anchor, VSum(Centre, SegEnd)))

  return Result


#-------------------------------------------------------------------------------
# Output formatting functions
#-------------------------------------------------------------------------------


def MaxDP(x, n):

  u'''Return as a string, x at a maximum of n decimal places.'''

  s = '%.*f' % (n, x)

  if '.' in s:
    while s[-1:] == '0':
      s = s[:-1]
    if s[-1:] == '.':
      s = s[:-1]

  return s


#-------------------------------------------------------------------------------


def GFListStr(L):

  u'''Return as a string, a list (or tuple) in general precision format.'''

  return '[' + (', '.join('%g' % (x) for x in L)) + ']'


#-------------------------------------------------------------------------------


def GFTupleStr(T):

  u'''Return as a string, a tuple (or list) in general precision format.'''

  if len(T) == 1:
    return '(%g,)' % (T[0])
  else:
    return '(' + (', '.join('%g' % (x) for x in T)) + ')'


#-------------------------------------------------------------------------------


def HTMLEscaped(Text):

  u'''Return text safe to use in HTML text and in quoted attributes values.

  Using unquoted values in attribute assignments where the values can be
  chosen by an untrusted agent can lead to a script injection attack unless
  the values are very heavily sanitised. It is good practice to always wrap
  attribute values in single or double quotes.

  '''

  EntityMap = {
    '&': '&amp;',
    '<': '&lt;',
    '>': '&gt;',
    '"': '&quot;',
    "'": '&apos',
    '`': '&#96;'
  }

  Result = ""

  for RawC in Text:
    SafeC = EntityMap[RawC] if RawC in EntityMap else RawC
    Result += SafeC

  return Result


#-------------------------------------------------------------------------------


def AttrMarkup(Attributes, PrependSpace):

  u'''Return HTML-style attribute markup from a dictionary.

  if PrependSpace is True and there is at least one attribute assignment
  generated, a space is added to the beginning of the result.

  Both an empty dictionary and None are valid values for Attributes.

  '''

  Result = ''

  if Attributes is not None:
    for Attr, Value in Attributes.items():
      if PrependSpace or (Result != ''):
        Result += ' '
      Result += HTMLEscaped(Attr) + '="' + HTMLEscaped(Value) + '"'

  return Result


#-------------------------------------------------------------------------------


def ProgressColourStr(Progress, Opacity=None):

  u'''Return an SVG or CSS colour string to indicate progress.'''

  Colours = [
    (1.0, 0.0, 0.0),
    (1.0, 1.0, 0.0),
    (0.0, 1.0, 0.0),
    (0.0, 1.0, 1.0),
    (0.0, 0.0, 1.0),
    (1.0, 0.0, 1.0)
  ]

  a = 4.25 * max(0.0, min(1.0, Progress))
  f = floor(a)
  t = a - f
  i = int(f)

  C0 = Colours[i % 6]
  C1 = Colours[(i + 1) % 6]

  # Surprisingly, working with linear light makes for more readily
  # distinguishable rainbow hues even though the purpose of nonlinear
  # framebuffer encoding is to provide a perceptually linear ramp of
  # brightnesses.

  # Since 0.0 and 1.0 are the same in linear and nonlinear form, no
  # conversion to linear is necessary.
  #
  # C0 = [pow(x, 2.2) for x in C0]
  # C1 = [pow(x, 2.2) for x in C1]

  C = VLerp(C0, C1, t)
  C = [pow(x, 1.0/2.2) for x in C]
  C = VScaled(C, 255.0)

  r = int(round(C[0]))
  g = int(round(C[1]))
  b = int(round(C[2]))

  if Opacity is None:
    OpacityStr = '1'
  else:
    a= max(0.0, min(1.0, Opacity))
    OpacityStr = MaxDP(a, 3)

  if OpacityStr == '1':
    Result = '#%.2x%.2x%.2x' % (r, g, b)
  else:
    Result = 'rgba(%d, %d, %d, %s)' % (r, g, b, OpacityStr)

  return Result


#-------------------------------------------------------------------------------
# SVG functions
#-------------------------------------------------------------------------------


def SVGStart(IT, Title=None, SVGAttributes=None):

  u'''Return a string for the beginning of an SVG file.

  IT is a tIndentTracker object, Title is used in the <title> tag and SVGAttr
  is a dictionary of attributes used to supplement or override the default
  attributes assigned to the <svg> tag.

  '''

  TitleToUse = '(Untitled)' if Title is None or Title == '' else Title

  Attr = {
    'width': '28cm',
    'height': '19cm',
    'viewBox': '0 0 28 19',
    'preserveAspectRatio': 'xMidYMid meet',
    'version': '1.1',
    'xmlns': 'http://www.w3.org/2000/svg',
    'xmlns:xlink': 'http://www.w3.org/1999/xlink'
   }

  Attr = MergedDictionary(Attr, SVGAttributes)

  Result = IT(
    '<?xml version="1.0" standalone="no"?>',
    '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"',
    IT.IndentUnitStr + '"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">',
    '<svg' + AttrMarkup(Attr, True) + '>',
    '',
    '<title>' + HTMLEscaped(TitleToUse) + '</title>',
    ''
  )

  #IT.StepIn()

  return Result


#-------------------------------------------------------------------------------


def SVGEnd(IT):

  u'''Return a string for the end of an SVG file.'''

  #IT.StepOut()

  Result = IT('', '</svg>')

  return Result


#-------------------------------------------------------------------------------


def SVGPathDataSegments(Shape):

  u'''Return a list of SVG path commands from a Shape.

  The result is ready for pretty-printing and stuffing into the
  “d” attribute of a path tag.

  SVG path commands are very much like Postscript commands.

  '''

  def SVGNStr(n):
    u'''Return a string representation of a number, fit for an SVG.'''
    s = MaxDP(n, 6)
    return s

  def SVGVStr(V):
    u'''Return a string representation of a 2D vector, fit for an SVG.'''
    return SVGNStr(V[0]) + ',' + SVGNStr(V[1])

  Result = []

  FirstSegAnchor = None
  LastAnchor = None
  LastSegCP = None
  LastSegWasQuadratic = False

  Segment = []

  for i, ShapePt in enumerate(Shape):

    PtType, Coords = ShapePt

    if PtType == Pt_Anchor:

      if i + 1 < len(Shape):
        IsTerminal = Shape[i + 1][0] == Pt_Break
      else:
        IsTerminal = True

      if LastAnchor is None:

        if not IsTerminal:

          Result.append('M ' + SVGVStr(Coords))

          FirstSegAnchor = Coords
          LastAnchor = Coords
          LastSegCP = None

      else:

        if len(Segment) > 0:

          IsSmooth = False
          IsQuadratic = len(Segment) == 1
          IsCubic = len(Segment) == 2

          if (LastAnchor is not None) and (LastSegCP is not None):
            MirrorCP = VSum(LastAnchor, VDiff(LastAnchor, LastSegCP))
            if LastSegWasQuadratic == IsQuadratic:
              IsSmooth = SVGVStr(Segment[0]) == SVGVStr(MirrorCP)

          if IsQuadratic:
            if IsSmooth:
              CmdStr = 'T'
            else:
              CmdStr = 'Q'
          elif IsCubic:
            if IsSmooth:
              CmdStr = 'S'
            else:
              CmdStr = 'C'
          else:
            raise Error(
              u'SVG requires a Bézier curve to be of the order ' +
                'one, two or three (linear, quadratic or cubic).'
            )

          LastSegWasQuadratic = IsQuadratic
          LastAnchor = Coords
          LastSegCP = Segment[-1]
          Segment.append(Coords)

          if IsSmooth:
            PointsToOutput = Segment[1:]
          else:
            PointsToOutput = Segment[:]

          for V in PointsToOutput:
            CmdStr = CmdStr + ' ' + SVGVStr(V)

          Result.append(CmdStr)
          Segment = []

        else:

          XYStr = SVGVStr(Coords)

          if IsTerminal and XYStr == SVGVStr(FirstSegAnchor):

            Result.append('Z')

            FirstSegAnchor = None
            LastAnchor = None
            LastSegCP = None

          else:

            XStr = SVGNStr(Coords[0])
            YStr = SVGNStr(Coords[1])

            if LastAnchor is not None:
              IsH = YStr == SVGNStr(LastAnchor[1])
              IsV = XStr == SVGNStr(LastAnchor[0])
            else:
              IsH = False
              IsV = False

            if IsH:
              if not IsV:
                Result.append('H ' + XStr)
            else:
              if IsV:
                Result.append('V ' + YStr)
              else:
                Result.append('L ' + XYStr)

            LastAnchor = Coords
            LastSegCP = None

    elif PtType == Pt_Control:

      if LastAnchor is None:
        raise Error('A curve may not start with a control point.')

      Segment.append(Coords)

    elif PtType == Pt_Break:

      if len(Segment) > 0:
        raise Error('A Break command must not occur within a curve.')

      FirstSegAnchor = None
      LastAnchor = None
      LastSegCP = None

    else:

      raise Error('Unhandled point type %s.' % (str(PtType)))

  if len(Segment) > 0:
    raise Error('No anchor point was given for the last curve.')

  return Result


#-------------------------------------------------------------------------------


def SVGPath(IT, Shape, Attributes=None):

  u'''Return SVG markup for a Shape.

  A Shape is defined as a list of (PtType, Coords) tuples which mark
  anchors, control points and breaks.

  Attributes is a dictionary for writing the attribute markup for
  the SVG path tag. Common attributes to set include fill, fill-rule,
  stroke, stroke-width, stroke-linejoin and stroke-linecap. Both an
  empty dictionary and None are valid values for Attributes.

  '''

  Result = ''
  FirstLinePart = '<path' + AttrMarkup(Attributes, True) + ' d="'

  # Defer writing the beginning of the path markup.
  IT.StepIn()

  InnerLines = []
  AvailTextColumns = max(0, 78 - len(IT.LIStr))

  CmdSep = '  '
  LineStr = ''
  Commands = SVGPathDataSegments(Shape)

  for Cmd in Commands:
    if LineStr != '':
      RemColumns = AvailTextColumns - len(LineStr) - len(CmdSep) - len(Cmd)
      if RemColumns < 0:
        InnerLines.append(LineStr)
        LineStr = ''
    if LineStr != '':
      LineStr += CmdSep
    LineStr += Cmd
  if LineStr != '':
    InnerLines.append(LineStr)

  InnerText = IT(*InnerLines)
  IT.StepOut()

  if len(InnerLines) > 0:
    Result += IT(FirstLinePart)
    Result += InnerText
    Result += IT('"/>')
  else:
    Result += IT(FirstLinePart + '"/>')

  return Result


#-------------------------------------------------------------------------------


def SVGText(IT, Position, Text, Attributes=None):

  u'''Return SVG markup for a line of text.

  Several lines of text with similar attributes can have their attributes
  inherited from those of a containing group.

  Attributes is a dictionary for writing the attribute markup for
  the <text> tag. Common attributes to set include font-family,
  font-style, font-variant, font-size, font-weight, kerning,
  letter-spacing, word-spacing, text-decoration, text-anchor, fill,
  stroke and stroke-width. Both an empty dictionary and None are
  valid values for Attributes.

  '''

  BadKeys = ['x', 'X', 'y', 'Y']

  A = Attributes

  if Position is not None:

    PosStr = (
      ' x="' + MaxDP(Position[0], 5) + '" ' +
      'y="' + MaxDP(Position[1], 5) + '"'
    )

    if A is not None:
      for BadKey in BadKeys:
        if BadKey in A:
          if A is Attributes:
            A = dict(Attributes)
          del A[BadKey]

  else:

    PosStr = ''

  Result = IT(
    '<text' + PosStr + AttrMarkup(A, True) + '>' +
    HTMLEscaped(Text) +
    '</text>'
  )

  return Result


#-------------------------------------------------------------------------------


def SVGGroup(IT, Attributes=None):

  u'''Return markup for the beginning of an SVG group.

  A group allows objects to easily share properties in a manner to
  the group function of a desktop publishing package. This allows
  the group to be transformed or styled as one unit.

  Attributes is a dictionary for writing the attribute markup for
  the <g> tag. Common attributes to set include fill, fill-rule,
  stroke, stroke-width, stroke-linejoin and stroke-linecap. Both
  an empty dictionary and None are valid values for Attributes.

  '''

  Result = IT('<g' + AttrMarkup(Attributes, True) + '>')
  IT.StepIn()

  return Result


#-------------------------------------------------------------------------------


def SVGGroupEnd(IT):

  u'''Return markup for the end of an SVG group.'''

  IT.StepOut()
  Result = IT('</g>')

  return Result


#-------------------------------------------------------------------------------


def SVGGrid(IT, Grid):

  u'''Return transformed SVG group markup to facilitate graph plotting.

  Grid is a dictionary with the keys:

    'CanvasMinima': (left, top)
    'CanvasMaxima': (right, bottom)
    'RangeMinima': (x0, y0)
    'RangeMaxima': (x1, y1)
    'YIsUp': True|False
    'Transpose': True|False
    'SquareAlignment': 'Corner'|'Centre'
    'DrawGrid': True|False
    'DrawUnitAxes': True|False
    'GridLineAttributes': SVG Attributes for grid lines
    'GeneralAttributes': SVG Attributes for the group tag

  YIsUp assumes the current reference frame resembles the frame
  SVG begins with: <x> is right and <y> is down.

  If SquareAlignment is “Corner” or is unspecified, integer
  coordinates lie on the intersections of grid lines and
  RangeMinima and RangeMaxima are inclusive. If SquareAlignment
  is “Centre” or “Center”, integer coordinates lie in the centres
  of grid squares, RangeMinima is inclusive and RangeMaxima is
  exclusive in regard to the square indices.

  '''

  #-----------------------------------------------------------------------------

  # Shorthand

  A = Pt_Anchor
  C = Pt_Control
  B = (Pt_Break, None)

  #-----------------------------------------------------------------------------

  def Field(Name, Default):

    u'''Return a value of Grid given a key name or return a default value.'''

    return Grid[Name] if Name in Grid else Default

  #-----------------------------------------------------------------------------

  def DictWithDefaults(ContainerDict, DictName, Defaults):

    u'''Allow an optional dictionary to be merged over some defaults.'''

    Result = Defaults

    if DictName in ContainerDict:
      Result = MergedDictionary(Defaults, ContainerDict[DictName])

    return Result

  #-----------------------------------------------------------------------------

  def T(V):

    u'''Return a 2D vector with its ordinals swapped.'''

    return (V[1], V[0])

  #-----------------------------------------------------------------------------

  Result = ''

  Transposed = Field('Transpose', False)

  CanvasMinima = tuple(Grid['CanvasMinima'])
  CanvasMaxima = tuple(Grid['CanvasMaxima'])
  CanvasCentre = VLerp(CanvasMinima, CanvasMaxima, 0.5)
  CanvasSpan = VDiff(CanvasMaxima, CanvasMinima)

  if Transposed:
    TCanvasSpan = T(CanvasSpan)
  else:
    TCanvasSpan = CanvasSpan

  RangeMinima = tuple(Grid['RangeMinima'])
  RangeMaxima = tuple(Grid['RangeMaxima'])
  RangeCentre = VLerp(RangeMinima, RangeMaxima, 0.5)
  RangeSpan = VDiff(RangeMaxima, RangeMinima)

  s = min(TCanvasSpan[0] / RangeSpan[0], TCanvasSpan[1] / RangeSpan[1])
  Scale = (s, s)
  ScaleStr = str(Scale[0]) + ', ' + str(Scale[1])

  AddressSquareCentres = Field('SquareAlignment', 'Corner') != 'Corner'

  if AddressSquareCentres:
    h = 0.5 * Scale[0]
  else:
    h = 0.0
  GridOffset = (h, h)

  if Field('YIsUp', False):
    GridOffset = (GridOffset[0], -GridOffset[1])
    Scale = (Scale[0], -Scale[1])
    ScaleStr = str(Scale[0]) + ', ' + str(Scale[1])

  StrokeWidth = max(0.0075, min(0.02, (0.15 / Scale[0])))

  if Transposed:
    Origin = VDiff(
      VSum(CanvasCentre, T(GridOffset)),
      T(VSchur(Scale, RangeCentre))
    )
  else:
    Origin = VDiff(VSum(CanvasCentre, GridOffset), VSchur(Scale, RangeCentre))
  OriginStr = str(Origin[0]) + ', ' + str(Origin[1])

  GeneralAttributes = DictWithDefaults(
    Grid, 'GeneralAttributes', {
      'stroke': 'rgba(0, 192, 255, 0.5)',
      'fill': 'none',
      'stroke-linecap': 'butt',
      'stroke-width': '%g' % (StrokeWidth)
  })

  XFormList = []

  if Transposed:
    XFormList.append('matrix(0, %s, 0, %s)' % (ScaleStr, OriginStr))
  else:
    XFormList = []
    if Origin != (0, 0):
      XFormList.append('translate(' + OriginStr + ')')
    if Scale != (1, 1):
      XFormList.append('scale(' + ScaleStr + ')')

  if len(XFormList) > 0:
    GeneralAttributes['transform'] = ' '.join(XFormList)

  GridLineAttributes = DictWithDefaults(
    Grid, 'GridLineAttributes', {
      'fill': 'none',
      'stroke-linecap': 'square',
      'stroke-width': '%g' % (max(0.0075, min(0.02, (0.1 / Scale[0]))))
  })

  Result += SVGGroup(IT, GeneralAttributes)

  if Field('DrawGrid', True):

    Result += IT('<!-- Grid lines -->')
    Result += SVGGroup(IT, GridLineAttributes)

    if AddressSquareCentres:
      GridOffset = (-0.5, -0.5)
    else:
      GridOffset = (0.0, 0.0)

    AM = AffineMtxTS(GridOffset, 1.0)

    Result += IT('<!-- Grid lines parallel to the y axis -->')
    S = []
    for x in range(RangeMinima[0], RangeMaxima[0] + 1):
      S += [(A, (x, RangeMinima[1])), (A, (x, RangeMaxima[1])), B]
    Result += SVGPath(IT, TransformedShape(AM, S))

    Result += IT('<!-- Grid lines parallel to the x axis -->')
    S = []
    for y in range(RangeMinima[1], RangeMaxima[1] + 1):
      S += [(A, (RangeMinima[0], y)), (A, (RangeMaxima[0], y)), B]
    Result += SVGPath(IT, TransformedShape(AM, S))

    if AddressSquareCentres:
      Result += IT('<!-- Grid square centres -->')
      S = []
      h = 0.125
      for x in range(RangeMinima[0], RangeMaxima[0]):
        for y in range(RangeMinima[1], RangeMaxima[1]):
          S += [(A, (x - h, y)), (A, (x + h, y)), B]
          S += [(A, (x, y - h)), (A, (x, y + h)), B]
      Result += SVGPath(IT, S, GridLineAttributes)

    Result += SVGGroupEnd(IT)

  if Field('DrawUnitAxes', False):
    Result += IT('<!-- Unit axes -->')
    Result += SVGGroup(IT, {'stroke': 'none'})
    h = 2.0 * (0.5 * StrokeWidth)
    ahx = 1.0 - 8.0 * h
    S = [
      (A, (-h, -h)), (A, (0.5 * h, h)), (A, (ahx, h)), (A, (ahx, 3.0 * h)),
      (A, (1.0, 0.0)), (A, (ahx, -3.0 * h)), (A, (ahx, -h)),
      (A, (-h, -h))
    ]
    Result += IT('<!-- Origin -->')
    Result += IT('<circle cx="0" cy="r" r="0.1" ' +
      'fill="none" stroke="#777" stroke-width="%g"/>' % (2.0 * h))
    Result += IT('<!-- x -->')
    Result += SVGPath(IT, S, {'fill': '#e00'})
    S[1] = (A, (h, h))
    S = TransformedShape(AffineMtxTRS2D((0.0, 0.0), 0.5 * pi, (1.0, -1.0)), S)
    Result += IT('<!-- y -->')
    Result += SVGPath(IT, S, {'fill': '#0c0'})
    Result += SVGGroupEnd(IT)

  return Result


#-------------------------------------------------------------------------------
# End
#-------------------------------------------------------------------------------