代码之家  ›  专栏  ›  技术社区  ›  Greg B

计算两个任意形状的并集

  •  8
  • Greg B  · 技术社区  · 15 年前

    我正在开发一个应用程序,我需要能够结合用户绘制的两个重叠的任意形状。这将是对两个形状的联合操作。最终形成的形状将是两个重叠形状的轮廓。

    形状按顺时针顺序存储为点序列。

    理想情况下,我想要一个算法,它将取两个点数组(x,y)并返回一个结果形状的单个数组。

    我一直在读维基百科 Boolean operations on polygons 其中提到 Sweep line algorithm 但是我不能把这和我的目标联系起来,唉,我不是一个数学家。

    我正在开发ActionScript 3中的应用程序,但是我熟悉C语言,Java和I可以通过C和C++选择我的方法。

    6 回复  |  直到 13 年前
        1
  •  5
  •   Martin B    15 年前

    正确地实现布尔运算并不容易;幸运的是,有些库已经实现了这个功能。

    你用什么语言?如果是C++,请看 CGAL ,计算几何算法库。

        2
  •  3
  •   Dead account    15 年前

    给出两个点列表(A和B)
    -[1]A中的每一条线是否与B中的一条线相交?
    -.-[2]如果没有(更多)条线相交,则没有重叠。
    -.-[3]如果(a)中的一条线与b中的一条线相交,则
    -.-.-[4]将交点添加到输出中
    -.-.-[5]从A相交B的下一行
    -.-.-.-[6]如果没有,把这个加到输出端(在B里面)转到5
    -.-.-.-[7]如果是,请将intersect添加到output,并将switch列表A&B转到2

    也看到 Intersection Point Of Two Lines . 我不会写代码对不起:)

        3
  •  3
  •   lhf    15 年前

    另请参见 GPC .

        4
  •  2
  •   Jon Cage    15 年前

    this algorithm 为你工作?

        5
  •  1
  •   Jon Cage    15 年前

    怎么样:

    1. 选择两个形状中最左边的点。将该形状称为A并使其成为当前形状。
    2. 沿当前形状顺时针旋转到下一个点,检查一条或多条线是否相交。
      • 如果有任何线相交,请找到第一个相交点并将其添加到新形状中。切换到沿另一个形状缠绕。
      • 如果没有线相交,则移动到形状A中的下一个点,并将其添加为新形状中的点。继续沿当前形状缠绕。
    3. 重复步骤2。

    我认为,如果你一直沿着当前的任何形状缠绕,寻找交叉点,那应该是你想要的。我认为这也应该解决凹形的问题…

    我相信一旦你的基础工作了,你可以增加很多优化。

        6
  •  1
  •   Karussell    13 年前

    似乎还有一个javascript API:

    https://github.com/bjornharrtell/jsts/

    它似乎实现了JTS标准,并有几个不同的实现:

    http://tsusiatsoftware.net/jts/jts-links.html#ports

    他们都应该能够执行联合等任务:

    http://tsusiatsoftware.net/jts/JTSUser/contents.html

    但是CSG.JS是IMO最令人印象深刻的项目

    https://github.com/evanw/csg.js