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