aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/python/fonttools/fontTools/pens/pointInsidePen.py
blob: 8a579ae4c93f824b5ce3a5e80097aeffd5f5933d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
"""fontTools.pens.pointInsidePen -- Pen implementing "point inside" testing
for shapes.
"""

from fontTools.pens.basePen import BasePen
from fontTools.misc.bezierTools import solveQuadratic, solveCubic


__all__ = ["PointInsidePen"]


class PointInsidePen(BasePen):

    """This pen implements "point inside" testing: to test whether
    a given point lies inside the shape (black) or outside (white).
    Instances of this class can be recycled, as long as the
    setTestPoint() method is used to set the new point to test.

    Typical usage:

            pen = PointInsidePen(glyphSet, (100, 200))
            outline.draw(pen)
            isInside = pen.getResult()

    Both the even-odd algorithm and the non-zero-winding-rule
    algorithm are implemented. The latter is the default, specify
    True for the evenOdd argument of __init__ or setTestPoint
    to use the even-odd algorithm.
    """

    # This class implements the classical "shoot a ray from the test point
    # to infinity and count how many times it intersects the outline" (as well
    # as the non-zero variant, where the counter is incremented if the outline
    # intersects the ray in one direction and decremented if it intersects in
    # the other direction).
    # I found an amazingly clear explanation of the subtleties involved in
    # implementing this correctly for polygons here:
    #   http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html
    # I extended the principles outlined on that page to curves.

    def __init__(self, glyphSet, testPoint, evenOdd=False):
        BasePen.__init__(self, glyphSet)
        self.setTestPoint(testPoint, evenOdd)

    def setTestPoint(self, testPoint, evenOdd=False):
        """Set the point to test. Call this _before_ the outline gets drawn."""
        self.testPoint = testPoint
        self.evenOdd = evenOdd
        self.firstPoint = None
        self.intersectionCount = 0

    def getWinding(self):
        if self.firstPoint is not None:
            # always make sure the sub paths are closed; the algorithm only works
            # for closed paths.
            self.closePath()
        return self.intersectionCount

    def getResult(self):
        """After the shape has been drawn, getResult() returns True if the test
        point lies within the (black) shape, and False if it doesn't.
        """
        winding = self.getWinding()
        if self.evenOdd:
            result = winding % 2
        else:  # non-zero
            result = self.intersectionCount != 0
        return not not result

    def _addIntersection(self, goingUp):
        if self.evenOdd or goingUp:
            self.intersectionCount += 1
        else:
            self.intersectionCount -= 1

    def _moveTo(self, point):
        if self.firstPoint is not None:
            # always make sure the sub paths are closed; the algorithm only works
            # for closed paths.
            self.closePath()
        self.firstPoint = point

    def _lineTo(self, point):
        x, y = self.testPoint
        x1, y1 = self._getCurrentPoint()
        x2, y2 = point

        if x1 < x and x2 < x:
            return
        if y1 < y and y2 < y:
            return
        if y1 >= y and y2 >= y:
            return

        dx = x2 - x1
        dy = y2 - y1
        t = (y - y1) / dy
        ix = dx * t + x1
        if ix < x:
            return
        self._addIntersection(y2 > y1)

    def _curveToOne(self, bcp1, bcp2, point):
        x, y = self.testPoint
        x1, y1 = self._getCurrentPoint()
        x2, y2 = bcp1
        x3, y3 = bcp2
        x4, y4 = point

        if x1 < x and x2 < x and x3 < x and x4 < x:
            return
        if y1 < y and y2 < y and y3 < y and y4 < y:
            return
        if y1 >= y and y2 >= y and y3 >= y and y4 >= y:
            return

        dy = y1
        cy = (y2 - dy) * 3.0
        by = (y3 - y2) * 3.0 - cy
        ay = y4 - dy - cy - by
        solutions = sorted(solveCubic(ay, by, cy, dy - y))
        solutions = [t for t in solutions if -0.0 <= t <= 1.0]
        if not solutions:
            return

        dx = x1
        cx = (x2 - dx) * 3.0
        bx = (x3 - x2) * 3.0 - cx
        ax = x4 - dx - cx - bx

        above = y1 >= y
        lastT = None
        for t in solutions:
            if t == lastT:
                continue
            lastT = t
            t2 = t * t
            t3 = t2 * t

            direction = 3 * ay * t2 + 2 * by * t + cy
            incomingGoingUp = outgoingGoingUp = direction > 0.0
            if direction == 0.0:
                direction = 6 * ay * t + 2 * by
                outgoingGoingUp = direction > 0.0
                incomingGoingUp = not outgoingGoingUp
                if direction == 0.0:
                    direction = ay
                    incomingGoingUp = outgoingGoingUp = direction > 0.0

            xt = ax * t3 + bx * t2 + cx * t + dx
            if xt < x:
                continue

            if t in (0.0, -0.0):
                if not outgoingGoingUp:
                    self._addIntersection(outgoingGoingUp)
            elif t == 1.0:
                if incomingGoingUp:
                    self._addIntersection(incomingGoingUp)
            else:
                if incomingGoingUp == outgoingGoingUp:
                    self._addIntersection(outgoingGoingUp)
                # else:
                #   we're not really intersecting, merely touching

    def _qCurveToOne_unfinished(self, bcp, point):
        # XXX need to finish this, for now doing it through a cubic
        # (BasePen implements _qCurveTo in terms of a cubic) will
        # have to do.
        x, y = self.testPoint
        x1, y1 = self._getCurrentPoint()
        x2, y2 = bcp
        x3, y3 = point
        c = y1
        b = (y2 - c) * 2.0
        a = y3 - c - b
        solutions = sorted(solveQuadratic(a, b, c - y))
        solutions = [
            t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON
        ]
        if not solutions:
            return
        # XXX

    def _closePath(self):
        if self._getCurrentPoint() != self.firstPoint:
            self.lineTo(self.firstPoint)
        self.firstPoint = None

    def _endPath(self):
        """Insideness is not defined for open contours."""
        raise NotImplementedError