Spaces:
Running
Running
File size: 6,336 Bytes
b72ab63 |
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
|