153d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr"""fontTools.pens.pointInsidePen -- Pen implementing "point inside" testing 253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvrfor shapes. 353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr""" 453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 51ae29591efbb29492ce05378909ccf4028d7c1eeBehdad Esfahbodfrom __future__ import print_function, division, absolute_import 630e691edd056ba22fa8970280e986747817bec3dBehdad Esfahbodfrom fontTools.misc.py23 import * 74162de350edeb4aa09c508e5a39ac5fa20d8d619jvrfrom fontTools.pens.basePen import BasePen 84162de350edeb4aa09c508e5a39ac5fa20d8d619jvrfrom fontTools.misc.bezierTools import solveQuadratic, solveCubic 94162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 104162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 114162de350edeb4aa09c508e5a39ac5fa20d8d619jvr__all__ = ["PointInsidePen"] 124162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 134162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1405e2541b49e530a3771b5ec14eee5f956308506ajvr# working around floating point errors 1505e2541b49e530a3771b5ec14eee5f956308506ajvrEPSILON = 1e-10 1605e2541b49e530a3771b5ec14eee5f956308506ajvrONE_PLUS_EPSILON = 1 + EPSILON 1705e2541b49e530a3771b5ec14eee5f956308506ajvrZERO_MINUS_EPSILON = 0 - EPSILON 1805e2541b49e530a3771b5ec14eee5f956308506ajvr 1905e2541b49e530a3771b5ec14eee5f956308506ajvr 204162de350edeb4aa09c508e5a39ac5fa20d8d619jvrclass PointInsidePen(BasePen): 2153d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 2253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr """This pen implements "point inside" testing: to test whether 2353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr a given point lies inside the shape (black) or outside (white). 2453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr Instances of this class can be recycled, as long as the 2553d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr setTestPoint() method is used to set the new point to test. 2653d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 2753d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr Typical usage: 2853d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 2953d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr pen = PointInsidePen(glyphSet, (100, 200)) 3053d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr outline.draw(pen) 3153d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr isInside = pen.getResult() 3253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 3353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr Both the even-odd algorithm and the non-zero-winding-rule 3453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr algorithm are implemented. The latter is the default, specify 3553d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr True for the evenOdd argument of __init__ or setTestPoint 3653d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr to use the even-odd algorithm. 3753d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr """ 3853d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 3953d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # This class implements the classical "shoot a ray from the test point 4053d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # to infinity and count how many times it intersects the outline" (as well 4153d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # as the non-zero variant, where the counter is incremented if the outline 4253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # intersects the ray in one direction and decremented if it intersects in 4353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # the other direction). 4453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # I found an amazingly clear explanation of the subtleties involved in 4553d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # implementing this correctly for polygons here: 4653d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html 4753d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # I extended the principles outlined on that page to curves. 4853d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 494162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def __init__(self, glyphSet, testPoint, evenOdd=0): 504162de350edeb4aa09c508e5a39ac5fa20d8d619jvr BasePen.__init__(self, glyphSet) 514162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.setTestPoint(testPoint, evenOdd) 5253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 534162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def setTestPoint(self, testPoint, evenOdd=0): 5453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr """Set the point to test. Call this _before_ the outline gets drawn.""" 554162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.testPoint = testPoint 564162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.evenOdd = evenOdd 574162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.firstPoint = None 584162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.intersectionCount = 0 594162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 604162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def getResult(self): 6153d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr """After the shape has been drawn, getResult() returns True if the test 6253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr point lies within the (black) shape, and False if it doesn't. 6353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr """ 644162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if self.firstPoint is not None: 6553d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # always make sure the sub paths are closed; the algorithm only works 6653d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # for closed paths. 674162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.closePath() 684162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if self.evenOdd: 694162de350edeb4aa09c508e5a39ac5fa20d8d619jvr result = self.intersectionCount % 2 704162de350edeb4aa09c508e5a39ac5fa20d8d619jvr else: 714162de350edeb4aa09c508e5a39ac5fa20d8d619jvr result = self.intersectionCount 724162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return not not result 7353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 744162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _addIntersection(self, goingUp): 754162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if self.evenOdd or goingUp: 764162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.intersectionCount += 1 774162de350edeb4aa09c508e5a39ac5fa20d8d619jvr else: 784162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.intersectionCount -= 1 7953d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 804162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _moveTo(self, point): 814162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if self.firstPoint is not None: 8253d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # always make sure the sub paths are closed; the algorithm only works 8353d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr # for closed paths. 844162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.closePath() 854162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.firstPoint = point 8653d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 874162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _lineTo(self, point): 884162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x, y = self.testPoint 894162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x1, y1 = self._getCurrentPoint() 904162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x2, y2 = point 914162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 924162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if x1 < x and x2 < x: 934162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 944162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if y1 < y and y2 < y: 954162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 964162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if y1 >= y and y2 >= y: 974162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 9853d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 994162de350edeb4aa09c508e5a39ac5fa20d8d619jvr dx = x2 - x1 1004162de350edeb4aa09c508e5a39ac5fa20d8d619jvr dy = y2 - y1 10132c10eecffb4923e0721c395e4b80fb732543f18Behdad Esfahbod t = (y - y1) / dy 1024162de350edeb4aa09c508e5a39ac5fa20d8d619jvr ix = dx * t + x1 1034162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if ix < x: 1044162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 1054162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self._addIntersection(y2 > y1) 1064162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1074162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _curveToOne(self, bcp1, bcp2, point): 1084162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x, y = self.testPoint 1094162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x1, y1 = self._getCurrentPoint() 1104162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x2, y2 = bcp1 1114162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x3, y3 = bcp2 1124162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x4, y4 = point 1134162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1144162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if x1 < x and x2 < x and x3 < x and x4 < x: 1154162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 1164162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if y1 < y and y2 < y and y3 < y and y4 < y: 1174162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 1184162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if y1 >= y and y2 >= y and y3 >= y and y4 >= y: 1194162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 12053d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 1214162de350edeb4aa09c508e5a39ac5fa20d8d619jvr dy = y1 1224162de350edeb4aa09c508e5a39ac5fa20d8d619jvr cy = (y2 - dy) * 3.0 1234162de350edeb4aa09c508e5a39ac5fa20d8d619jvr by = (y3 - y2) * 3.0 - cy 1244162de350edeb4aa09c508e5a39ac5fa20d8d619jvr ay = y4 - dy - cy - by 125ac1b4359467ca3deab03186a15eae1d55eb35567Behdad Esfahbod solutions = sorted(solveCubic(ay, by, cy, dy - y)) 12605e2541b49e530a3771b5ec14eee5f956308506ajvr solutions = [t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON] 1274162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if not solutions: 1284162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 1294162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1304162de350edeb4aa09c508e5a39ac5fa20d8d619jvr dx = x1 1314162de350edeb4aa09c508e5a39ac5fa20d8d619jvr cx = (x2 - dx) * 3.0 1324162de350edeb4aa09c508e5a39ac5fa20d8d619jvr bx = (x3 - x2) * 3.0 - cx 1334162de350edeb4aa09c508e5a39ac5fa20d8d619jvr ax = x4 - dx - cx - bx 13453d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 1354162de350edeb4aa09c508e5a39ac5fa20d8d619jvr above = y1 >= y 1364162de350edeb4aa09c508e5a39ac5fa20d8d619jvr lastT = None 1374162de350edeb4aa09c508e5a39ac5fa20d8d619jvr for t in solutions: 1384162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if t == lastT: 1394162de350edeb4aa09c508e5a39ac5fa20d8d619jvr continue 1404162de350edeb4aa09c508e5a39ac5fa20d8d619jvr lastT = t 1414162de350edeb4aa09c508e5a39ac5fa20d8d619jvr t2 = t * t 1424162de350edeb4aa09c508e5a39ac5fa20d8d619jvr t3 = t2 * t 1434162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1444162de350edeb4aa09c508e5a39ac5fa20d8d619jvr direction = 3*ay*t2 + 2*by*t + cy 1454162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if direction == 0.0: 1464162de350edeb4aa09c508e5a39ac5fa20d8d619jvr direction = 6*ay*t + 2*by 1474162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if direction == 0.0: 1484162de350edeb4aa09c508e5a39ac5fa20d8d619jvr direction = ay 1494162de350edeb4aa09c508e5a39ac5fa20d8d619jvr goingUp = direction > 0.0 1504162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1514162de350edeb4aa09c508e5a39ac5fa20d8d619jvr xt = ax*t3 + bx*t2 + cx*t + dx 1524162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if xt < x: 1534162de350edeb4aa09c508e5a39ac5fa20d8d619jvr above = goingUp 1544162de350edeb4aa09c508e5a39ac5fa20d8d619jvr continue 1554162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1564162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if t == 0.0: 1574162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if not goingUp: 1584162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self._addIntersection(goingUp) 1594162de350edeb4aa09c508e5a39ac5fa20d8d619jvr elif t == 1.0: 1604162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if not above: 1614162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self._addIntersection(goingUp) 1624162de350edeb4aa09c508e5a39ac5fa20d8d619jvr else: 1634162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if above != goingUp: 1644162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self._addIntersection(goingUp) 1654162de350edeb4aa09c508e5a39ac5fa20d8d619jvr #else: 1664162de350edeb4aa09c508e5a39ac5fa20d8d619jvr # we're not really intersecting, merely touching the 'top' 1674162de350edeb4aa09c508e5a39ac5fa20d8d619jvr above = goingUp 1684162de350edeb4aa09c508e5a39ac5fa20d8d619jvr 1694162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _qCurveToOne_unfinished(self, bcp, point): 1704162de350edeb4aa09c508e5a39ac5fa20d8d619jvr # XXX need to finish this, for now doing it through a cubic 1714162de350edeb4aa09c508e5a39ac5fa20d8d619jvr # (BasePen implements _qCurveTo in terms of a cubic) will 1724162de350edeb4aa09c508e5a39ac5fa20d8d619jvr # have to do. 1734162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x, y = self.testPoint 1744162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x1, y1 = self._getCurrentPoint() 1754162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x2, y2 = bcp 1764162de350edeb4aa09c508e5a39ac5fa20d8d619jvr x3, y3 = point 1774162de350edeb4aa09c508e5a39ac5fa20d8d619jvr c = y1 1784162de350edeb4aa09c508e5a39ac5fa20d8d619jvr b = (y2 - c) * 2.0 1794162de350edeb4aa09c508e5a39ac5fa20d8d619jvr a = y3 - c - b 180ac1b4359467ca3deab03186a15eae1d55eb35567Behdad Esfahbod solutions = sorted(solveQuadratic(a, b, c - y)) 18105e2541b49e530a3771b5ec14eee5f956308506ajvr solutions = [t for t in solutions if ZERO_MINUS_EPSILON <= t <= ONE_PLUS_EPSILON] 1824162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if not solutions: 1834162de350edeb4aa09c508e5a39ac5fa20d8d619jvr return 1844162de350edeb4aa09c508e5a39ac5fa20d8d619jvr XXX 18553d7523c1c36caf25e72c7a4ab0f9d18d594b895jvr 1864162de350edeb4aa09c508e5a39ac5fa20d8d619jvr def _closePath(self): 1874162de350edeb4aa09c508e5a39ac5fa20d8d619jvr if self._getCurrentPoint() != self.firstPoint: 1884162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.lineTo(self.firstPoint) 1894162de350edeb4aa09c508e5a39ac5fa20d8d619jvr self.firstPoint = None 1903a98ae5baf9ebff980f02eacb4ce8509503824a2jvr 1913a98ae5baf9ebff980f02eacb4ce8509503824a2jvr _endPath = _closePath 192