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