1
"""fontTools.pens.pointInsidePen -- Pen implementing "point inside" testing
5
from fontTools.pens.basePen import BasePen
6
from fontTools.misc.bezierTools import solveQuadratic, solveCubic
9
__all__ = ["PointInsidePen"]
12
# working around floating point errors
14
ONE_PLUS_EPSILON = 1 + EPSILON
15
ZERO_MINUS_EPSILON = 0 - EPSILON
18
class PointInsidePen(BasePen):
20
"""This pen implements "point inside" testing: to test whether
21
a given point lies inside the shape (black) or outside (white).
22
Instances of this class can be recycled, as long as the
23
setTestPoint() method is used to set the new point to test.
27
pen = PointInsidePen(glyphSet, (100, 200))
29
isInside = pen.getResult()
31
Both the even-odd algorithm and the non-zero-winding-rule
32
algorithm are implemented. The latter is the default, specify
33
True for the evenOdd argument of __init__ or setTestPoint
34
to use the even-odd algorithm.
37
# This class implements the classical "shoot a ray from the test point
38
# to infinity and count how many times it intersects the outline" (as well
39
# as the non-zero variant, where the counter is incremented if the outline
40
# intersects the ray in one direction and decremented if it intersects in
41
# the other direction).
42
# I found an amazingly clear explanation of the subtleties involved in
43
# implementing this correctly for polygons here:
44
# http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html
45
# I extended the principles outlined on that page to curves.
47
def __init__(self, glyphSet, testPoint, evenOdd=0):
48
BasePen.__init__(self, glyphSet)
49
self.setTestPoint(testPoint, evenOdd)
51
def setTestPoint(self, testPoint, evenOdd=0):
52
"""Set the point to test. Call this _before_ the outline gets drawn."""
53
self.testPoint = testPoint
54
self.evenOdd = evenOdd
55
self.firstPoint = None
56
self.intersectionCount = 0
59
"""After the shape has been drawn, getResult() returns True if the test
60
point lies within the (black) shape, and False if it doesn't.
62
if self.firstPoint is not None:
63
# always make sure the sub paths are closed; the algorithm only works
67
result = self.intersectionCount % 2
69
result = self.intersectionCount
72
def _addIntersection(self, goingUp):
73
if self.evenOdd or goingUp:
74
self.intersectionCount += 1
76
self.intersectionCount -= 1
78
def _moveTo(self, point):
79
if self.firstPoint is not None:
80
# always make sure the sub paths are closed; the algorithm only works
83
self.firstPoint = point
85
def _lineTo(self, point):
87
x1, y1 = self._getCurrentPoint()
94
if y1 >= y and y2 >= y:
99
t = float(y - y1) / dy
103
self._addIntersection(y2 > y1)
105
def _curveToOne(self, bcp1, bcp2, point):
106
x, y = self.testPoint
107
x1, y1 = self._getCurrentPoint()
112
if x1 < x and x2 < x and x3 < x and x4 < x:
114
if y1 < y and y2 < y and y3 < y and y4 < y:
116
if y1 >= y and y2 >= y and y3 >= y and y4 >= y:
121
by = (y3 - y2) * 3.0 - cy
122
ay = y4 - dy - cy - by
123
solutions = solveCubic(ay, by, cy, dy - y)
125
solutions = [t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON]
131
bx = (x3 - x2) * 3.0 - cx
132
ax = x4 - dx - cx - bx
143
direction = 3*ay*t2 + 2*by*t + cy
145
direction = 6*ay*t + 2*by
148
goingUp = direction > 0.0
150
xt = ax*t3 + bx*t2 + cx*t + dx
157
self._addIntersection(goingUp)
160
self._addIntersection(goingUp)
163
self._addIntersection(goingUp)
165
# we're not really intersecting, merely touching the 'top'
168
def _qCurveToOne_unfinished(self, bcp, point):
169
# XXX need to finish this, for now doing it through a cubic
170
# (BasePen implements _qCurveTo in terms of a cubic) will
172
x, y = self.testPoint
173
x1, y1 = self._getCurrentPoint()
179
solutions = solveQuadratic(a, b, c - y)
181
solutions = [t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON]
186
def _closePath(self):
187
if self._getCurrentPoint() != self.firstPoint:
188
self.lineTo(self.firstPoint)
189
self.firstPoint = None
added
removed
Lib/fontTools/pens/pointInsidePen.py
