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