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
14class PointInsidePen(BasePen):
15
16	"""This pen implements "point inside" testing: to test whether
17	a given point lies inside the shape (black) or outside (white).
18	Instances of this class can be recycled, as long as the
19	setTestPoint() method is used to set the new point to test.
20
21	Typical usage:
22
23		pen = PointInsidePen(glyphSet, (100, 200))
24		outline.draw(pen)
25		isInside = pen.getResult()
26
27	Both the even-odd algorithm and the non-zero-winding-rule
28	algorithm are implemented. The latter is the default, specify
29	True for the evenOdd argument of __init__ or setTestPoint
30	to use the even-odd algorithm.
31	"""
32
33	# This class implements the classical "shoot a ray from the test point
34	# to infinity and count how many times it intersects the outline" (as well
35	# as the non-zero variant, where the counter is incremented if the outline
36	# intersects the ray in one direction and decremented if it intersects in
37	# the other direction).
38	# I found an amazingly clear explanation of the subtleties involved in
39	# implementing this correctly for polygons here:
40	#   http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html
41	# I extended the principles outlined on that page to curves.
42
43	def __init__(self, glyphSet, testPoint, evenOdd=False):
44		BasePen.__init__(self, glyphSet)
45		self.setTestPoint(testPoint, evenOdd)
46
47	def setTestPoint(self, testPoint, evenOdd=False):
48		"""Set the point to test. Call this _before_ the outline gets drawn."""
49		self.testPoint = testPoint
50		self.evenOdd = evenOdd
51		self.firstPoint = None
52		self.intersectionCount = 0
53
54	def getWinding(self):
55		if self.firstPoint is not None:
56			# always make sure the sub paths are closed; the algorithm only works
57			# for closed paths.
58			self.closePath()
59		return self.intersectionCount
60
61	def getResult(self):
62		"""After the shape has been drawn, getResult() returns True if the test
63		point lies within the (black) shape, and False if it doesn't.
64		"""
65		winding = self.getWinding()
66		if self.evenOdd:
67			result = winding % 2
68		else: # non-zero
69			result = self.intersectionCount != 0
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 = (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 -0. <= t <= 1.]
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			incomingGoingUp = outgoingGoingUp = direction > 0.0
144			if direction == 0.0:
145				direction = 6*ay*t + 2*by
146				outgoingGoingUp = direction > 0.0
147				incomingGoingUp = not outgoingGoingUp
148				if direction == 0.0:
149					direction = ay
150					incomingGoingUp = outgoingGoingUp = direction > 0.0
151
152			xt = ax*t3 + bx*t2 + cx*t + dx
153			if xt < x:
154				continue
155
156			if t in (0.0, -0.0):
157				if not outgoingGoingUp:
158					self._addIntersection(outgoingGoingUp)
159			elif t == 1.0:
160				if incomingGoingUp:
161					self._addIntersection(incomingGoingUp)
162			else:
163				if incomingGoingUp == outgoingGoingUp:
164					self._addIntersection(outgoingGoingUp)
165				#else:
166				#   we're not really intersecting, merely touching
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	def _endPath(self):
191		"""Insideness is not defined for open contours."""
192		raise NotImplementedError
193