☰

如何检查给定点是否位于 MetaPost 中的某个封闭路径内

tag-icon • tag-icon metapost
如何检查给定点是否位于 MetaPost 中的某个封闭路径内

如果 MetaPost 中存在某些任意闭合路径（没有自相交），是否有一种简单的方法来检查给定点是位于该路径内部还是外部？

例如：

path p;
pair q, r;
p := (-3cm, 0) .. (-4cm, 1cm) .. (2cm, 3cm) .. (3cm, 1cm) .. (-1cm, -1cm) .. (1cm, -2cm) .. (-2cm, -1cm) .. cycle;
q := (0, 0);
r := (0, 1cm);
draw p;
fill (fullcircle scaled 1mm) shifted q withcolor red;
fill (fullcircle scaled 1mm) shifted r withcolor green;

里面还是外面？

在这种情况下，我希望根据它们与“p”的关系，对于“q”获取红色的“false”以及对于“r”获取绿色的“true”。

答案1

基于获取MetaPost中的所有交点并实施奇偶规则：

  vardef is_inside(expr p,q) =
    begingroup;
    save cut, inside;
    path cut;boolean inside;
    cut := q -- (ulcorner p + (-2,2));
    inside := false;
    forever:
      cut := cut cutbefore p;
      exitif length cuttings = 0;
      cut := subpath(4epsilon, length cut) of cut;
      inside := not inside;
    endfor;
    inside
    endgroup
  enddef;

  beginfig(1) ;
  path p;
  p := (-0.5cm,0cm) .. (5cm,5cm) .. (0cm,3cm) .. (-7cm,9cm) .. cycle;
  z0 = (2cm,3.5cm);
  draw p;
  draw z0 withpen pencircle scaled 2;
  draw origin withpen pencircle scaled 1;

  if is_inside(p,z0):
    label.lrt("IN", origin);
  else:
    label.lrt("OUT", origin);
  fi
  endfig ;

另一种规则是非零缠绕规则。这是Bogusław Jackowski 为 MetaPost 提供的缠绕编号。我扩展了inside运算符以允许测试某个点是否位于路径内：

vardef mock_arclength(expr p) = % |p| -- Bézier segment
  % |mock_arclength(p)>=arclength(p)|
  length((postcontrol 0 of p)-(point 0 of p)) +
  length((precontrol 1 of p)-(postcontrol 0 of p)) +
  length((point 1 of p)-(precontrol 1 of p))
enddef;
vardef windingangle(expr p,q) = % |p| -- point, |q| -- Bézier segment
  save a,b,v;
  a=length(p-point 0 of q); b=length(p-point 1 of q);
  if min(a,b)<2eps: % MP is not the master of precision, we’d better stop now
    errhelp "It is rather not advisable to continue. Will return 0.";
    errmessage "windingangle: point unsafely near Bézier segment (dist="
      & decimal(min(a,b)) & ")";
    0
  else:
    v:=mock_arclength(q); % |v| denotes both length and angle
    if (v>=a) and (v>=b): % possibly too long Bézier arc
      windingangle(p, subpath (0,1/2) of q)+windingangle(p, subpath (1/2,1) of q)
    else:
      v:=angle((point 1 of q)-p)-angle((point 0 of q)-p);
      if v>180: v:=v-360; fi
      if v<-180: v:=v+360; fi
      v
    fi
  fi
enddef;
vardef windingnumber (expr p,q) = % |p| -- point, |q| -- Bézier spline
    save a; a:=0;
    for t:=1 upto length(q):
        a:=a+windingangle(p, subpath(t-1,t) of q);
    endfor
    a/360
enddef;
tertiarydef a inside b =
    if path a: % |and path b|; |a| and |b| must not touch each other
        begingroup
            save a_,b_; (a_,b_)=
                (windingnumber(point 0 of a,b), windingnumber(point 0 of b,a));
            (abs(a_-1)<eps) and (abs(b_)<eps)
        endgroup
    elseif pair a: % |and path b|; |a| must not lie on |b|
        begingroup
            abs(windingnumber(a,b))>eps
        endgroup
    else: % |numeric a and pair b|
        begingroup
            (a>=xpart b) and (a<=ypart b)
        endgroup
    fi
enddef;

这是基于拓扑不变量的，所以应该更可靠。如果它不能计算出正确的结果，至少它会失败。

相关内容