Add booleanOperations library to scripts/lib/.

This library will be used for overlap removal. We include it here for now because it doesn't have a setup.py.

7 files changed, 1513 insertions, 0 deletions

diff --git a/scripts/lib/booleanOperations/__init__.py b/scripts/lib/booleanOperations/__init__.py
new file mode 100644
index 0000000..8b49517
--- /dev/null
+++ b/scripts/lib/booleanOperations/__init__.py
@@ -0,0 +1 @@
+from booleanOperationManager import BooleanOperationManager
\ No newline at end of file
diff --git a/scripts/lib/booleanOperations/booleanGlyph.py b/scripts/lib/booleanOperations/booleanGlyph.py
new file mode 100644
index 0000000..70d175d
--- /dev/null
+++ b/scripts/lib/booleanOperations/booleanGlyph.py
@@ -0,0 +1,225 @@
+import weakref
+from copy import deepcopy
+
+from robofab.pens.pointPen import AbstractPointPen
+from defcon.pens.clockwiseTestPointPen import ClockwiseTestPointPen
+
+from booleanOperationManager import BooleanOperationManager
+
+manager = BooleanOperationManager()
+
+class BooleanGlyphDataPointPen(AbstractPointPen):
+
+    def __init__(self, glyph):
+        self._glyph = glyph
+        self._points = []
+        self.copyContourData = True
+
+    def _flushContour(self):
+        points = self._points
+        if len(points) == 1 and points[0][0] == "move":
+            self._glyph.anchors.append((pt, name))
+        elif self.copyContourData:
+            contour = self._glyph.contourClass()
+            contour._points = points
+            self._glyph.contours.append(contour)
+
+    def beginPath(self):
+        self._points = []
+
+    def addPoint(self, pt, segmentType=None, smooth=False, name=None, **kwargs):
+        self._points.append((segmentType, pt, smooth, name))
+
+    def endPath(self):
+        self._flushContour()
+
+    def addComponent(self, baseGlyphName, transformation):
+        self._glyph.components.append((baseGlyphName, transformation))
+
+class BooleanContour(object):
+
+    """
+    Contour like object.
+    """
+
+    def __init__(self):
+        self._points = []
+        self._clockwise = None
+        self._bounds = None
+
+    def __len__(self):
+        return len(self._points)
+
+    ## shallow contour API
+
+    def draw(self, pen):
+        from robofab.pens.adapterPens import PointToSegmentPen
+        pointPen = PointToSegmentPen(pen)
+        self.drawPoints(pointPen)
+
+    def drawPoints(self, pointPen):
+        pointPen.beginPath()
+        for segmentType, pt, smooth, name in self._points:
+            pointPen.addPoint(pt=pt, segmentType=segmentType, smooth=smooth, name=name)
+        pointPen.endPath()
+
+    def _get_clockwise(self):
+        if self._clockwise is None:
+            pointPen = ClockwiseTestPointPen()
+            self.drawPoints(pointPen)
+            self._clockwiseCache = pointPen.getIsClockwise()
+        return self._clockwise
+
+    clockwise = property(_get_clockwise)
+
+    def _get_bounds(self):
+        if self._bounds is None:
+            from robofab.pens.boundsPen import BoundsPen
+            pen = BoundsPen(None)
+            self.draw(pen)
+            self._boundsCache = pen.bounds
+        return self._bounds
+
+    bounds = property(_get_bounds)
+
+class BooleanGlyph(object):
+    
+    """
+    Glyph like object handling boolean operations.
+    
+    union:
+        result = BooleanGlyph(glyph).union(BooleanGlyph(glyph2))
+        result = BooleanGlyph(glyph) | BooleanGlyph(glyph2)
+    
+    difference:
+        result = BooleanGlyph(glyph).difference(BooleanGlyph(glyph2))
+        result = BooleanGlyph(glyph) % BooleanGlyph(glyph2)
+    
+    intersection:
+        result = BooleanGlyph(glyph).intersection(BooleanGlyph(glyph2))
+        result = BooleanGlyph(glyph) & BooleanGlyph(glyph2)
+    
+    xor:
+        result = BooleanGlyph(glyph).xor(BooleanGlyph(glyph2))
+        result = BooleanGlyph(glyph) ^ BooleanGlyph(glyph2)
+    
+    """
+    
+    contourClass = BooleanContour
+
+    def __init__(self, glyph=None, copyContourData=True):
+        self.contours = []
+        self.components = []
+        self.anchors = []
+        
+        self.name = None
+        self.unicodes = None
+        self.width = None
+        self.lib = {}
+        self.note = None
+
+        if glyph:
+            pen = self.getPointPen()
+            pen.copyContourData = copyContourData
+            glyph.drawPoints(pen)
+            
+            self.name = glyph.name
+            self.unicodes = glyph.unicodes
+            self.width = glyph.width
+            self.lib = deepcopy(glyph.lib)
+            self.note = glyph.note
+
+            if not isinstance(glyph, self.__class__):
+                self.getSourceGlyph = weakref.ref(glyph)
+    
+    def __repr__(self):
+        return "<BooleanGlyph %s>" % self.name
+
+    def __len__(self):
+        return len(self.contours)
+
+    def __getitem__(self, index):
+        return self.contours[index]
+
+    def getSourceGlyph(self):
+        return None
+    
+    ## shalllow glyph API
+
+    def draw(self, pen):
+        from robofab.pens.adapterPens import PointToSegmentPen
+        pointPen = PointToSegmentPen(pen)
+        self.drawPoints(pointPen)
+    
+    def drawPoints(self, pointPen):
+        for contour in self.contours:
+            contour.drawPoints(pointPen)
+        for baseName, transformation in self.components:
+            pointPen.addComponent(baseName, transformation)
+        for pt, name in self.anchors:
+            pointPen.beginPath()
+            pointPen.addPoint(pt=pt, segmentType="move", smooth=False, name=name)
+            pointPen.endPath()
+    
+    def getPen(self):
+        from robofab.pens.adapterPens import SegmentToPointPen
+        return SegmentToPointPen(self.getPointPen())
+
+    def getPointPen(self):
+        from defcon.pens.glyphObjectPointPen import GlyphObjectPointPen
+        return BooleanGlyphDataPointPen(self)
+
+    ## boolean operations
+
+    def _booleanMath(self, operation, other):
+        if not isinstance(other, self.__class__):
+            other = self.__class__(other)
+        destination = self.__class__(self, copyContourData=False)
+        func = getattr(manager, operation)
+
+        if operation == "union":
+            contours = self.contours
+            if other is not None:
+                contours += other.contours
+            func(contours, destination.getPointPen())    
+        else:
+            subjectContours = self.contours
+            clipContours = other.contours
+            func(subjectContours, clipContours, destination.getPointPen())
+        return destination
+    
+    def __or__(self, other):
+        return self.union(other)
+    
+    __ror__ = __ior__ = __or__
+
+    def __mod__(self, other):
+        return self.difference(other)
+
+    __rmod__ = __imod__ = __mod__
+
+    def __and__(self, other):
+        return self.intersection(other)
+    
+    __rand__ = __iand__ = __and__
+
+    def __xor__(self, other):
+        return self.xor(other)
+
+    __rxor__ = __ixor__ = __xor__
+
+    def union(self, other):
+        return self._booleanMath("union", other)
+
+    def difference(self, other):
+        return self._booleanMath("difference", other)
+
+    def intersection(self, other):
+        return self._booleanMath("intersection", other)
+
+    def xor(self, other):
+        return self._booleanMath("xor", other)
+
+    def removeOverlap(self):
+        return self._booleanMath("union", None)
+
diff --git a/scripts/lib/booleanOperations/booleanOperationManager.py b/scripts/lib/booleanOperations/booleanOperationManager.py
new file mode 100644
index 0000000..84fc8b8
--- /dev/null
+++ b/scripts/lib/booleanOperations/booleanOperationManager.py
@@ -0,0 +1,88 @@
+from fontTools.pens.basePen import BasePen
+from flatten import InputContour, OutputContour
+import pyClipper
+
+
+"""
+General Suggestions:
+- Contours should only be sent here if they actually overlap.
+  This can be checked easily using contour bounds.
+- Only perform operations on closed contours.
+- contours must have an on curve point
+- some kind of a log
+"""
+
+
+class BooleanOperationManager(object):
+
+    def _performOperation(self, operation, subjectContours, clipContours, outPen):
+        # prep the contours
+        subjectInputContours = [InputContour(contour) for contour in subjectContours if contour and len(contour) > 1]
+        clipInputContours = [InputContour(contour) for contour in clipContours if contour and len(contour) > 1]
+        inputContours = subjectInputContours + clipInputContours
+
+        resultContours = pyClipper.clipExecute([subjectInputContour.originalFlat for subjectInputContour in subjectInputContours], 
+                                               [clipInputContour.originalFlat for clipInputContour in clipInputContours], 
+                                               operation, subjectFillType="noneZero", clipFillType="noneZero")
+        # convert to output contours
+        outputContours = [OutputContour(contour) for contour in resultContours]
+        # re-curve entire contour
+        for inputContour in inputContours:
+            for outputContour in outputContours:
+                if outputContour.final:
+                    continue
+                if outputContour.reCurveFromEntireInputContour(inputContour):
+                    # the input is expired if a match was made,
+                    # so stop passing it to the outputs
+                    break
+        # re-curve segments
+        for inputContour in inputContours:
+            # skip contours that were comppletely used in the previous step
+            if inputContour.used:
+                continue
+            # XXX this could be expensive if an input becomes completely used
+            # it doesn't stop from being passed to the output
+            for outputContour in outputContours:
+                outputContour.reCurveFromInputContourSegments(inputContour)
+        # curve fit
+        for outputContour in outputContours:
+            outputContour.reCurveSubSegments(inputContours)
+        # output the results
+        for outputContour in outputContours:
+            outputContour.drawPoints(outPen)
+        return outputContours
+
+    def union(self, contours, outPen):
+        return self._performOperation("union", contours, [], outPen)
+    
+    def difference(self, subjectContours, clipContours, outPen):
+        return self._performOperation("difference", subjectContours, clipContours, outPen)
+    
+    def intersection(self, subjectContours, clipContours, outPen):
+        return self._performOperation("intersection", subjectContours, clipContours, outPen)
+    
+    def xor(self, subjectContours, clipContours, outPen):
+        return self._performOperation("xor", subjectContours, clipContours, outPen)
+
+    def getIntersections(self, contours):
+        from flatten import _scalePoints, inverseClipperScale
+        # prep the contours
+        inputContours = [InputContour(contour) for contour in contours if contour and len(contour) > 1]
+
+        inputFlatPoints = set()
+        for contour in inputContours:
+            inputFlatPoints.update(contour.originalFlat)
+        
+        resultContours = pyClipper.clipExecute([inputContour.originalFlat for inputContour in inputContours], 
+                                               [], 
+                                               "union", subjectFillType="noneZero", clipFillType="noneZero")
+
+        resultFlatPoints = set()
+        for contour in resultContours:
+            resultFlatPoints.update(contour)
+        
+        intersections = resultFlatPoints - inputFlatPoints
+        return _scalePoints(intersections, inverseClipperScale)
+
+
+    
\ No newline at end of file
diff --git a/scripts/lib/booleanOperations/flatten.py b/scripts/lib/booleanOperations/flatten.py
new file mode 100644
index 0000000..58b6fdb
--- /dev/null
+++ b/scripts/lib/booleanOperations/flatten.py
@@ -0,0 +1,1199 @@
+import math
+from fontTools.pens.basePen import BasePen
+from fontTools.misc import bezierTools
+from fontTools.pens.basePen import decomposeQuadraticSegment
+from robofab.pens.reverseContourPointPen import ReverseContourPointPen
+from robofab.pens.adapterPens import PointToSegmentPen
+
+"""
+To Do:
+- the stuff listed below
+- need to know what kind of curves should be used for
+  curve fit--curve or qcurve
+- false curves and duplicate points need to be filtered early on
+
+notes:
+- the flattened segments *must* be cyclical.
+  if they aren't, matching is almost impossible.
+
+
+optimization ideas:
+- the flattening of the output segment in the full contour
+  matching is probably expensive.
+- there should be a way to flag an input contour as
+  entirely used so that it isn't tried and tried and
+  tried for segment matches.
+- do a faster test when matching segments: when a end
+  match is found, jump back input length and grab the
+  output segment. test for match with the input.
+- cache input contour objects. matching these to incoming
+  will be a little difficult because of point names and
+  identifiers. alternatively, deal with those after the fact.
+- some tests on input before conversion to input objects
+  could yield significant speedups. would need to check
+  each contour for self intersection and each
+  non-self-intersectingcontour for collision with other
+  contours. and contours that don't have a hit could be
+  skipped. this cound be done roughly with bounds.
+  this should probably be done by extenal callers.
+- set a proper starting points of the output segments based on known points
+  known points are: 
+    input oncurve points
+    if nothing found intersection points (only use this is in the final curve fitting stage)
+
+test cases:
+- untouched contour: make clockwise and counter-clockwise tests
+  of the same contour
+"""
+epsilon = 1e-8
+
+# factors for transferring coordinates to and from Clipper
+clipperScale = 100000
+inverseClipperScale = 1.0 / clipperScale
+
+# approximateSegmentLength setting
+_approximateSegmentLength = 5.3
+
+# -------------
+# Input Objects
+# -------------
+
+# Input
+
+class InputContour(object):
+
+    def __init__(self, contour):
+        # gather the point data
+        pointPen = ContourPointDataPen()
+        contour.drawPoints(pointPen)
+        points = pointPen.getData()
+        reversedPoints = _reversePoints(points)
+        # gather segments
+        self.segments = _convertPointsToSegments(points)
+        # only calculate once all the flat points.
+        # it seems to have some tiny difference and its a lot faster
+        # if the flat points are calculated from the reversed input points.
+        self.reversedSegments = _convertPointsToSegments(reversedPoints, willBeReversed=True)
+        # simple reverse the flat points and store them in the reversedSegments
+        index = 0
+        for segment in self.segments:
+            otherSegment = self.reversedSegments[index]
+            otherSegment.flat = segment.getReversedFlatPoints()
+            index -= 1
+        # get the direction
+        self.clockwise = contour.clockwise
+        # store the gathered data
+        if self.clockwise:
+            self.clockwiseSegments = self.segments
+            self.counterClockwiseSegments = self.reversedSegments
+        else:
+            self.clockwiseSegments = self.reversedSegments
+            self.counterClockwiseSegments = self.segments
+        # flag indicating if the contour has been used
+        self.used = False
+
+    # ----------
+    # Attributes
+    # ----------
+
+    # the original direction in flat segments
+
+    def _get_originalFlat(self):
+        if self.clockwise:
+            return self.clockwiseFlat
+        else:
+            return self.counterClockwiseFlat
+
+    originalFlat = property(_get_originalFlat)
+
+    # the clockwise direction in flat segments
+
+    def _get_clockwiseFlat(self):
+        flat = []
+        segments = self.clockwiseSegments
+        for segment in segments:
+            flat.extend(segment.flat)
+        return flat
+
+    clockwiseFlat = property(_get_clockwiseFlat)
+
+    # the counter-clockwise direction in flat segments
+
+    def _get_counterClockwiseFlat(self):
+        flat = []
+        segments = self.counterClockwiseSegments
+        for segment in segments:
+            flat.extend(segment.flat)
+        return flat
+
+    counterClockwiseFlat = property(_get_counterClockwiseFlat)
+
+    def hasOnCurve(self):
+        for inputSegment in self.segments:
+            if not inputSegment.used and inputSegment.segmentType != "line":
+                return True
+        return False
+
+
+class InputSegment(object):
+
+    #__slots__ = ["points", "previousOnCurve", "scaledPreviousOnCurve", "flat", "used"]
+
+    def __init__(self, points=None, previousOnCurve=None, willBeReversed=False):
+        if points is None:
+            points = []
+        self.points = points
+        self.previousOnCurve = previousOnCurve
+        self.scaledPreviousOnCurve = _scaleSinglePoint(previousOnCurve, scale=clipperScale)
+        self.used = False
+        self.flat = []
+        # if the bcps are equal to the oncurves convert the segment to a line segment.
+        # otherwise this causes an error when flattening.
+        if self.segmentType == "curve":
+            if previousOnCurve == points[0].coordinates and points[1].coordinates == points[-1].coordinates:
+                oncurve = points[-1]
+                oncurve.segmentType = "line"
+                self.points = points = [oncurve]
+            elif previousOnCurve[0] == points[0].coordinates[0] == points[1].coordinates[0] == points[-1].coordinates[0]:
+                oncurve = points[-1]
+                oncurve.segmentType = "line"
+                self.points = points = [oncurve]
+            elif previousOnCurve[1] == points[0].coordinates[1] == points[1].coordinates[1] == points[-1].coordinates[1]:
+                oncurve = points[-1]
+                oncurve.segmentType = "line"
+                self.points = points = [oncurve]
+        # its a reversed segment the flat points will be set later on in the InputContour
+        if willBeReversed:
+            return
+        pointsToFlatten = []
+        if self.segmentType == "qcurve":
+            assert len(points) >= 0
+            flat = []
+            currentOnCurve = previousOnCurve
+            pointCoordinates = [point.coordinates for point in points]
+            for pt1, pt2 in decomposeQuadraticSegment(pointCoordinates[1:]):
+                pt0x, pt0y = currentOnCurve
+                pt1x, pt1y = pt1
+                pt2x, pt2y = pt2
+                mid1x = pt0x + 0.66666666666666667 * (pt1x - pt0x)
+                mid1y = pt0y + 0.66666666666666667 * (pt1y - pt0y)
+                mid2x = pt2x + 0.66666666666666667 * (pt1x - pt2x)
+                mid2y = pt2y + 0.66666666666666667 * (pt1y - pt2y)
+                
+                convertedQuadPointToFlatten = [currentOnCurve, (mid1x, mid1y), (mid2x, mid2y), pt2]
+                flat.extend(_flattenSegment(convertedQuadPointToFlatten))
+                currentOnCurve = pt2
+            self.flat = flat
+            # this shoudl be easy.
+            # copy the quad to cubic from fontTools.pens.basePen
+        elif self.segmentType == "curve":
+            pointsToFlatten = [previousOnCurve] + [point.coordinates for point in points]
+        else:
+            assert len(points) == 1
+            self.flat = [point.coordinates for point in points]
+        if pointsToFlatten:
+            self.flat = _flattenSegment(pointsToFlatten)
+        # if len(self.flat) == 1 and self.segmentType == "curve":
+        #     oncurve = self.points[-1]
+        #     oncurve.segmentType = "line"
+        #     self.points = [oncurve]
+        self.flat = _scalePoints(self.flat, scale=clipperScale)
+        self.flat = _checkFlatPoints(self.flat)
+        self.used = False
+
+    def _get_segmentType(self):
+        return self.points[-1].segmentType
+
+    segmentType = property(_get_segmentType)
+
+    def getReversedFlatPoints(self):
+        reversedFlatPoints = [self.scaledPreviousOnCurve] + self.flat[:-1]
+        reversedFlatPoints.reverse()
+        return reversedFlatPoints
+
+    def split(self, tValues):
+        """
+        Split the segment according the t values
+        """
+        if self.segmentType == "curve":
+            on1 = self.previousOnCurve
+            off1 = self.points[0].coordinates
+            off2 = self.points[1].coordinates
+            on2 = self.points[2].coordinates
+            return bezierTools.splitCubicAtT(on1, off1, off2, on2, *tValues)
+        elif self.segmentType == "line":
+            segments = []
+            x1, y1 = self.previousOnCurve
+            x2, y2 = self.points[0].coordinates
+            dx = x2 - x1
+            dy = y2 - y1
+            pp = x1, y1
+            for t in tValues:
+                np = (x1+dx*t, y1+dy*t)
+                segments.append([pp, np])
+                pp = np
+            segments.append([pp, (x2, y2)])
+            return segments
+        elif self.segmentType == "qcurve":
+            raise NotImplementedError
+        else:
+            raise NotImplementedError
+
+    def tValueForPoint(self, point):
+        """
+        get a t values for a given point
+
+        required:
+            the point must be a point on the curve.
+            in an overlap cause the point will be an intersection points wich is alwasy a point on the curve
+        """
+        if self.segmentType == "curve":
+            on1 = self.previousOnCurve
+            off1 = self.points[0].coordinates
+            off2 = self.points[1].coordinates
+            on2 = self.points[2].coordinates
+            return _tValueForPointOnCubicCurve(point, (on1, off1, off2, on2))
+        elif self.segmentType == "line":
+            return _tValueForPointOnLine(point, (self.previousOnCurve, self.points[0].coordinates))
+        elif self.segmentType == "qcurve":
+            raise NotImplementedError
+        else:
+            raise NotImplementedError
+
+
+class InputPoint(object):
+
+    __slots__ = ["coordinates", "segmentType", "smooth", "name", "kwargs"]
+
+    def __init__(self, coordinates, segmentType=None, smooth=False, name=None, kwargs=None):
+        x, y = coordinates
+        self.coordinates = coordinates
+        self.segmentType = segmentType
+        self.smooth = smooth
+        self.name = name
+        self.kwargs = kwargs
+
+    def copy(self):
+        copy = self.__class__(
+            coordinates=self.coordinates,
+            segmentType=self.segmentType,
+            smooth=self.smooth,
+            name=self.name,
+            kwargs=self.kwargs
+        )
+        return copy
+
+
+# -------------
+# Input Support
+# -------------
+
+class ContourPointDataPen:
+
+    """
+    Point pen for gathering raw contour data.
+    An instance of this pen may only be used for one contour.
+    """
+
+    def __init__(self):
+        self._points = None
+
+    def getData(self):
+        """
+        Return a list of normalized InputPoint objects
+        for the contour drawn with this pen.
+        """
+        # organize the points into segments
+        # 1. make sure there is an on curve
+        haveOnCurve = False
+        for point in self._points:
+            if point.segmentType is not None:
+                haveOnCurve = True
+                break
+        # 2. move the off curves to front of the list
+        if haveOnCurve:
+            _prepPointsForSegments(self._points)
+        # 3. ignore double points on start and end
+        firstPoint = self._points[0]
+        lastPoint = self._points[-1]
+        if firstPoint.segmentType is not None and lastPoint.segmentType is not None:
+            if firstPoint.coordinates == lastPoint.coordinates:
+                self._points = self._points[1:]
+                if firstPoint.segmentType != "line":
+                    lastPoint.segmentType = firstPoint.segmentType
+        # done
+        return self._points
+
+    def beginPath(self):
+        assert self._points is None
+        self._points = []
+
+    def endPath(self):
+        pass
+
+    def addPoint(self, pt, segmentType=None, smooth=False, name=None, **kwargs):
+        assert segmentType != "move"
+        data = InputPoint(
+            coordinates=pt,
+            segmentType=segmentType,
+            smooth=smooth,
+            name=name,
+            kwargs=kwargs
+        )
+        self._points.append(data)
+
+    def addComponent(self, baseGlyphName, transformation):
+        raise NotImplementedError
+
+def _prepPointsForSegments(points):
+    """
+    Move any off curves at the end of the contour
+    to the beginning of the contour. This makes
+    segmentation easier.
+    """
+    while 1:
+        point = points[-1]
+        if point.segmentType:
+            break
+        else:
+            point = points.pop()
+            points.insert(0, point)
+            continue
+        break
+
+def _copyPoints(points):
+    """
+    Make a shallow copy of the points.
+    """
+    copied = [point.copy() for point in points]
+    return copied
+
+def _reversePoints(points):
+    """
+    Reverse the points. This differs from the
+    reversal point pen in RoboFab in that it doesn't
+    worry about maintaing the start point position.
+    That has no benefit within the context of this module.
+    """
+    # copy the points
+    points = _copyPoints(points)
+    # find the first on curve type and recycle
+    # it for the last on curve type
+    firstOnCurve = None
+    for index, point in enumerate(points):
+        if point.segmentType is not None:
+            firstOnCurve = index
+            break
+    lastSegmentType = points[firstOnCurve].segmentType
+    # reverse the points
+    points = reversed(points)
+    # work through the reversed remaining points
+    final = []
+    for point in points:
+        segmentType = point.segmentType
+        if segmentType is not None:
+            point.segmentType = lastSegmentType
+            lastSegmentType = segmentType
+        final.append(point)
+    # move any offcurves at the end of the points
+    # to the start of the points
+    _prepPointsForSegments(final)
+    # done
+    return final
+
+def _convertPointsToSegments(points, willBeReversed=False):
+    """
+    Compile points into InputSegment objects.
+    """
+    # get the last on curve
+    previousOnCurve = None
+    for point in reversed(points):
+        if point.segmentType is not None:
+            previousOnCurve = point.coordinates
+            break
+    assert previousOnCurve is not None
+    # gather the segments
+    offCurves = []
+    segments = []
+    for point in points:
+        # off curve, hold.
+        if point.segmentType is None:
+            offCurves.append(point)
+        else:
+            segment = InputSegment(
+                points=offCurves + [point],
+                previousOnCurve=previousOnCurve,
+                willBeReversed=willBeReversed
+            )
+            segments.append(segment)
+            offCurves = []
+            previousOnCurve = point.coordinates
+    assert not offCurves
+    return segments
+
+
+# --------------
+# Output Objects
+# --------------
+
+class OutputContour(object):
+
+    def __init__(self, pointList):
+        if pointList[0] == pointList[-1]:
+            del pointList[-1]
+        self.clockwise = _getClockwise(pointList)
+        self.segments = [
+            OutputSegment(
+                segmentType="flat",
+                points=[point]
+            ) for point in pointList
+        ]
+
+    def _scalePoint(self, point):
+        x, y = point
+        x = x * inverseClipperScale
+        if int(x) == x:
+            x = int(x)
+        y = y * inverseClipperScale
+        if int(y) == y:
+            y = int(y)
+        return x, y
+
+    # ----------
+    # Attributes
+    # ----------
+
+    def _get_final(self):
+        # XXX this could be optimized:
+        # store a fixed value after teh contour is finalized
+        # don't do the dymanic searching if that flag is set to True
+        for segment in self.segments:
+            if not segment.final:
+                return False
+        return True
+
+    final = property(_get_final)
+
+    # --------------------------
+    # Re-Curve and Curve Fitting
+    # --------------------------
+
+    def reCurveFromEntireInputContour(self, inputContour):
+        if self.clockwise:
+            inputFlat = inputContour.clockwiseFlat
+        else:
+            inputFlat = inputContour.counterClockwiseFlat
+        outputFlat = []
+        for segment in self.segments:
+            # XXX this could be expensive
+            assert segment.segmentType == "flat"
+            outputFlat += segment.points
+        # test lengths
+        haveMatch = False
+        if len(inputFlat) == len(outputFlat):
+            if inputFlat == outputFlat:
+                haveMatch = True
+            else:
+                inputStart = inputFlat[0]
+                if inputStart in outputFlat:
+                    # there should be only one occurance of the point
+                    # but handle it just in case
+                    if outputFlat.count(inputStart) > 1:
+                        startIndexes = [index for index, point in enumerate(outputFlat) if point == inputStart]
+                    else:
+                        startIndexes = [outputFlat.index(inputStart)]
+                    # slice and dice to test possible orders
+                    for startIndex in startIndexes:
+                        test = outputFlat[startIndex:] + outputFlat[:startIndex]
+                        if inputFlat == test:
+                            haveMatch = True
+                            break
+        if haveMatch:
+            # clear out the flat points
+            self.segments = []
+            # replace with the appropriate points from the input
+            if self.clockwise:
+                inputSegments = inputContour.clockwiseSegments
+            else:
+                inputSegments = inputContour.counterClockwiseSegments
+            for inputSegment in inputSegments:
+                self.segments.append(
+                    OutputSegment(
+                        segmentType=inputSegment.segmentType,
+                        points=[
+                            OutputPoint(
+                                coordinates=point.coordinates,
+                                segmentType=point.segmentType,
+                                smooth=point.smooth,
+                                name=point.name,
+                                kwargs=point.kwargs
+                            )
+                            for point in inputSegment.points
+                        ],
+                        final=True
+                    )
+                )
+                inputSegment.used = True
+            # reset the direction of the final contour
+            self.clockwise = inputContour.clockwise
+            return True
+        return False
+
+    def reCurveFromInputContourSegments(self, inputContour):
+        return
+        # match individual segments
+        if self.clockwise:
+            inputSegments = inputContour.clockwiseSegments
+        else:
+            inputSegments = inputContour.counterClockwiseSegments
+        for inputSegment in inputSegments:
+            # skip used
+            if inputSegment.used:
+                continue
+            # skip if the input contains more points than the entire output contour
+            if len(inputSegment.flat) > len(self.segments):
+                continue
+            # skip if the input end is not in the contour
+            inputSegmentLastPoint = inputSegment.flat[-1]
+            outputFlat = [segment.points[-1] for segment in self.segments]
+            if inputSegmentLastPoint not in outputFlat:
+                continue
+            # work through all output segments
+            for outputSegmentIndex, outputSegment in enumerate(self.segments):
+                # skip finalized
+                if outputSegment.final:
+                    continue
+                # skip if the output point doesn't match the input end
+                if outputSegment.points[-1] != inputSegmentLastPoint:
+                    continue
+                # make a set of ranges for slicing the output into a testable list of points
+                inputLength = len(inputSegment.flat)
+                outputRanges = []
+                outputSegmentIndex += 1
+                if outputSegmentIndex - inputLength < 0:
+                    r1 = (len(self.segments) + outputSegmentIndex - inputLength, len(self.segments))
+                    outputRanges.append(r1)
+                    r2 = (0, outputSegmentIndex)
+                    outputRanges.append(r2)
+                else:
+                    outputRanges.append((outputSegmentIndex - inputLength, outputSegmentIndex))
+                # gather the output segments
+                testableOutputSegments = []
+                for start, end in outputRanges:
+                    testableOutputSegments += self.segments[start:end]
+                # create a list of points
+                test = []
+                for s in testableOutputSegments:
+                    # stop if a segment is final
+                    if s.final:
+                        test = None
+                        break
+                    test.append(s.points[-1])
+                if test == inputSegment.flat and inputSegment.segmentType != "line":
+                    # insert new segment                    
+                    newSegment = OutputSegment(
+                        segmentType=inputSegment.segmentType,
+                        points=[
+                            OutputPoint(
+                                coordinates=point.coordinates,
+                                segmentType=point.segmentType,
+                                smooth=point.smooth,
+                                name=point.name,
+                                kwargs=point.kwargs
+                            )
+                            for point in inputSegment.points
+                        ],
+                        final=True
+                    )
+                    self.segments.insert(outputSegmentIndex, newSegment)
+                    # remove old segments
+                    # XXX this is sloppy
+                    for start, end in outputRanges:
+                        if start > outputSegmentIndex:
+                            start += 1
+                            end += 1
+                        del self.segments[start:end]
+                    # flag the original as used
+                    inputSegment.used = True
+                    break
+        # ? match line start points (to prevent curve fit in shortened line)
+        return False
+
+    def reCurveSubSegmentsCheckInputContoursOnHasCurve(self, inputContours):
+        # test is the remaining input contours contains only lineTo points
+        # XXX could be cached
+        return True
+        # for inputContour in inputContours:
+        #     if inputContour.used:
+        #         continue
+        #     if inputContour.hasOnCurve():
+        #         return True
+        # return False
+
+    def reCurveSubSegments(self, inputContours):
+        if not self.segments:
+            # its all done
+            return 
+        # the inputContours has some curved segments
+        # if not it all the segments will be converted at the end
+        if self.reCurveSubSegmentsCheckInputContoursOnHasCurve(inputContours):
+            # collect all flat points in a dict of unused inputContours
+            # collect both clockwise segment and counterClockwise segments
+            # it happens a lot that the directions turns around
+            # the clockwise attribute can help but testing the directions is always needed
+            # collect all oncurve points as well
+            flatInputPointsSegmentDict = dict()
+            reversedFlatInputPointsSegmentDict = dict()
+            flatIntputOncurves = set()
+            for inputContour in inputContours:
+                if inputContour.used:
+                    continue
+                if self.clockwise:
+                    inputSegments = inputContour.clockwiseSegments
+                    reversedSegments = inputContour.counterClockwiseSegments
+                else:
+                    inputSegments = inputContour.counterClockwiseSegments
+                    reversedSegments = inputContour.clockwiseSegments
+                for inputSegment in inputSegments:
+                    if inputSegment.used:
+                        continue
+                    for p in inputSegment.flat:
+                        flatInputPointsSegmentDict[p] = inputSegment
+                    flatIntputOncurves.add(inputSegment.scaledPreviousOnCurve)
+                    
+                for inputSegment in reversedSegments:
+                    if inputSegment.used:
+                        continue
+                    for p in inputSegment.flat:
+                        reversedFlatInputPointsSegmentDict[p] = inputSegment
+                    flatIntputOncurves.add(inputSegment.scaledPreviousOnCurve)
+            flatInputPoints = set(flatInputPointsSegmentDict.keys())
+            # reset the starting point to a known point.
+            # not somewhere in the middle of a flatten point list
+            firstSegment = self.segments[0]
+            foundStartingPoint = True
+            if firstSegment.segmentType == "flat":
+                foundStartingPoint = False
+                for index, segment in enumerate(self.segments):
+                    if segment.segmentType in ["line", "curve", "qcurve"]:
+                        foundStartingPoint = True
+                        break
+                if foundStartingPoint:
+                    # if found re index the segments
+                    # if there is no known starting point found do it later based on the intersection points
+                    self.segments = self.segments[index:] + self.segments[:index]
+            # collect all flat points in a intersect segment
+            remainingSubSegment = OutputSegment(segmentType="intersect", points=[])
+            # store all segments in one big temp list
+            newSegments = []
+            for index, segment in enumerate(self.segments):
+                if segment.segmentType != "flat":
+                    # when the segment contains only one points its a line cause it is a single intersection point
+                    if len(remainingSubSegment.points) == 1:
+                        remainingSubSegment.segmentType = "line"
+                        remainingSubSegment.final = True
+                        remainingSubSegment.points = [
+                                          OutputPoint(
+                                                coordinates=self._scalePoint(point),
+                                                segmentType="line",
+                                                smooth=point.smooth,
+                                                name=point.name,
+                                                kwargs=point.kwargs
+                                              )
+                                          for point in remainingSubSegment.points
+                                          ]
+                    newSegments.append(remainingSubSegment)
+                    remainingSubSegment = OutputSegment(segmentType="intersect", points=[])
+                    newSegments.append(segment)
+                    continue
+                remainingSubSegment.points.extend(segment.points)
+            newSegments.append(remainingSubSegment)
+            # loop over all segments 
+            for segment in newSegments:
+                # handle only segments tagged as intersect
+                if segment.segmentType != "intersect":
+                    continue
+                # skip empty segments
+                if not segment.points:
+                    continue
+                # get al inputSegments, this is an unorderd list of all points no in the the flatInputPoints
+                segmentPointsSet = set(segment.points)
+                intersectionPoints = segmentPointsSet - flatInputPoints
+                # merge both oncurves and intersectionPoints as known points
+                possibleStartingPoints = flatIntputOncurves | intersectionPoints
+                hasOncurvePoints = segmentPointsSet & flatIntputOncurves
+                # if not starting point is found earlier do it here
+                foundStartingPointIndex = None
+                if not foundStartingPoint:
+                    for index, p in enumerate(segment.points):
+                        if p in flatIntputOncurves:
+                            foundStartingPointIndex = index
+                            break
+                    if foundStartingPointIndex is None:
+                        for index, p in enumerate(segment.points):
+                            if p in intersectionPoints:
+                                foundStartingPointIndex = index
+                                break
+                    segment.points = segment.points[foundStartingPointIndex:] + segment.points[:foundStartingPointIndex]
+                # split list based on oncurvepoints and intersection points
+                segmentedFlatPoints = [[]]
+                for p in segment.points:
+                    segmentedFlatPoints[-1].append(p)
+                    if p in possibleStartingPoints:
+                        segmentedFlatPoints.append([])
+                if not segmentedFlatPoints[-1]:
+                    segmentedFlatPoints.pop(-1)
+                if len(segmentedFlatPoints) > 1 and len(segmentedFlatPoints[0]) == 1:
+                    ## possible starting point of last part of the curve
+                    ## check of the both have the same inputSegment or reversedInputSegment
+                    fp = segmentedFlatPoints[0][0]
+                    lp = segmentedFlatPoints[-1][-1]
+                    mergeFirstSegments = False
+                    if fp in flatInputPoints and lp in flatInputPoints:
+                        firstInputSegment = flatInputPointsSegmentDict[fp]
+                        lastInputSegment = flatInputPointsSegmentDict[lp]
+                        reversedFirstInputSegment = reversedFlatInputPointsSegmentDict[fp]
+                        reversedLastInputSegment = reversedFlatInputPointsSegmentDict[lp]
+                        if (firstInputSegment.segmentType == reversedFirstInputSegment.segmentType == "curve") or (lastInputSegment.segmentType == reversedLastInputSegment.segmentType == "curve"):
+                            if firstInputSegment == lastInputSegment or reversedFirstInputSegment == reversedLastInputSegment:
+                                mergeFirstSegments = True
+                            #elif len(firstInputSegment.points) > 1 and len(lastInputSegment.points) > 1:
+                            elif fp == lastInputSegment.scaledPreviousOnCurve:
+                                mergeFirstSegments = True
+                            elif lp == firstInputSegment.scaledPreviousOnCurve:
+                                mergeFirstSegments = True
+                            elif fp == reversedLastInputSegment.scaledPreviousOnCurve:
+                                mergeFirstSegments = True
+                            elif lp == reversedFirstInputSegment.scaledPreviousOnCurve:
+                                mergeFirstSegments = True
+                    elif not hasOncurvePoints and _distance(fp, lp) < _approximateSegmentLength*clipperScale:
+                        mergeFirstSegments = True
+                    if mergeFirstSegments:
+                        segmentedFlatPoints[0] = segmentedFlatPoints[-1] + segmentedFlatPoints[0]
+                        segmentedFlatPoints.pop(-1)
+                        mergeFirstSegments = False
+                convertedSegments = []
+                previousIntersectionPoint = None
+                if segmentedFlatPoints[-1][-1] in intersectionPoints:
+                    previousIntersectionPoint = self._scalePoint(segmentedFlatPoints[-1][-1])
+                elif segmentedFlatPoints[0][0] in intersectionPoints:
+                    previousIntersectionPoint = self._scalePoint(segmentedFlatPoints[0][0])
+
+                for flatSegment in segmentedFlatPoints:
+                    # search two points in the flat segment that is not an inputOncurve or intersection point
+                    # to get a proper direction of the flatSegment
+                    # based on these two points pick a inputSegment
+                    fp = ep = None
+                    for p in flatSegment:
+                        if p in possibleStartingPoints:
+                            continue
+                        elif fp is None:
+                            fp = p
+                        elif ep is None:
+                            ep = p
+                        else:
+                            break
+                    canDoFastLine = True
+                    if fp is None and ep is None:
+                        # flat segment only contains two intersection points or one intersection point and one input oncurve point
+                        # this can be ignored cause this is a very small line
+                        # and will be converted to a simple line
+                        if self.clockwise:
+                            inputSegment = reversedFlatInputPointsSegmentDict.get(flatSegment[-1])
+                        else:
+                            inputSegment = flatInputPointsSegmentDict.get(flatSegment[-1]) 
+                    else:
+                        # get inputSegment based on the clockwise settings
+                        inputSegment = flatInputPointsSegmentDict[fp]
+                        if ep is not None and ep in inputSegment.flat:
+                            # if two points are found get indexes
+                            fi = inputSegment.flat.index(fp)
+                            ei = inputSegment.flat.index(ep)
+                            if fi > ei:
+                                # if the start index is bigger
+                                # get the reversed inputSegment
+                                inputSegment = reversedFlatInputPointsSegmentDict[fp]
+                        else:
+                            # if flat segment is short and has only one point not in intersections and input oncurves
+                            # test it against the reversed inputSegment
+                            reversedInputSegment = reversedFlatInputPointsSegmentDict[fp]
+                            if flatSegment[0] == reversedInputSegment.flat[0] and flatSegment[-1] == reversedInputSegment.flat[-1]:
+                                inputSegment = reversedInputSegment
+                            elif flatSegment[0] in intersectionPoints and flatSegment[-1] == reversedInputSegment.flat[-1]:
+                                inputSegment = reversedInputSegment
+                            elif flatSegment[-1] in intersectionPoints and flatSegment[0] == reversedInputSegment.flat[0]:
+                                inputSegment = reversedInputSegment
+                            canDoFastLine = False
+                        # if there is only one point in a flat segment
+                        # this is a single intersection points (two crossing lineTo's)
+                        if inputSegment.segmentType == "curve":
+                            canDoFastLine = False
+                    if (len(flatSegment) == 1 or inputSegment is None) and canDoFastLine:
+                        #p = flatSegment[0]
+                        for p in flatSegment:
+                            previousIntersectionPoint = self._scalePoint(p)
+                            pointInfo = dict()
+                            kwargs = dict()
+                            if p in flatInputPointsSegmentDict:
+                                lineSegment = flatInputPointsSegmentDict[p]
+                                segmentPoint =  lineSegment.points[-1]
+                                pointInfo["smooth"] = segmentPoint.smooth
+                                pointInfo["name"] = segmentPoint.name
+                                kwargs.update(segmentPoint.kwargs)
+                            convertedSegments.append(OutputPoint(coordinates=previousIntersectionPoint, segmentType="line", kwargs=kwargs, **pointInfo))
+                        continue
+                    tValues = None
+                    lastPointWithAttributes = None
+                    if flatSegment[0] == inputSegment.flat[0] and flatSegment[-1] != inputSegment.flat[-1]:
+                        # needed the first part of the segment
+                        #if previousIntersectionPoint is None:
+                        #    previousIntersectionPoint = self._scalePoint(flatSegment[-1])
+                        searchPoint = self._scalePoint(flatSegment[-1])
+                        tValues = inputSegment.tValueForPoint(searchPoint)
+                        curveNeeded = 0
+                        replacePointOnNewCurve = [(3, searchPoint)]
+                        previousIntersectionPoint = searchPoint
+                    elif flatSegment[-1] == inputSegment.flat[-1] and flatSegment[0] != inputSegment.flat[0]:
+                        # needed the end of the segment
+                        if previousIntersectionPoint is None:
+                            previousIntersectionPoint = self._scalePoint(flatSegment[0])
+                            convertedSegments.append(OutputPoint(
+                                coordinates=previousIntersectionPoint,
+                                segmentType="line",
+                            ))
+                        tValues = inputSegment.tValueForPoint(previousIntersectionPoint)
+                        curveNeeded = -1
+                        replacePointOnNewCurve = [(0, previousIntersectionPoint)]
+                        previousIntersectionPoint = None
+                        lastPointWithAttributes = inputSegment.points[-1]
+                    elif flatSegment[0] != inputSegment.flat[0] and flatSegment[-1] != inputSegment.flat[-1]:
+                        # needed the a middle part of the segment
+                        tValues = inputSegment.tValueForPoint(previousIntersectionPoint)
+                        searchPoint = self._scalePoint(flatSegment[-1])
+                        tValues.extend(inputSegment.tValueForPoint(searchPoint))
+                        curveNeeded = 1
+                        replacePointOnNewCurve = [(0, previousIntersectionPoint), (3, searchPoint)]
+                        previousIntersectionPoint = searchPoint
+                    else:
+                        # take the whole segments as is
+                        newCurve = [
+                            OutputPoint(
+                                coordinates=point.coordinates,
+                                segmentType=point.segmentType,
+                                smooth=point.smooth,
+                                name=point.name,
+                                kwargs=point.kwargs
+                            )
+                            for point in inputSegment.points
+                        ]
+                        convertedSegments.extend(newCurve)
+                        previousIntersectionPoint = None                    
+                    # if we found some tvalue, split the curve and get the requested parts of the splitted curves
+                    if tValues:
+                        newCurve = inputSegment.split(tValues)
+                        newCurve = list(newCurve[curveNeeded])
+                        for i, replace in replacePointOnNewCurve:
+                            newCurve[i] = replace
+                        newCurve = [OutputPoint(coordinates=p, segmentType=None) for p in newCurve[1:]]
+                        newCurve[-1].segmentType = inputSegment.segmentType
+                        if lastPointWithAttributes is not None:
+                            newCurve[-1].smooth = lastPointWithAttributes.smooth
+                            newCurve[-1].name = lastPointWithAttributes.name
+                            newCurve[-1].kwargs = lastPointWithAttributes.kwargs
+                        convertedSegments.extend(newCurve)
+                # replace the the points with the converted segments
+                segment.points = convertedSegments
+                segment.segmentType = "reCurved"
+            self.segments = newSegments
+        # XXX convert all of the remaining segments to lines
+        for segment in self.segments:
+            if not segment.points:
+                continue
+            if segment.segmentType not in ["intersect", "flat"]:
+                continue
+            segment.segmentType = "line"
+            segment.points = [
+                OutputPoint(
+                    coordinates=self._scalePoint(point),
+                    segmentType="line",
+                    # smooth=point.smooth,
+                    # name=point.name,
+                    # kwargs=point.kwargs
+                )
+                for point in segment.points
+            ]
+
+    # ----
+    # Draw
+    # ----
+
+    def drawPoints(self, pointPen):
+        pointPen.beginPath()
+        points = []
+        for segment in self.segments:
+            points.extend(segment.points)
+
+        hasOnCurve = False
+        for point in points:
+            if point.segmentType is not None:
+                hasOnCurve = True
+                break
+        if hasOnCurve:
+            while points[0].segmentType is None:
+                p = points.pop(0)
+                points.append(p)
+        previousPointCoordinates = None
+        for point in points:
+            if previousPointCoordinates is not None and point.segmentType and tuple(point.coordinates) == previousPointCoordinates:
+                continue
+            kwargs = {}
+            if point.kwargs is not None:
+                kwargs = point.kwargs
+            pointPen.addPoint(
+                point.coordinates,
+                segmentType=point.segmentType,
+                smooth=point.smooth,
+                name=point.name,
+                **kwargs
+            )
+            if point.segmentType:
+                previousPointCoordinates = tuple(point.coordinates)
+            else:
+                previousPointCoordinates = None
+        pointPen.endPath()
+
+
+class OutputSegment(object):
+
+    __slots__ = ["segmentType", "points", "final"]
+
+    def __init__(self, segmentType=None, points=None, final=False):
+        self.segmentType = segmentType
+        if points is None:
+            points = []
+        self.points = points
+        self.final = final
+
+
+class OutputPoint(InputPoint): pass
+
+
+# -------------
+# Ouput Support
+# -------------
+
+def _getClockwise(points):
+    """
+    Very quickly get the direction for points.
+    This only works for contours that *do not*
+    self-intersect. It works by finding the area
+    of the polygon. positive is counter-clockwise,
+    negative is clockwise.
+    """
+    # quickly make segments
+    segments = zip(points, points[1:] + [points[0]])
+    # get the area
+    area = sum([x0 * y1 - x1 * y0 for ((x0, y0), (x1, y1)) in segments])
+    return area <= 0
+
+# ----------
+# Misc. Math
+# ----------
+
+def _tValueForPointOnCubicCurve(point, (pt1, pt2, pt3, pt4), isHorizontal=0):
+    """
+    Finds a t value on a curve from a point.
+    The points must be originaly be a point on the curve.
+    This will only back trace the t value, needed to split the curve in parts
+    """
+    a, b, c, d = bezierTools.calcCubicParameters(pt1, pt2, pt3, pt4)
+    solutions = bezierTools.solveCubic(a[isHorizontal], b[isHorizontal], c[isHorizontal],
+        d[isHorizontal] - point[isHorizontal])
+    solutions = [t for t in solutions if 0 <= t < 1]
+    if not solutions and not isHorizontal:
+        # can happen that a horizontal line doens intersect, try the vertical
+        return _tValueForPointOnCubicCurve(point, (pt1, pt2, pt3, pt4), isHorizontal=1)
+    if len(solutions) > 1:
+        intersectionLenghts = {}
+        for t in solutions:
+            tp = _getCubicPoint(t, pt1, pt2, pt3, pt4)
+            dist = _distance(tp, point)
+            intersectionLenghts[dist] = t
+        minDist = min(intersectionLenghts.keys())
+        solutions = [intersectionLenghts[minDist]]
+    return solutions
+
+def _tValueForPointOnQuadCurve(point, pts, isHorizontal=0):
+    quadSegments = decomposeQuadraticSegment(pts[1:])
+    previousOnCurve = pts[0]
+    solutionsDict = dict()
+    for index, (pt1, pt2) in enumerate(quadSegments):
+        a, b, c = bezierTools.calcQuadraticParameters(previousOnCurve, pt1, pt2)
+        subSolutions = bezierTools.solveQuadratic(a[isHorizontal], b[isHorizontal], c[isHorizontal] - point[isHorizontal])
+        subSolutions = [t for t in subSolutions if 0 <= t < 1]
+        for t in subSolutions:
+            solutionsDict[(t, index)] = _getQuadPoint(t, previousOnCurve, pt1, pt2)
+        previousOnCurve = pt2
+    solutions = solutionsDict.keys()
+    if not solutions and not isHorizontal:
+        return _tValueForPointOnQuadCurve(point, pts, isHorizontal=1)
+    if len(solutions) > 1:
+        intersectionLenghts = {}
+        for t in solutions:
+            tp = solutionsDict[t]
+            dist = _distance(tp, point)
+            intersectionLenghts[dist] = t
+        minDist = min(intersectionLenghts.keys())
+        solutions = [intersectionLenghts[minDist]]
+    return solutions
+
+def _tValueForPointOnLine(point, (pt1, pt2)):
+    dist = _distance(pt1, point)
+    totalDist = _distance(pt1, pt2)
+    return [dist / totalDist]
+
+def _scalePoints(points, scale=1, convertToInteger=True):
+    """
+    Scale points and optionally convert them to integers.
+    """
+    if convertToInteger:
+        points = [
+            (int(round(x * scale)), int(round(y * scale)))
+            for (x, y) in points
+        ]
+    else:
+        points = [(x * scale, y * scale) for (x, y) in points]
+    return points
+
+def _scaleSinglePoint(point, scale=1, convertToInteger=True):
+    """
+    Scale a single point
+    """
+    x, y = point
+    if convertToInteger:
+        return int(round(x * scale)), int(round(y * scale))
+    else:
+        (x * scale, y * scale)
+
+def _intPoint(pt):
+    return int(round(pt[0])), int(round(pt[1]))
+
+def _checkFlatPoints(points):
+    _points = []
+    previousX = previousY = None
+    for x, y in points:
+        if x == previousX:
+            continue
+        elif y == previousY:
+            continue
+        if (x, y) not in _points: 
+            # is it possible that two flat point are on top of eachother???
+            _points.append((x, y))
+        previousX, previousY = x, y
+    if _points[-1] != points[-1]:
+        _points[-1] = points[-1]
+    return _points
+
+"""
+The curve flattening code was forked and modified from RoboFab's FilterPen.
+That code was written by Erik van Blokland.
+"""
+
+def _flattenSegment(segment, approximateSegmentLength=_approximateSegmentLength):
+    """
+    Flatten the curve segment int a list of points.
+    The first and last points in the segment must be
+    on curves. The returned list of points will not
+    include the first on curve point.
+
+    false curves (where the off curves are not any
+    different from the on curves) must not be sent here.
+    duplicate points must not be sent here.
+    """
+    onCurve1, offCurve1, offCurve2, onCurve2 = segment
+    if _pointOnLine(onCurve1, onCurve2, offCurve1) and _pointOnLine(onCurve1, onCurve2, offCurve2):
+        return [onCurve2]
+    est = _estimateCubicCurveLength(onCurve1, offCurve1, offCurve2, onCurve2) / approximateSegmentLength
+    flat = []
+    minStep = 0.1564
+    step = 1.0 / est
+    if step > .3:
+        step = minStep
+    t = step
+    while t < 1:
+        pt = _getCubicPoint(t, onCurve1, offCurve1, offCurve2, onCurve2)
+        flat.append(pt)
+        t += step 
+    flat.append(onCurve2)
+    return flat
+
+def _distance(pt1, pt2):
+    return math.sqrt((pt1[0] - pt2[0]) ** 2 + (pt1[1] - pt2[1]) ** 2)
+
+def _pointOnLine(pt1, pt2, a):
+    return abs(_distance(pt1, a) + _distance(a, pt2) - _distance(pt1, pt2)) < epsilon  
+
+def _estimateCubicCurveLength(pt0, pt1, pt2, pt3, precision=10):
+    """
+    Estimate the length of this curve by iterating
+    through it and averaging the length of the flat bits.
+    """
+    points = []
+    length = 0
+    step = 1.0 / precision
+    factors = range(0, precision + 1)
+    for i in factors:
+        points.append(_getCubicPoint(i * step, pt0, pt1, pt2, pt3))
+    for i in range(len(points) - 1):
+        pta = points[i]
+        ptb = points[i + 1]
+        length += _distance(pta, ptb)
+    return length
+
+def _mid((x0, y0), (x1, y1)):
+    """
+    (Point, Point) -> Point
+    Return the point that lies in between the two input points.
+    """
+    return 0.5 * (x0 + x1), 0.5 * (y0 + y1)
+
+def _getCubicPoint(t, pt0, pt1, pt2, pt3):
+    if t == 0:
+        return pt0
+    if t == 1:
+        return pt3
+    if t == 0.5:
+        a = _mid(pt0, pt1)
+        b = _mid(pt1, pt2)
+        c = _mid(pt2, pt3)
+        d = _mid(a, b)
+        e = _mid(b, c)
+        return _mid(d, e)
+    else:
+        cx = (pt1[0] - pt0[0]) * 3.0
+        cy = (pt1[1] - pt0[1]) * 3.0
+        bx = (pt2[0] - pt1[0]) * 3.0 - cx
+        by = (pt2[1] - pt1[1]) * 3.0 - cy
+        ax = pt3[0] - pt0[0] - cx - bx
+        ay = pt3[1] - pt0[1] - cy - by
+        t3 = t ** 3
+        t2 = t * t
+        x = ax * t3 + bx * t2 + cx * t + pt0[0]
+        y = ay * t3 + by * t2 + cy * t + pt0[1]
+        return x, y
+
+def _getQuadPoint(t, pt0, pt1, pt2):
+    if t == 0:
+        return pt0
+    if t == 1:
+        return pt2
+    else:
+        cx = pt0[0]
+        cy = pt0[1]
+        bx = (pt1[0] - cx) * 2.0
+        by = (pt1[1] - cy) * 2.0
+        ax = pt2[0] - cx - bx
+        ay = pt2[1] - cy - by
+        x = ax * t**2 + bx * t + cx
+        y = ay * t**2 + by * t + cy
+        return x, y
diff --git a/scripts/lib/booleanOperations/pyClipper-LINUX.so b/scripts/lib/booleanOperations/pyClipper-LINUX.so
new file mode 100644
index 0000000..20a5daf
--- /dev/null
+++ b/scripts/lib/booleanOperations/pyClipper-LINUX.so
diff --git a/scripts/lib/booleanOperations/pyClipper-MAC.so b/scripts/lib/booleanOperations/pyClipper-MAC.so
new file mode 100644
index 0000000..3e2d520
--- /dev/null
+++ b/scripts/lib/booleanOperations/pyClipper-MAC.so
diff --git a/scripts/lib/booleanOperations/pyClipper.so b/scripts/lib/booleanOperations/pyClipper.so
new file mode 100644
index 0000000..20a5daf
--- /dev/null
+++ b/scripts/lib/booleanOperations/pyClipper.so