多三角形相交

Question

我有一个二维点数组 space。我试图从这些点创建尽可能多的三角形但是：

所有三角形必须有效（a < b + c and b < a + c and c < a + b）
没有三角形可以包含点（只有它们的顶点）
没有三角形可以与任何其他三角形相交

我所说的交集是指一个三角形不能在另一个三角形内部，三角形的边不能与另一个三角形的边相交（但它们可以共享一条边）。

我认为我的算法没有问题（为简单起见伪）：

newTriangles := false
do:
    newTriangles := false
    for a in points:
        for b in points:
            if b = a:
                continue

            for c in points:
                if c = a or c = b:
                    continue
                // So now we have every combination of a, b and c

                // Now the tests
                if not valid_triangle(a, b, c) then continue

                containsPoint := false
                for p in points:
                    if p = a or p = b or p = c:
                        continue

                    if contains(a, b, c, p):
                        containsPoint := true // first 3 params are the vertices of the triangle, the 4th is the point for test

                if containsPoint:
                    continue

                // Now the last test, the existing triangle intersection
                intersects := false
                for triangle in triangles:
                    if intersects(triangle, a, b, c):
                        intersects := true

                // It passed every test, it can be a triangle
                if not intersects:
                    triangles.add(new triange(a, b, c))
                    newTriangles := true
while newTriangles

这连接了一些三角形，但每个三角形都与其他三角形隔离。我猜交叉点检查 returns 是真的。现在更好地说明我的问题：

所以第一步发生了，但第二步不会发生，它使每个三角形（有时是单个点）保持隔离。但是，如果我更改我的交集检查代码，那么该代码将永远不会停止。可能的解决方案是什么？

编辑：

这是我的相交算法（这是真实的 Java 代码）：

public static boolean intersects(Vector2f a, Vector2f b, Vector2f c, Triangle other) {
        boolean x = (Line.segmentIntersects(a, b, other.a, other.b) || Line.segmentIntersects(b, c, other.a, other.b)) ||
                    (Line.segmentIntersects(a, b, other.a, other.b) || Line.segmentIntersects(a, c, other.a, other.b)) ||
                    (Line.segmentIntersects(a, c, other.a, other.b) || Line.segmentIntersects(b, c, other.a, other.b));

        boolean y = (Line.segmentIntersects(a, b, other.b, other.c) || Line.segmentIntersects(b, c, other.b, other.c)) ||
                    (Line.segmentIntersects(a, b, other.b, other.c) || Line.segmentIntersects(a, c, other.b, other.c)) ||
                    (Line.segmentIntersects(a, c, other.b, other.c) || Line.segmentIntersects(b, c, other.b, other.c));

        boolean z = (Line.segmentIntersects(a, b, other.a, other.c) || Line.segmentIntersects(b, c, other.a, other.c)) ||
                    (Line.segmentIntersects(a, b, other.a, other.c) || Line.segmentIntersects(a, c, other.a, other.c)) ||
                    (Line.segmentIntersects(a, c, other.a, other.c) || Line.segmentIntersects(b, c, other.a, other.c));

        return (x || y || z ||
                other.contains(a) || other.contains(b) || other.contains(c));
    }

段相交是：

public static boolean segmentIntersects(Vector2f ps1, Vector2f pe1, Vector2f ps2, Vector2f pe2) {
        return (Line2D.linesIntersect(ps1.x, ps1.y, pe1.x, pe1.y, ps2.x, ps2.y, pe2.x, pe2.y));
}

并包含：

private static float sign(Vector2f p1, Vector2f p2, Vector2f p3) {
        return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
    }
public static boolean contains(Vector2f a, Vector2f b, Vector2f c, Vector2f p) {
        boolean b1, b2, b3;
        b1 = sign(p, a, b) < 0.0f;
        b2 = sign(p, b, c) < 0.0f;
        b3 = sign(p, c, a) < 0.0f;
        return ((b1 == b2) && (b2 == b3));
    }

Answer 1

我不能给你完整的工作代码，但我可以给你一些建议和一些可能的错误点：

首先请注意，在您的 intersects 方法中，您进行了大量冗余检查！

boolean x = (Line.segmentIntersects(a, b, other.a, other.b) ||
            (Line.segmentIntersects(a, b, other.a, other.c) ||
            (Line.segmentIntersects(a, b, other.b, other.c);

boolean y = (Line.segmentIntersects(a, c, other.a, other.b) ||
            (Line.segmentIntersects(a, c, other.a, other.c) ||
            (Line.segmentIntersects(a, c, other.b, other.c);

boolean z = (Line.segmentIntersects(b, c, other.a, other.b) ||
            (Line.segmentIntersects(b, c, other.a, other.c) ||
            (Line.segmentIntersects(b, c, other.b, other.c);

这就是你所需要的！此处您正在检查三角形的每一边 abc 是否与另一个三角形的任何边相交。

在您的 return 中，您也可以通过不检查 other.contains(a) || other.contains(b) || other.contains(c) 来节省一些时间。由于 other 已被选为有效三角形，我们可以假设 other 不包含来自三角形 abc.

的任何点

如果你的代码永远是运行那么我愿意打赌这是因为你没有检查三角形 abc 是否等于 另一个三角形.如果是，那么您应该停止查看 abc，因为它已经被添加了！

请注意，根据您的伪代码，您的代码确实应该暂停，因为您只使用 for 循环，应该保证终止。也许您应该检查这些循环的退出条件:)

希望对您有所帮助！

多三角形相交

Multiple triangle intersection

algorithm

intersection

triangulation