technical_drawings_extraction/venv/lib/python3.7/site-packages/ezdxf/math/bezier.py

# Purpose: general bezier curve
# Created: 26.03.2010
# Copyright (c) 2010-2018 Manfred Moitzi
# License: MIT License
from typing import TYPE_CHECKING, List, Iterable, Tuple, Dict
from ezdxf.math.vector import Vector

if TYPE_CHECKING:
    from ezdxf.eztypes import Vertex

"""

Bezier curves
=============

https://www.cl.cam.ac.uk/teaching/2000/AGraphHCI/SMEG/node3.html

A Bezier curve is a weighted sum of n+1 control points,  P0, P1, ..., Pn, where the weights are the Bernstein 
polynomials. 

The Bezier curve of order n+1 (degree n) has n+1 control points. These are the first three orders of Bezier curve 
definitions. 

(75) linear P(t) = (1-t)*P0 + t*P1
(76) quadratic P(t) = (1-t)^2*P0 + 2*(t-1)*t*P1 + t^2*P2
(77) cubic P(t) = (1-t)^3*P0 + 3*(t-1)^2*t*P1 + 3*(t-1)*t^2*P2 + t^3*P3

Ways of thinking about Bezier curves
------------------------------------

There are several useful ways in which you can think about Bezier curves. Here are the ones that I use.

Linear interpolation
~~~~~~~~~~~~~~~~~~~~

Equation (75) is obviously a linear interpolation between two points. Equation (76) can be rewritten as a linear 
interpolation between linear interpolations between points.

Weighted average
~~~~~~~~~~~~~~~~

A Bezier curve can be seen as a weighted average of all of its control points. Because all of the weights are 
positive, and because the weights sum to one, the Bezier curve is guaranteed to lie within the convex hull of its 
control points.
    
Refinement of the control polygon
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

A Bezier curve can be seen as some sort of refinement of the polygon made by connecting its control points in order. 
The Bezier curve starts and ends at the two end points and its shape is determined by the relative positions of the 
n-1 other control points, although it will generally not pass through these other control points. The tangent vectors 
at the start and end of the curve pass through the end point and the immediately adjacent point.

Continuity
----------

You should note that each Bezier curve is independent of any other Bezier curve. If we wish two Bezier curves to join 
with any type of continuity, then we must explicitly position the control points of the second curve so that they bear 
the appropriate relationship with the control points in the first curve.

Any Bezier curve is infinitely differentiable within itself, and is therefore continuous to any degree.

"""


class Bezier:
    """
    A general Bezier curve.

    Accepts 2d points as definition points, but output ist always 3d (z-axis is 0).

    """

    def __init__(self, defpoints: Iterable['Vertex']):
        self._defpoints = [Vector(p) for p in defpoints]  # type: List[Vector]

    @property
    def control_points(self) -> List[Vector]:
        return self._defpoints

    def approximate(self, segments: int = 20) -> Iterable[Vector]:
        step = 1.0 / float(segments)
        for point_index in range(segments + 1):
            yield self.point(point_index * step)

    def point(self, t: float) -> Vector:
        """
        Returns point at BezierCurve(t) as tuple (x, y, z)

        Args:
            t: parameter in range [0, 1]

        Returns: Vector(x, y, z)

        """
        if t < 0. or t > 1.:
            raise ValueError('parameter t in range [0, 1]')
        if (1.0 - t) < 5e-6:
            t = 1.0
        point = [0., 0., 0.]
        defpoints = self._defpoints
        len_defpoints = len(defpoints)

        for axis in (0, 1, 2):
            for i in range(len_defpoints):
                bsf = bernstein_basis(len_defpoints - 1, i, t)
                point[axis] += bsf * defpoints[i][axis]
        return Vector(point)


class DBezier(Bezier):
    """
    Calculate the Points and Derivative of a Bezier curve.

    """

    def point(self, t: float) -> Tuple[Vector, Vector, Vector]:
        """
        Returns (point, derivative1, derivative2) at BezierCurve(t)

        Args:
            t: parameter in range [0, 1]

        Returns: (point, derivative1, derivative2)
            point -- Vector(x, y, z)
            derivative1 -- Vector(x, y, z)
            derivative2 -- Vector(x, y, z)

        """
        if t < 0. or t > 1.:
            raise ValueError('parameter t in range [0, 1]')

        if (1.0 - t) < 5e-6:
            t = 1.0
        defpoints = self._defpoints
        npts = len(defpoints)
        npts0 = npts - 1
        point = [0., 0., 0.]
        d1 = [0., 0., 0.]
        d2 = [0., 0., 0.]
        for axis in (0, 1, 2):
            if t == 0.0:
                d1[axis] = npts0 * (defpoints[1][axis] - defpoints[0][axis])
                d2[axis] = npts0 * (npts0 - 1) * (defpoints[0][axis] - 2. * defpoints[1][axis] + defpoints[2][axis])
            for i in range(len(defpoints)):
                tempbasis = bernstein_basis(npts0, i, t)
                point[axis] += tempbasis * defpoints[i][axis]
                if 0.0 < t < 1.0:
                    d1[axis] += ((i - npts0 * t) / (t * (1. - t))) * tempbasis * defpoints[i][axis]
                    temp1 = (i - npts0 * t) ** 2
                    temp2 = temp1 - npts0 * t ** 2 - i * (1. - 2. * t)
                    d2[axis] += (temp2 / (t ** 2 * (1. - t) ** 2)) * tempbasis * defpoints[i][axis]
                if t == 1.0:
                    d1[axis] = npts0 * (defpoints[npts0][axis] - defpoints[npts0 - 1][axis])
                    d2[axis] = npts0 * (npts0 - 1) * (defpoints[npts0][axis] - 2 * defpoints[npts0 - 1][axis] +
                                                      defpoints[npts0 - 2][axis])
        return Vector(point), Vector(d1), Vector(d2)


def bernstein_basis(n: int, i: int, t: float) -> float:
    # handle the special cases to avoid domain problem with pow
    if t == 0.0 and i == 0:
        ti = 1.0
    else:
        ti = pow(t, i)
    if n == i and t == 1.0:
        tni = 1.0
    else:
        tni = pow((1.0 - t), (n - i))
    Ni = factorial(n) / (factorial(i) * factorial(n - i))
    return Ni * ti * tni


class _Factorial:
    _values = {0: 1.0}  # type: Dict[int, float]

    def __init__(self, maxvalue: int = 33):
        value = 1.
        for i in range(1, maxvalue):
            value *= i
            self._values[i] = value

    def get(self, value: int) -> float:
        value = int(value)
        try:
            return self._values[value]
        except KeyError:
            result = self.get(value - 1) * value
            self._values[value] = result
            return result


_factorial = _Factorial()
factorial = _factorial.get