Multiple triangle intersection

Question

I have an array of points in 2D space. I'm trying to create from those points as many triangles as possible but:

• All triangles must be valid (a < b + c and b < a + c and c < a + b)
• No triangles can contain a point (just their vertices)
• No triangles can intersect any other triangles

By intersection I mean that a triangle can't be inside another triangle and a triangle's side can't cross an other's (but they can share an edge).

I think there's no problem with my algorithm (pseudo for simplicity):

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

This connects some triangles, but every triangle is isolated from the others. I guess that intersection checking returns true. Now to illustrate my problem a bit better:

So the first step happens, but the second one won't, it keeps every triangle (and sometimes single points) isolated. However if I change my intersection checking code, then this code will never halt. What could be the solution?

Edit:

Here's my intersects algorithm (this is real Java code):

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));
    }

Segment intersects is:

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));
}

And contains:

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

I can't give you full working code but I can give you some advice and some possible points of error:

First note that in your intersects method you are doing a lot of redundant checks!

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);

Is all you need! Here you are checking if each side of your triangle abc intersects with any side of the other triangle.

In your return you can also save some time by not checking other.contains(a) || other.contains(b) || other.contains(c). Since other was selected as a valid triangle already we can assume that other does not contain any points from triangle abc.

If your code is running forever then I would be willing to bet it is because you are not checking whether triangle abc equals the other triangle. If it does then you should stop looking at abc since it has already been added!

Mind you, based on your pseudo code, your code really should be halting as you only use for loops which should be guaranteed to terminate. Perhaps you should check the exit conditions for these loops :)

Hope this helps!