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