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