Adjacent shapes: any way to detect them?
-
I'm writing code to cycle through every valid combination of shapes in a modular script system I've reconstructed from a script André Gürtler drew for the cover of TM/RSI/SGM in 1966.
The rules of the script are that every glyph can be made of no more than two shapes, and that the shapes cannot intersect or touch.
The code I'm writing cycles through and draws each shape by itself, and will also generate a list of every unique pair of non-repeating shapes—so that if the list were (1, 2, 3) it would return ((1, 2), (1, 3), (2, 3)).
But before drawing a given pair, the code has to test to see if its shapes intersect or touch. Testing intersection is easy—thanks to intersectionPoints()!—but touching is harder. The paths of two shapes drawn right next to each other do not actually 'touch' or overlap in any way that
intersection() or intersectionPoints() can detect—see below.
So, is there any way to tell when shapes are close like this that anyone knows of? I could just write out a list of forbidden pairs to compare each generated pair against, but I'd rather test dynamically (a) because it's a more elegant solution and (b) in case I redefine the shapes later.
-
@mauricemeilleur This is what the matrix looks like, by the way; the circular shapes include multiple combinations of partial arcs, hence the need to test for 'adjacency' as well as intersection.
-
finding touching shapes are really difficult...
On point level it can be done easily. Even on line segment level it can be done, but when handling curves touching its hard...
Maybe the best solution is to calculate extreme points for each shape and test those. (not only the bounds of a shape but the extremes where left/right and top/bottom direction are changing.
good luck!!
-
@mauricemeilleur Maybe move things closer by some small value, if they then intersect, assume they touch in the unmoved position.
-
Thanks, you two. I'll try Frederik's extreme points idea after, but Just's idea might be the easiest solution: pick one of the two shapes, move the control points one pixel up/down and left/right, and test for intersection points with each move. I tried a side sketch and that set of points becomes non-empty as soon as you move a shape like that in an 'adjacent' pair.
-
Oops: the anchors, not the control points.
-
@frederik @justvanrossum Following up on Just's suggestion: what's the easiest way to shift the shape?
translate() won't work, obviously, because I need to keep an absolute position reference. I see a transform() function in the manual, but I don't understand the syntax:
transform(transformMatrix, center=(0, 0))
Transform a path with a transform matrix (xy, xx, yy, yx, x, y).Is there another way to directly edit the points in a path to move the path +/- 1px on both x and y axes? My thinking is I'd revise my compareShapes() function to add this test: shift one of the two shapes in all four directions and retest for shared points and intersectionPoints() each time.
-
I dont understand your initial problem:
you would like to shift a
bezierPathobject? or draw it shifted.path = BezierPath() path.rect(0, 0, 100, 100) # move the canvas where to draw the path # the path object is untouched translate(100, 100) drawPath(path)path = BezierPath() path.rect(0, 0, 100, 100) # move the content of the path # this will change the points inside the path path.translate(100, 100) drawPath(path)bezierPath.transformaccepts a transformation matrix. For 2D its a tuple of six describing translate, rotation, scale, skew, ...from fontTools.misc.transform import Transform import math t = Transform().translate(10, 10) print(tuple(t)) t = Transform().rotate(math.radians(45)) print(tuple(t)) t = Transform().scale(.5, 2) print(tuple(t))hope this helps
-
It did! In the process of explaining myself better with a small sketch I realized I'd had a very mistaken notion of the consequences of calling translate().
canvas = 500 shape = canvas/2 shift = 250 newPage(canvas, canvas) fill(1) rect(0, 0, canvas, canvas) translate(canvas/2, canvas/2) fill(0, .25) p1 = BezierPath() p1.rect(-shape, -shape/2, shape, shape) drawPath(p1) p2 = BezierPath() p2.oval(-shape + shift, -shape/2, shape, shape) p2.translate(-1, -1) drawPath(p2) p3 = BezierPath() p3 = p1.intersection(p2) print(len(p1.intersectionPoints(p2)))
I was trying to create a test to see if two shapes were 'adjacent'—not overlapping or have any shared points, those are easy to test for, but literally next to one another, 'touching' so to speak.You can see in the code that without the translate() call
print(len(p1.intersectionPoints(p2)))would print '0'. For some reason I thought translating a path would only change its apparent position on the canvas, but somehow its absolute position would stay the same, so that there would never be any intersection points between the shapes unless I literally changed where I was defining the circle.
So now for my test I can check for shared points and intersecting points, then translate one of the shapes 1 pixel in all four directions and check again each translation. As Just suggested above, if one of those shifts causes the tests to fail, I can assume that the shapes were 'touching' to begin with.
As soon as the larger project this is all a part of is ready, I'll post it here and you'll see what I'm up to.
-
@frederik @justvanrossum Here's the final code with a fully working test. The code defines a design space with 45 shapes (some of which are subsets of larger shapes). The code draws each shape, then draws each unique pair of shapes whose members don't 'touch' and don't overlap.
from itertools import combinations canvasX = 750 canvasY = canvasX * 1.25 u = (canvasX/50) def c1(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) c.closePath() return c def c1t(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u - (9 * u), -8 * u, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c1ti(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u + (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u + (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u - (9 * u), 7 * u, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c1b(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u - (9 * u), 0, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c1bi(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u - (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u - (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u - (9 * u), -8 * u - (7 * u), 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c1r(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u - (9 * u), -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c1l(): c = BezierPath() c.oval(-8 * u - (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u - (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-(9 * u), -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c2(): c = BezierPath() c.oval(-8 * u, -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) c.closePath() return c def c2t(): c = BezierPath() c.oval(-8 * u, -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -8 * u, 16 * u, 8.5 * u) c = c.difference(r) c.closePath() return c def c2ti(): c = BezierPath() c.oval(-8 * u, -8 * u + (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u + (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, 7 * u, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c2b(): c = BezierPath() c.oval(-8 * u, -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -.5 * u, 16 * u, 8.5 * u) c = c.difference(r) c.closePath() return c def c2bi(): c = BezierPath() c.oval(-8 * u, -8 * u - (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -8 * u - (7 * u), 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c2r(): c = BezierPath() c.oval(-8 * u, -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c2l(): c = BezierPath() c.oval(-8 * u, -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(0, -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c3(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) c.closePath() return c def c3t(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u + (9 * u), -8 * u, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c3ti(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u + (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u + (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u + (9 * u), 7 * u, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c3b(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u + (9 * u), 0, 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c3bi(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u - (7 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u - (7 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u + (9 * u), -8 * u - (7 * u), 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c3r(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u + (9 * u), -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c3l(): c = BezierPath() c.oval(-8 * u + (9 * u), -8 * u, 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u + (9 * u), -7 * u, 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(9 * u, -8 * u, 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c4(): c = BezierPath() c.oval(-8 * u, -8 * u - (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) c.closePath() return c def c4t(): c = BezierPath() c.oval(-8 * u, -8 * u - (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -8 * u - (17 * u), 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c4b(): c = BezierPath() c.oval(-8 * u, -8 * u - (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -(17 * u), 16 * u, 8 * u) c = c.difference(r) c.closePath() return c def c4r(): c = BezierPath() c.oval(-8 * u, -8 * u - (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(-8 * u, -8 * u - (17 * u), 8 * u, 16 * u) c = c.difference(r) c.closePath() return c def c4l(): c = BezierPath() c.oval(-8 * u, -8 * u - (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u - (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) r = BezierPath() r.rect(0, -8 * u - (17 * u), 8 * u, 16 * u) c = c.difference(r) c.closePath() return c """ def c5(): #may not be needed c = BezierPath() c.oval(-8 * u, -8 * u + (17 * u), 16 * u, 16 * u) ch = BezierPath() ch.oval(-7 * u, -7 * u + (17 * u), 14 * u, 14 * u) ch.closePath() c = c.difference(ch) c.closePath() return c """ def b1m(): b = BezierPath() b.rect(-12 * u, -7 * u, u, 14 * u) b.closePath() return b def b1t(): b = BezierPath() b.rect(-12 * u, -7 * u, u, 22 * u) b.closePath() return b def b1b(): b = BezierPath() b.rect(-12 * u, -15 * u, u, 22 * u) b.closePath() return b def b2m(): b = BezierPath() b.rect(-u/2, -7 * u, u, 14 * u) b.closePath() return b def b2t(): b = BezierPath() b.rect(-u/2, -7 * u, u, 22 * u) b.closePath() return b def b2b(): b = BezierPath() b.rect(-u/2, -15 * u, u, 22 * u) b.closePath() return b def b3m(): b = BezierPath() b.rect(11 * u, -7 * u, u, 14 * u) b.closePath() return b def b3t(): b = BezierPath() b.rect(11 * u, -7 * u, u, 22 * u) b.closePath() return b def b3b(): b = BezierPath() b.rect(11 * u, -15 * u, u, 22 * u) b.closePath() return b def b4r(): b = BezierPath() b.rect(0, -u/2, 8 * u, u) b.closePath() return b def b4l(): b = BezierPath() b.rect(-8 * u, -u/2, 8 * u, u) b.closePath() return b def b5(): b = BezierPath() b.rect(-8 * u, 9 * u, 16 * u, u) b.closePath() return b def b6(): b = BezierPath() b.rect(-8 * u, -10 * u, 16 * u, u) b.closePath() return b def a1(): a = BezierPath() a.moveTo((-9 * u, 7 * u)) a.lineTo((-9 * u + (12.7017059 * u), -15 * u)) a.lineTo(( -9 * u + (12.7017059 * u) - (u * cos(radians(30))), -15 * u - (u * sin(radians(30))) )) a.lineTo(( -9 * u - (u * cos(radians(30))), 7 * u - (u * sin(radians(30))) )) a.closePath() return a def a1s(): a = BezierPath() a.moveTo((-9 * u, 7 * u)) a.lineTo((-9 * u + (8.0829037 * u), -7 * u)) a.lineTo(( -9 * u + (8.0829037 * u) - (u * cos(radians(30))), -7 * u - (u * sin(radians(30))) )) a.lineTo(( -9 * u - (u * cos(radians(30))), 7 * u - (u * sin(radians(30))) )) a.closePath() return a def a1si(): a = BezierPath() a.moveTo((-9 * u, -7 * u)) a.lineTo((-9 * u + (8.0829037 * u), 7 * u)) a.lineTo(( -9 * u + (8.0829037 * u) - (u * cos(radians(30))), 7 * u + (u * sin(radians(30))) )) a.lineTo(( -9 * u - (u * cos(radians(30))), -7 * u + (u * sin(radians(30))) )) a.closePath() return a def a2(): a = BezierPath() a.moveTo((9 * u, 7 * u)) a.lineTo((9 * u - (12.7017059 * u), -15 * u)) a.lineTo(( 9 * u - (12.7017059 * u) + (u * cos(radians(30))), -15 * u - (u * sin(radians(30))) )) a.lineTo(( 9 * u + (u * cos(radians(30))), 7 * u - (u * sin(radians(30))) )) a.closePath() return a def a2s(): a = BezierPath() a.moveTo((9 * u, 7 * u)) a.lineTo((9 * u - (8.0829037 * u), -7 * u)) a.lineTo(( 9 * u - (8.0829037 * u) + (u * cos(radians(30))), -7 * u - (u * sin(radians(30))) )) a.lineTo(( 9 * u + (u * cos(radians(30))), 7 * u - (u * sin(radians(30))) )) a.closePath() return a def a2si(): a = BezierPath() a.moveTo((9 * u, -7 * u)) a.lineTo((9 * u - (8.0829037 * u), 7 * u)) a.lineTo(( 9 * u - (8.0829037 * u) + (u * cos(radians(30))), 7 * u + (u * sin(radians(30))) )) a.lineTo(( 9 * u + (u * cos(radians(30))), -7 * u + (u * sin(radians(30))) )) a.closePath() return a matrix = [c1, c1t, c1ti, c1b, c1bi, c1r, c1l, c2, c2t, c2ti, c2b, c2bi, c2r, c2l, c3, c3t, c3ti, c3b, c3bi, c3r, c3l, c4, c4t, c4b, c4r, c4l, b1m, b1t, b1b, b2m, b2t, b2b, b3m, b3t, b3b, b4r, b4l, b5, b6, a1, a1s, a1si, a2, a2s, a2si] pairs = [] def compareShape(s1, s2): s1n = s1.copy() s1n.translate(0, 1) s1s = s1.copy() s1s.translate(0, -1) s1e = s1.copy() s1e.translate(1, 0) s1w = s1.copy() s1w.translate(-1, 0) if len(set(s1.points) & set(s2.points)) == 0 and len(s1.intersectionPoints(s2)) == 0 and len(s1n.intersectionPoints(s2)) == 0 and len(s1s.intersectionPoints(s2)) == 0 and len(s1e.intersectionPoints(s2)) == 0 and len(s1w.intersectionPoints(s2)) == 0: newPage(canvasX, canvasY) frameDuration(1/3) fill(1) rect(0, 0, canvasX, canvasY) translate(canvasX/2, canvasY/2) fill(0, .05) for l in range(len(matrix)): mat = BezierPath() mat = matrix[l]() drawPath(mat) fill(0) drawPath(s1) drawPath(s2) for m in range(len(matrix)): newPage(canvasX, canvasY) frameDuration(1/3) fill(1) rect(0, 0, canvasX, canvasY) translate(canvasX/2, canvasY/2) fill(0, .05) for l in range(len(matrix)): mat = BezierPath() mat = matrix[l]() drawPath(mat) fill(0) single = BezierPath() single = matrix[m]() drawPath(single) for subset in combinations(matrix, 2): pairs.append(subset) for n in range(len(pairs)): compareShape(pairs[n][0](), pairs[n][1]()) #saveImage('~/Desktop/gürtler_script_matrix.pdf')
