☰

为什么在 MetaPost 中两条相交的路径无法构建循环？

tag-icon • tag-icon metapost
为什么在 MetaPost 中两条相交的路径无法构建循环？

假设我有两条路径：

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;

为什么它们的交点没有填充红色？

我认为这是由于 MetaPost 的精度太低造成的，如何解决？

答案1

如果其中一条路径的起点 ( ) 位于另一条路径内，plain.mp则 的实现无法找到两条循环路径之间的正确重叠。例如：buildcyclepoint 0

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;

生产

在此处输入图片描述

在每个子图中，箭头指向路径的起点。你可以看到，这只buildcycle适用于情况 2，即两者都不point 0在另一个循环路径内。请注意，在情况 4 中，我们得到了联盟两条路径。

以下是纠正此错误的方法。首先，您需要一个函数来确定给定点是否位于循环路径内。遵循 Sedgewick 的C 语言算法， 你可以写：

% 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;

这是一个在两个重叠循环路径的特殊情况下overlap进行替换的函数。buildcycle

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;

基本思想是，如果两者都不point 0在另一条路径内，则只需调用buildcycle，否则将两个循环拆分为适当的半循环序列。将buildcycle上例中的 替换为overlap可得出以下结果：

在此处输入图片描述

buildcycle在 OP 示例中替换overlap为：

在此处输入图片描述

这可能更接近最初想要的结果。

此外，如果两个循环路径运行在相反方向的行为buildcycle又不同了。这是第一个例子的扩展版本；在第二行中，较大的路径是向后运行的：

在此处输入图片描述

为了解决这种可能性，您可以overlap使用有用的counterclockwise函数（来自plain.mp）来提高鲁棒性，该函数返回逆时针运行的循环路径的副本。这是该overlap函数的改进版本。

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;

这在我的扩展示例中产生了这一点。

在此处输入图片描述

答案2

如果我稍微改变 的定义pat3，使其pat3从圆的“左边”（可以这么说）开始，而不是从“右边”（与 相反pat0）开始，它就会在这里起作用。为此，我定义了另一个vardef宏（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.

在此处输入图片描述

buildcycle在这幅图中，我试图准确重现MetaPost 手册第 30 页（第 9.1 节“构建周期”）中解释的运作方式。引用：

宏buildcycle检测到图 24b 中标记为 1 和 2 的两个交叉点。然后，它构建了图中粗体显示的循环路径，即沿着路径 aa 从交叉点 1 前进到交叉点 2，然后沿着逆时针路径 b 前进回到交叉点 1。

如果我理解intersectionpoint正确的话，第 1 点实际上aa intersectionpoint b是第一的aa( pat0) 与b( )的交点pat3。

类似地，第 2 点是b intersectiopoint aa，它也是第一的b( pat3) 与aa( )的交点pat0。

要重现此方案，必须从pat3左侧开始路径。否则，第一个pat3=b会遇到的交叉点将pat0=aa是点 1。两个交叉点将是相同的，在这种情况下buildcycle会失败。

我希望我没有太让人困惑：英语不是我的母语……

更新

我简化了代码。我的新 vardef 宏randomcircbis不是必需的。pat3:=randomcirc(p3,5u,0.4u);只需将原始代码中的行替换为 即可pat3:=randomcirc(p3,-5u,0.4u);。当然，结果图是相同的。

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.

答案3

这是与 fpast 的答案中相同想法的另一种实现。您不必从左侧的点开始，只需将原始圆旋转 180 度即可。（我还稍微简化了随机圆的代码）。

\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

这使

在此处输入图片描述

相关内容