pointInsidePen.py revision 4162de350edeb4aa09c508e5a39ac5fa20d8d619 
1from fontTools.pens.basePen import BasePen
2from fontTools.misc.bezierTools import solveQuadratic, solveCubic
3
4
5__all__ = ["PointInsidePen"]
6
7
8class PointInsidePen(BasePen):
9
10	def __init__(self, glyphSet, testPoint, evenOdd=0):
11		BasePen.__init__(self, glyphSet)
12		self.setTestPoint(testPoint, evenOdd)
13
14	def setTestPoint(self, testPoint, evenOdd=0):
15		self.testPoint = testPoint
16		self.evenOdd = evenOdd
17		self.firstPoint = None
18		self.intersectionCount = 0
19
20	def getResult(self):
21		if self.firstPoint is not None:
22			self.closePath()
23		if self.evenOdd:
24			result = self.intersectionCount % 2
25		else:
26			result = self.intersectionCount
27		return not not result
28
29	def _addIntersection(self, goingUp):
30		if self.evenOdd or goingUp:
31			self.intersectionCount += 1
32		else:
33			self.intersectionCount -= 1
34
35	def _moveTo(self, point):
36		if self.firstPoint is not None:
37			self.closePath()
38		self.firstPoint = point
39
40	def _lineTo(self, point):
41		# An amazingly clear explanation of the problem:
42		# http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html
43		x, y = self.testPoint
44		x1, y1 = self._getCurrentPoint()
45		x2, y2 = point
46
47		if x1 < x and x2 < x:
48			return
49		if y1 < y and y2 < y:
50			return
51		if y1 >= y and y2 >= y:
52			return
53
54		dx = x2 - x1
55		dy = y2 - y1
56		t = float(y - y1) / dy
57		ix = dx * t + x1
58		if ix < x:
59			return
60		self._addIntersection(y2 > y1)
61
62	def _curveToOne(self, bcp1, bcp2, point):
63		x, y = self.testPoint
64		x1, y1 = self._getCurrentPoint()
65		x2, y2 = bcp1
66		x3, y3 = bcp2
67		x4, y4 = point
68
69		if x1 < x and x2 < x and x3 < x and x4 < x:
70			return
71		if y1 < y and y2 < y and y3 < y and y4 < y:
72			return
73		if y1 >= y and y2 >= y and y3 >= y and y4 >= y:
74			return
75
76		dy = y1
77		cy = (y2 - dy) * 3.0
78		by = (y3 - y2) * 3.0 - cy
79		ay = y4 - dy - cy - by
80		solutions = solveCubic(ay, by, cy, dy - y)
81		solutions.sort()
82		solutions = [t for t in solutions if 0 <= t <= 1]
83		if not solutions:
84			return
85
86		dx = x1
87		cx = (x2 - dx) * 3.0
88		bx = (x3 - x2) * 3.0 - cx
89		ax = x4 - dx - cx - bx
90
91		above = y1 >= y
92		lastT = None
93		for t in solutions:
94			if t == lastT:
95				continue
96			lastT = t
97			t2 = t * t
98			t3 = t2 * t
99
100			direction = 3*ay*t2 + 2*by*t + cy
101			if direction == 0.0:
102				direction = 6*ay*t + 2*by
103				if direction == 0.0:
104					direction = ay
105			goingUp = direction > 0.0
106
107			xt = ax*t3 + bx*t2 + cx*t + dx
108			if xt < x:
109				above = goingUp
110				continue
111
112			if t == 0.0:
113				if not goingUp:
114					self._addIntersection(goingUp)
115			elif t == 1.0:
116				if not above:
117					self._addIntersection(goingUp)
118			else:
119				if above != goingUp:
120					self._addIntersection(goingUp)
121				#else:
122				#   we're not really intersecting, merely touching the 'top'
123			above = goingUp
124
125	def _qCurveToOne_unfinished(self, bcp, point):
126		# XXX need to finish this, for now doing it through a cubic
127		# (BasePen implements _qCurveTo in terms of a cubic) will
128		# have to do.
129		x, y = self.testPoint
130		x1, y1 = self._getCurrentPoint()
131		x2, y2 = bcp
132		x3, y3 = point
133		c = y1
134		b = (y2 - c) * 2.0
135		a = y3 - c - b
136		solutions = solveQuadratic(a, b, c - y)
137		solutions.sort()
138		solutions = [t for t in solutions if 0 <= t <= 1]
139		if not solutions:
140			return
141		XXX
142
143	def _closePath(self):
144		if self._getCurrentPoint() != self.firstPoint:
145			self.lineTo(self.firstPoint)
146		self.firstPoint = None
147