pointInsidePen.py revision 3a98ae5baf9ebff980f02eacb4ce8509503824a2 
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 = solveCubic(ay, by, cy, dy - y)
124		solutions.sort()
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 = solveQuadratic(a, b, c - y)
180		solutions.sort()
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