1"""fontTools.pens.pointInsidePen -- Pen implementing "point inside" testing 2for shapes. 3""" 4 5from fontTools.pens.basePen import BasePen 6from fontTools.misc.bezierTools import solveQuadratic, solveCubic 7 8 9__all__ = ["PointInsidePen"] 10 11 12class PointInsidePen(BasePen): 13 """This pen implements "point inside" testing: to test whether 14 a given point lies inside the shape (black) or outside (white). 15 Instances of this class can be recycled, as long as the 16 setTestPoint() method is used to set the new point to test. 17 18 Typical usage: 19 20 pen = PointInsidePen(glyphSet, (100, 200)) 21 outline.draw(pen) 22 isInside = pen.getResult() 23 24 Both the even-odd algorithm and the non-zero-winding-rule 25 algorithm are implemented. The latter is the default, specify 26 True for the evenOdd argument of __init__ or setTestPoint 27 to use the even-odd algorithm. 28 """ 29 30 # This class implements the classical "shoot a ray from the test point 31 # to infinity and count how many times it intersects the outline" (as well 32 # as the non-zero variant, where the counter is incremented if the outline 33 # intersects the ray in one direction and decremented if it intersects in 34 # the other direction). 35 # I found an amazingly clear explanation of the subtleties involved in 36 # implementing this correctly for polygons here: 37 # http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html 38 # I extended the principles outlined on that page to curves. 39 40 def __init__(self, glyphSet, testPoint, evenOdd=False): 41 BasePen.__init__(self, glyphSet) 42 self.setTestPoint(testPoint, evenOdd) 43 44 def setTestPoint(self, testPoint, evenOdd=False): 45 """Set the point to test. Call this _before_ the outline gets drawn.""" 46 self.testPoint = testPoint 47 self.evenOdd = evenOdd 48 self.firstPoint = None 49 self.intersectionCount = 0 50 51 def getWinding(self): 52 if self.firstPoint is not None: 53 # always make sure the sub paths are closed; the algorithm only works 54 # for closed paths. 55 self.closePath() 56 return self.intersectionCount 57 58 def getResult(self): 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. 61 """ 62 winding = self.getWinding() 63 if self.evenOdd: 64 result = winding % 2 65 else: # non-zero 66 result = self.intersectionCount != 0 67 return not not result 68 69 def _addIntersection(self, goingUp): 70 if self.evenOdd or goingUp: 71 self.intersectionCount += 1 72 else: 73 self.intersectionCount -= 1 74 75 def _moveTo(self, point): 76 if self.firstPoint is not None: 77 # always make sure the sub paths are closed; the algorithm only works 78 # for closed paths. 79 self.closePath() 80 self.firstPoint = point 81 82 def _lineTo(self, point): 83 x, y = self.testPoint 84 x1, y1 = self._getCurrentPoint() 85 x2, y2 = point 86 87 if x1 < x and x2 < x: 88 return 89 if y1 < y and y2 < y: 90 return 91 if y1 >= y and y2 >= y: 92 return 93 94 dx = x2 - x1 95 dy = y2 - y1 96 t = (y - y1) / dy 97 ix = dx * t + x1 98 if ix < x: 99 return 100 self._addIntersection(y2 > y1) 101 102 def _curveToOne(self, bcp1, bcp2, point): 103 x, y = self.testPoint 104 x1, y1 = self._getCurrentPoint() 105 x2, y2 = bcp1 106 x3, y3 = bcp2 107 x4, y4 = point 108 109 if x1 < x and x2 < x and x3 < x and x4 < x: 110 return 111 if y1 < y and y2 < y and y3 < y and y4 < y: 112 return 113 if y1 >= y and y2 >= y and y3 >= y and y4 >= y: 114 return 115 116 dy = y1 117 cy = (y2 - dy) * 3.0 118 by = (y3 - y2) * 3.0 - cy 119 ay = y4 - dy - cy - by 120 solutions = sorted(solveCubic(ay, by, cy, dy - y)) 121 solutions = [t for t in solutions if -0.0 <= t <= 1.0] 122 if not solutions: 123 return 124 125 dx = x1 126 cx = (x2 - dx) * 3.0 127 bx = (x3 - x2) * 3.0 - cx 128 ax = x4 - dx - cx - bx 129 130 above = y1 >= y 131 lastT = None 132 for t in solutions: 133 if t == lastT: 134 continue 135 lastT = t 136 t2 = t * t 137 t3 = t2 * t 138 139 direction = 3 * ay * t2 + 2 * by * t + cy 140 incomingGoingUp = outgoingGoingUp = direction > 0.0 141 if direction == 0.0: 142 direction = 6 * ay * t + 2 * by 143 outgoingGoingUp = direction > 0.0 144 incomingGoingUp = not outgoingGoingUp 145 if direction == 0.0: 146 direction = ay 147 incomingGoingUp = outgoingGoingUp = direction > 0.0 148 149 xt = ax * t3 + bx * t2 + cx * t + dx 150 if xt < x: 151 continue 152 153 if t in (0.0, -0.0): 154 if not outgoingGoingUp: 155 self._addIntersection(outgoingGoingUp) 156 elif t == 1.0: 157 if incomingGoingUp: 158 self._addIntersection(incomingGoingUp) 159 else: 160 if incomingGoingUp == outgoingGoingUp: 161 self._addIntersection(outgoingGoingUp) 162 # else: 163 # we're not really intersecting, merely touching 164 165 def _qCurveToOne_unfinished(self, bcp, point): 166 # XXX need to finish this, for now doing it through a cubic 167 # (BasePen implements _qCurveTo in terms of a cubic) will 168 # have to do. 169 x, y = self.testPoint 170 x1, y1 = self._getCurrentPoint() 171 x2, y2 = bcp 172 x3, y3 = point 173 c = y1 174 b = (y2 - c) * 2.0 175 a = y3 - c - b 176 solutions = sorted(solveQuadratic(a, b, c - y)) 177 solutions = [ 178 t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON 179 ] 180 if not solutions: 181 return 182 # XXX 183 184 def _closePath(self): 185 if self._getCurrentPoint() != self.firstPoint: 186 self.lineTo(self.firstPoint) 187 self.firstPoint = None 188 189 def _endPath(self): 190 """Insideness is not defined for open contours.""" 191 raise NotImplementedError 192