从两个相交路径得到三个结果路径

Question

我在 xy 平面中有两条相交路径，请参见图像。

一条路径是由一组按顺序排列的点定义的，每两个连续的点形成一条路径的边。路径总是封闭的。标记点以指示它们是来自边缘还是曲线。我正在尝试编写一个函数来获取以下三个路径。

我尝试了以下方法。

create temp path Object path_C
go through every edge in path_A
    go through every edge in path_B
        if current edge of path_A intersects edge of path_B
        find the intersection
        store the intersection point in path_C
    inner loop ends here
outer loop ends here
go through every point in path_A
   if a point lies within the path_B 
   add it to the path_C
   and remove it from path_A 
end of loop
go through every point in path_B
   if a point lies within the path_A 
   add it to the path_C
   and remove it from path_B
end the loop

在我可以运行之前，我的一位朋友指出，不能保证 path_C 得到的分数顺序正确。现在我不知道如何解决这个问题。如果能提出一些优化建议就更好了。

旁注：我实际上是在尝试在 adobe illustrator 的探路者面板中实现 divide 功能。

Answer 1

您要查找的术语是 "graph cycle"，请查看此堆栈溢出线程：finding all cycles in graph。基本上你想从两条路径构建一个图。这是通过连接两条路径（带上它们的所有边和顶点）并在每个交点上引入新顶点来完成的。交点是图形将合并的地方。在实施过程中，考虑所有边缘情况，即交叉可能发生在通过顶点的边缘、共线 edges/verts 等之间。还要注意，对于某些形状，例如 U 形和矩形，可以产生多个循环.

从两个相交路径得到三个结果路径

getting three resultant paths from two intersecting paths

algorithm

geometry

shape

geometry-surface