Why two intersected paths can't buildcycle in MetaPost?

Suppose that I have two path:

beginfig(0)
u:=10pt;
vardef randomcirc(expr O, r, w) =
save p,i; pair p; numeric i;
p=O+right*r;
p for i=1 upto 9: .. (p rotatedaround(O, 36i))+(uniformdeviate w, uniformdeviate w) endfor .. cycle
enddef;
path pat[];
pair p[];
p0:=(0,5u); p3:=(-8u,0);
pat0:=randomcirc(p0,8u,.5u);
pat3:=randomcirc(p3,5u,0.4u);
fill buildcycle(pat0, pat3) withcolor red;
draw pat0; draw pat3;
endfig;

why their intersection are not filled with red color?

I think it's due to the precision of MetaPost too low, how to fix it?

• ok, maybe I forget to define u:=10pt; – user19832 Jan 22 '14 at 13:34
• If I say pat4=buildcycle(pat0,pat3) and show pat4, I get (-77.10028,51.76262)..controls (-77.10014,51.76274) and (-77.10033,51.76294)..(-77.10046,51.76282)..controls (-77.1006,51.7627) and (-77.10042,51.7625)..cycle. I can't say why, but this explains why you don't see the filling. – egreg Jan 22 '14 at 14:17

It works here if I change slightly the definition of pat3, making pat3 start at the "left" (so to speak) of the circle and not at the "right" (to the contrary of pat0). For this, I defined another vardef macro (randomcirc_bis)

beginfig(0)
u:=10pt;
vardef randomcirc(expr O, r, w) =
save p,i; pair p; numeric i;
p=O+right*r;
p for i=1 upto 9: .. (p rotatedaround(O, 36i))+(uniformdeviate w, uniformdeviate w)
endfor .. cycle
enddef;
%
vardef randomcirc_bis(expr O, r, w) =
save p,i; pair p; numeric i;
p=O+left*r;
p for i=1 upto 9: .. (p rotatedaround(O, 36i))+(uniformdeviate w, uniformdeviate w)
endfor .. cycle
enddef;
%
path pat[];
pair p[];
p0:=(0,5u); p3:=(-8u,0);
pat0:=randomcirc(p0,8u,.5u);
pat3:=randomcirc_bis(p3,5u,0.4u);
pat4 = buildcycle(pat0, pat3);
fill pat4 withcolor red;
draw pat0; draw pat3 dashed evenly;
%
dotlabel.ulft("1", pat0 intersectionpoint pat3);
dotlabel.lrt("2", pat3 intersectionpoint pat0);
label.rt("aa", point 0 of pat0);
label.lft("b", point 0 of pat3);
endfig;
end. In this drawing I tried to reproduce exactly the modus operandi of buildcycle as explained in the MetaPost manual, p. 30 (section 9.1, "Building Cycles"). Citation:

The buildcycle macro detects the two intersections labeled 1 and 2 in Figure 24b. Then it constructs the cyclic path shown in bold in the figure by going forward along path aa from intersection 1 to intersection 2 and then forward around the counter-clockwise path b back to intersection 1.

If I understand the macro intersectionpoint correctly, point 1 is in fact aa intersectionpoint b and it is the first intersection that aa (pat0) encounters with b (pat3).

Similarly point 2 is b intersectiopoint aa, and it is also the first intersection that b (pat3) encounters with aa (pat0).

To reproduce this scheme it has been necessary to start the path pat3 at the left. Otherwise the first intersection that pat3=b would have met with pat0=aa would have been point 1. The two intersection points would have been the same, and in that case buildcycle fails.

I hope I have not been too confusing: English is not my native language…

UPDATE

I have simplified the code. My new vardef macro randomcircbis wasn't necessary. It was enough to replace the line pat3:=randomcirc(p3,5u,0.4u);in the original code by pat3:=randomcirc(p3,-5u,0.4u);. The resulting figure is the same, of course.

beginfig(0)
u:=10pt;
vardef randomcirc(expr O, r, w) =
save p,i; pair p; numeric i;
p=O+right*r;
p for i=1 upto 9: .. (p rotatedaround(O, 36i))+(uniformdeviate w, uniformdeviate w)
endfor .. cycle
enddef;
%
path pat[];
pair p[];
p0:=(0,5u); p3:=(-8u,0);
pat0:=randomcirc(p0,8u,.5u);
pat3:=randomcirc(p3,-5u,0.4u);
pat4 = buildcycle(pat0, pat3);
fill pat4 withcolor red;
draw pat0; draw pat3 dashed evenly;
%
dotlabel.ulft("1", pat0 intersectionpoint pat3);
dotlabel.lrt("2", pat3 intersectionpoint pat0);
label.rt("aa", point 0 of pat0);
label.lft("b", point 0 of pat3);
endfig;
end.

The plain.mp implementation of buildcycle fails to find the correct overlap between two cyclic paths if the beginning (point 0) of one of the paths lies inside the other path. For example:

beginfig(3);
path A, B; picture p[];
A = fullcircle scaled 2.5cm;
B = fullcircle scaled 2cm shifted (1cm,0);

p1 = image(fill buildcycle(A,B) withcolor .8[blue,white]; drawarrow A; drawarrow B;);

A := A rotated 180;
p2 = image(fill buildcycle(A,B) withcolor .8[blue,white]; drawarrow A; drawarrow B;);

B := B rotatedabout(center B,180);
p3 = image(fill buildcycle(A,B) withcolor .8[blue,white]; drawarrow A; drawarrow B;);

A := A rotated 180;
p4 = image(fill buildcycle(A,B) withcolor .8[blue,white]; drawarrow A; drawarrow B;);

for i=1 upto 4: draw p[i] shifted (120i,0); label(decimal i, (7mm+120i,0)); endfor
endfig;

produces In each subfigure, the arrow head is pointing at the beginning of the path. You can see that buildcycle only works in situation 2 where neither point 0 lies within the other cyclic path. Note that in situation 4 we get the union of the two paths.

Here's a way to correct this fault. First you need a function to determine whether a given point lies within a cyclic path. Following Sedgewick's Algorirthms in C, you can write:

% is point "p" inside cyclic path "ring" ?
vardef inside(expr p, ring) =
save t, count, test_line;
count := 0;
path test_line;
test_line = p -- (infinity, ypart p);
for i = 1 upto length ring:
t := xpart(subpath(i-1,i) of ring intersectiontimes test_line);
if ((0<=t) and (t<1)): count := count + 1; fi
endfor
odd(count)
enddef;

And here is an overlap function that replaces buildcycle in this special case of two overlapping cyclic paths.

vardef front_half primary p = subpath(0, 1/2 length p) of p enddef;
vardef back_half  primary p = subpath(1/2 length p, length p) of p enddef;

% a and b should be cyclic paths...
vardef overlap(expr a, b) =
save p, q;
boolean p, q;
p = inside(point 0 of a, b);
q = inside(point 0 of b, a);
if ((not p) and (not q)):
buildcycle(a,b)
elseif (not p):
buildcycle(front_half b, a, back_half b)
elseif (not q):
buildcycle(front_half a, b, back_half a)
else:
buildcycle(front_half a, back_half b, front_half b, back_half a)
fi
enddef;

The basic idea is that if neither point 0 is inside the other path, then you just call buildcycle, otherwise you split the two cycles up into an appropriate sequence of half cycles. Replacing buildcycle in the above example with overlap gives this: And replacing buildcycle in the OP example with overlap gives this: which is probably closer to what was wanted in the first place.

Furthermore, if the two cyclic paths are running in opposite directions the behaviour of buildcycle is different again. Here's an extended version of the first example; in the second row, the larger path is running backwards: To deal with this possibility you can make overlap more robust by using the useful counterclockwise function (from plain.mp) which returns a copy of a cyclic path running counterclockwise. Here is the improved version of the overlap function.

vardef overlap(expr a, b) =
save p, q, A, B;
boolean p, q;
p = not inside(point 0 of a, b);
q = not inside(point 0 of b, a);
path A, B;
A = counterclockwise a;
B = counterclockwise b;
if (p and q):
buildcycle(A,B)
elseif p:
buildcycle(front_half B, A, back_half B)
elseif q:
buildcycle(front_half A, B, back_half A)
else:
buildcycle(front_half A, back_half B, front_half B, back_half A)
fi
enddef;

which produces this in my extended example. • I've just found an interesting counterexample: say that a = fullcircle scaled 6cm and b = a reflectedabout(origin, right) shifted (0, 4cm). Then buildcycle(a, b) gives nothing, despite the fact that each starting point is outside the other path. The reason is that the point 1 and point 2 defined in fig. 24b of the MetaPost manual are the same in this case. However, buildcycle(a, reverse b) works as expected. It seems thus that the turningnumber of the paths should be taken into account. – Franck Pastor Apr 1 '15 at 17:02
• @fpast - thanks, I suspect that there are lots of counter examples - in general both cyclic paths should be going in the same direction. – Thruston Apr 1 '15 at 17:08
• @fpast see updated solution which should cope with reflected or reversed paths... – Thruston Apr 2 '15 at 17:28
• Great! One more thing: buildcycle can also fail for non-cyclic paths. For example, when fullcircle is replaced by halfcircle in my counterexample above). I Would suggest extending your overlap macro to that kind of paths, e.g. by replacing arguments a and b by a..cycle, b..cycle if they are not cycles, before applying overlap upon them. – Franck Pastor Apr 3 '15 at 14:41

Here is another implementation of the same idea as in fpast's answer. Instead of starting with a point on the left, you can just rotate the original circle by 180 degrees. (I also simplified the code for randomized circle a bit).

\startMPdefinitions
vardef randomcircle(expr O, r, w, a) =
((fullcircle rotated  a scaled 2r) randomized w shifted O)
enddef;
\stopMPdefinitions
\starttext

\startMPpage[offset=2mm]
u:=10pt;
path pat[];
pair p[];

p0:=(0,5u); p3:=(-8u,0);

pat0 = randomcircle(p0, 8u, 0.4u, 0);
pat3 = randomcircle(p3, 5u, 0.4u, 180);

fill buildcycle(pat0, pat3) withcolor red;

draw pat0;
draw pat3;

dotlabel.ulft("1", pat0 intersectionpoint pat3);
dotlabel.lrt("2", pat3 intersectionpoint pat0);
label.rt("aa", point 0 of pat0);
label.lft("b", point 0 of pat3);
\stopMPpage

\stoptext

which gives • Undoubtedly more elegant! :-) – Franck Pastor Jan 22 '14 at 17:42
• Unfortunately, there is no automatic way of doing this (i.e., if the centres and radii of the circle change, you may need to rotate the other circle or not rotate any circle at all). I wish Metapost were smart enough to figure all this out on its own. – Aditya Jan 22 '14 at 18:25
• Ok, the realy interesting thing is why not to rebuild the buildcycle which make it work in any case proivded two path do intersect? – user19832 Jan 23 '14 at 13:56
• It is certainly more complicated than it seems. According to the MetaPost manual, buildcycle works best with a sequence of more than two paths and if in each pair of consecutive paths, the first path has only one intersection point with the second one. There are here two (closed) paths with two intersections, and at least four feasible cycles could be considered as feasible solutions (the left, the middle — the expected solution —, the right and the outer part). Not mentioning the "degenerated" possibilities like points 1 and 2. Any algorithm would wonder which one is to be chosen, I guess. – Franck Pastor Jan 23 '14 at 21:45
• @Aditya: Quoting Asymptote's manual (version 2.23), p. 40: path buildcycle(... path[] p); "This returns the path surrounding a region bounded by a list of two or more consecutively intersecting paths, following the behaviour of the MetaPost buildcycle command." So I guess it works just the same way. – Franck Pastor Jan 24 '14 at 8:30