如何获取自相交路径的交点？

Question

（棘手的问题。）我试图获取一条单独/任意曲线的交点，而不是搜索多条曲线之间的交点。我们可以在所有主要的 TeX 相关图形引擎中轻松获取两条不同曲线的交点（甚至是两条相同的曲线，如下例所示）(元帖子，技巧，渐近线，蒂克兹，您说得出名字的）。

TikZ 中的第一个示例（左图）演示了我使用的技巧。我定义了一条曲线，然后将其加载并命名为first和second。如果曲线由线段组成，我们会立即获得交点。添加参数后sort by，我们会得到两条曲线的正确点，在循环中仅使用奇数/偶数交点（1,3,...）后，我们会得到一条曲线的交点。尽管如此，结果还是不正确，因为点3和5由两个连续线段的端点或起点组成。

解决方案是将该曲线分成多条线段（单独的曲线），然后将它们分成两个比较，内外\foreach循环，不包括线段之间的连接点（实际上比较的是：第二条线段与第一条线段，第三条线段与前两条线段等等）。

• 第一条线段由以下部分组成(0,0)--(3,0)：
• 第二条线段由 组成(3,0)--(2,1)，并且，
• 第三个由原始曲线的这一部分组成(2,1)--(1,-1)。

解决方案只有一个，即点1。这需要一些编程，但可以做到。

但如何解决贝塞尔曲线？让我在下一个示例（右图）中演示一下。在这种情况下，由于曲线再次相互重叠，我们得到了许多交点，我们可以使用这些点（如果我没记错的话，它们之间的距离是）来1pt绘制许多线段。也许我们可以使用窗口测试，这可能是我们最好的办法。实际上，我使用一组不交叉的单独曲线，但有没有更好的方法来获取单个曲线的所有交点？

第二个例子中，只有一个解：路口位于点 附近113。

% *latex mal-intersections.tex
% (It takes a couple of seconds to get PDF.)
\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{tikz}
\usetikzlibrary{intersections}

\begin{document}
\begin{tikzpicture} % Curve consists from line segments.
\def\thecurve{ (0,0)--(3,0)--(2,1)--(1,-1) } 
\draw[name path=first] \thecurve;
\draw[name path=second] \thecurve;
\fill [name intersections={of=first and second, name=i, total=\t, sort by=first}]
[red, opacity=0.5, every node/.style={above, black, opacity=1}]
\foreach \s in {1,3,...,\t}{(i-\s) circle (2pt) node {\footnotesize\s}};
\end{tikzpicture}
%
\begin{tikzpicture} % A single Bézier curve.
\def\thecurve{ (0,0) .. controls (5,1) and (0,3) .. (2,-1) } 
\draw[name path=first] \thecurve;
\draw[name path=second] \thecurve;
\fill [name intersections={of=first and second, name=i, total=\t, sort by=first}]
[red, opacity=0.5, every node/.style={above, black, opacity=1}]
\foreach \s in {1,9,...,\t}{(i-\s) circle (2pt) node {\tiny\s}};
\end{tikzpicture}
\end{document}

Answer 1

这里似乎有一个技巧：搜索曲线的交点……以及它的反向交点。使用 MetaPost 进行应用。

u := 3cm;
path curve[];
curve1 = ((0,0)--(3,0)--(2,1)--(1,-1)) scaled u;
curve2 = ((0,0) .. controls (5,1) and (0,3) .. (2,-1)) scaled u;

def self_intersection(expr curve) = 
  draw curve;
  drawdot curve intersectionpoint reverse curve withpen pencircle scaled 6bp;
enddef;

beginfig(1);
  self_intersection(curve1);
  self_intersection(curve2 shifted (3.5u, 0));
endfig;
end.

同样的想法似乎也适用于 TikZ：

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{intersections}

\begin{document}

\begin{tikzpicture}
\draw[name path=curve1] 
  (0,0) -- (3,0) -- (2,1) -- (1,-1);
\path[name path=curve1r] 
  (1,-1) -- (2,1) -- (3,0) -- (0,0);
\path[name intersections={of=curve1 and curve1r, by={a}}]
  node[fill,circle,inner sep=1.5pt] at (a) {};  
\begin{scope}[xshift=4cm]
\draw[name path=curve2] 
  (0,0) .. controls (5,1) and (0,3) .. (2,-1);
\path[name path=curve2r] 
  (2,-1) .. controls (0,3) and (5,1) .. (0,0);
\path[name intersections={of=curve2 and curve2r, by={b}}]
  node[fill,circle,inner sep=1.5pt] at (b) {};  
\end{scope}
\end{tikzpicture}

\end{document}

Answer 2

我必须承认，我很惊讶地发现这个问题，而且公认的答案作品。我需要查看算法的细节才能理解为什么！

不知道 MetaPost 和 PGF 寻找交集的算法的这个特性，对于knots库然后我实现了一种查找自交点的方法，该方法通过将路径分解为子路径，然后找到它们之间的交点来实现。

经过进一步分析，我不会用上述算法替换我的算法，因为当我运行接受的答案中的代码并将其与我的算法进行比较时，编译所需的时间长度存在显着差异。

lualatex selfintersection.tex  88.85s user 1.84s system 96% cpu 1:33.89 total
lualatex selfintersection.tex  4.56s user 1.50s system 95% cpu 6.374 total

显然，这只是一个例子。

我的代码如下，它使用了 2.0 版spath3软件包（2021-01-22 发布）：

\documentclass{article}
%\url{https://tex.stackexchange.com/q/236550/86}

\usepackage{tikz}
\usetikzlibrary{intersections, spath3}

\begin{document}

\begin{tikzpicture}
\draw[spath/save=lines]  (0,0)--(3,0)--(2,1)--(1,-1) ;

\tikzset{
  spath/split at self intersections=lines,
  spath/get components of={lines}\lcpts
}

\foreach[count=\k] \cpt in \lcpts
{
  \fill[red, opacity=0.5] (spath cs:{\cpt} 1) circle[radius=2pt] node[above, black, opacity=1] {\(\k\)};
}
\end{tikzpicture}

\begin{tikzpicture} % A single Bézier curve.
\draw[spath/save=curve]  (0,0) .. controls (5,1) and (0,3) .. (2,-1);
\path[overlay, spath/save=marker] (spath cs:curve .5) +(-.2,-.2) -- +(.2,.2);
\tikzset{
  spath/split at intersections={curve}{marker},
  spath/spot weld=curve,
  spath/split at self intersections=curve,
  spath/get components of={curve}\ccpts
}

\foreach[count=\k] \cpt in \ccpts
{
  \fill[red, opacity=0.5] (spath cs:{\cpt} 1) circle[radius=2pt] node[above, black, opacity=1] {\(\k\)};
}
\end{tikzpicture}

\end{document}

它做的事情与问题描述略有不同，但希望足以证明其能力。它所做的是分裂路径在自相交点处。也就是说，如果我们想象原始路径的相关部分只是从(0,0)到的一条直线(1,0)，并且交点在，(.5,0)那么新路径的相应部分看起来就像您从路径规范中获得的那样：

(0,0) -- (.5,0) (.5,0) -- (1,0)

一旦这些分割到位，就可以提取路径的组成部分并单独处理它们，包括使用它们来指定坐标。在上面的代码中，这意味着交叉点被使用两次（每次路径经过它时使用一次），并且路径的终点也被标记，但这些都很容易处理。

贝塞尔曲线有一个小问题，即它被指定为一条自相交的单条曲线。我确实有代码可以自动分割这样的曲线，但我似乎没有在代码中包含这一点split at self intersections——我会弥补这个疏忽。与此同时，我们可以引入另一条路径来分割，将单条贝塞尔曲线分成两段来模拟这种情况。