1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
from robofab.pens.filterPen import flattenGlyph
from robofab.objects.objectsRF import RGlyph as _RGlyph
import math
_EPSILON = 1e-15
def normalise(a1, a2):
"""Normalise this vector to length 1"""
n = math.sqrt((a1*a1)+(a2*a2))
return (a1/n, a2/n)
def inbetween((a1, a2), (b1, b2), (c1, c2)):
"""Return True if point b is in between points a and c."""
x = (a1-_EPSILON<=b1<=c1+_EPSILON) or (a1+_EPSILON>=b1>=c1-_EPSILON)
y = (a2-_EPSILON<=b2<=c2+_EPSILON) or (a2+_EPSILON>=b2>=c2-_EPSILON)
return x == y == True
def sectlines((a1, a2), (p1, p2), (b1, b2), (q1, q2)):
'''Calculate the intersection point of two straight lines. Result in floats.'''
if (a1, a2) == (p1, p2):
return None
r1 = a1-p1
r2 = a2-p2
r1, r2 = normalise(r1, r2)
s1 = b1-q1
s2 = b2-q2
s1, s2 = normalise(s1, s2)
f = float(s1*r2 - s2*r1)
if f == 0:
return None
mu = (r1*(q2 - p2) + r2*(p1 - q1)) / f
m1 = mu*s1 + q1
m2 = mu*s2 + q2
if (m1, m2) == (a1, a2):
return None
if inbetween((a1, a2), (m1, m2), (p1,p2)) and inbetween((b1, b2), (m1, m2), (q1,q2)):
return m1, m2
else:
return None
def _makeFlat(aGlyph, segmentLength = 10):
"""Helper function to flatten the glyph with a given approximate segment length."""
return flattenGlyph(aGlyph, segmentLength)
def intersect(aGlyph, startPt, endPt, segmentLength=10):
"""Find the intersections between a glyph and a straight line."""
flat = _makeFlat(aGlyph)
return _intersect(flat, startPt, endPt, segmentLength)
def _intersect(flat, startPt, endPt, segmentLength=10):
"""Find the intersections between a flattened glyph and a straight line."""
if len(flat.contours) == 0:
return None
if startPt == endPt:
return None
sect = None
intersections = {}
# new contains the flattened outline
for c in flat:
l =len(c.points)
for i in range(l):
cur = c.points[i]
next = c.points[(i+1)%l]
sect = sectlines((cur.x, cur.y), (next.x, next.y), startPt, endPt)
if sect is None:
continue
intersections[sect] = 1
return intersections.keys()
def intersectGlyphs(glyphA, glyphB, segmentLength=10):
"""Approximate the intersection points between two glyphs by
flattening both glyphs and checking each tiny segment for
intersections. Slow, but perhaps more realistic then
solving the equasions.
Seems to work for basic curves and straights, but untested
for edges cases, alsmost hits, near hits, double points, crap like that.
"""
flatA = _makeFlat(glyphA)
flatB = _makeFlat(glyphB)
intersections = []
for c in flatA:
l =len(c.points)
for i in range(l):
cur = c.points[i]
next = c.points[(i+1)%l]
sect = _intersect(flatB, (cur.x, cur.y), (next.x, next.y))
if sect is None:
continue
intersections = intersections + sect
return intersections
def makeTestGlyph():
g = _RGlyph()
pen = g.getPen()
pen.moveTo((100, 100))
pen.lineTo((800, 100))
pen.curveTo((1000, 300), (1000, 600), (800, 800))
pen.lineTo((100, 800))
pen.lineTo((100, 100))
pen.closePath()
return g
if __name__ == "__main__":
g = makeTestGlyph()
print intersect(g, (-10, 200), (650, 150))
print intersect(g, (100, 100), (600, 600))
|
