Пересечение нескольких треугольников

У меня есть массив точек в 2D-пространстве. Я пытаюсь создать из этих точек как можно больше треугольников, но:

• Все треугольники должны быть правильными (a ‹ b + c и b ‹ a + c и 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

Это соединяет некоторые треугольники, но каждый треугольник изолирован от других. Я предполагаю, что проверка пересечения возвращает true. Теперь немного лучше проиллюстрирую мою проблему:

Таким образом, первый шаг происходит, а второй нет, он сохраняет каждый треугольник (а иногда и отдельные точки) изолированными. Однако, если я изменю свой код проверки пересечения, этот код никогда не остановится. Что может быть решением?

Редактировать:

Вот мой алгоритм пересечений (это настоящий код 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));
    }