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