Find triangles from line

Question

I have some lines that form triangles. I'd like to challenge the fastest way to find all triangles.

In particular the code should take an ArrayList of Line2D object and return an ArrayList of Triangle2D. The only constrain is to use p1.distanceToSquared(p2) < 1) as equal function.

Note:

My code does not work because it contains some triangles more time (10 triangles instead of 8), i.e. I didn't managed to write the triangle comparator.

This is my Java code (using this lib that has some standard 2D objects):

private ArrayList<Triangle2D> findTrinaglesTromLines(ArrayList<Line2D> lines) {

    class TriangleComparator implements Comparator<Triangle2D>{
        @Override
        public int compare(Triangle2D t1, Triangle2D t2) {
            TreeSet<Vec2D> pts1 = new TreeSet<Vec2D>();
            pts1.add(t1.a); pts1.add(t1.b); pts1.add(t1.c); 

            TreeSet<Vec2D> pts2 = new TreeSet<Vec2D>();
            pts2.add(t2.a); pts2.add(t2.b); pts2.add(t2.c);

            if (pts1.containsAll(pts2)) return 0;
            else return 1;
        }
    }   

    TreeSet<Triangle2D> triangles = new TreeSet<Triangle2D>(new TriangleComparator());
    for(int i=0; i<lines.size(); i++) {
        Line2D l1, l2, l3;
        l1 = lines.get(i);
        for (int j=0; j<lines.size(); j++) {
            Line2D m = lines.get(j);
            if(l1==m)continue;
            if(shareVertex(l1, m)) {
                l2 = m;
                for(int k=0; k<lines.size(); k++) {
                    Line2D n = lines.get(k);
                    if(l1==n || l2==n) continue;
                    l3 = n;
                    if( shareVertex(l1, l3) || shareVertex(l2, l3) ) {
                        Triangle2D t = getTraingle(l1, l2, l3);
                        if( t!= null ) {
                            triangles.add(t);
                            println(t.toString());
                        }
                    }
                }
            }
        } 
    }
    return new ArrayList<Triangle2D>(triangles);
}

private boolean shareVertex(Line2D l1, Line2D m) {
    if( l1.a.distanceToSquared(m.a) < 1) return true;
    if( l1.a.distanceToSquared(m.b) < 1) return true;
    if( l1.b.distanceToSquared(m.b) < 1) return true;
    return false;
}

private Triangle2D getTraingle(Line2D a, Line2D b, Line2D c) {
    TreeSet<Vec2D> pts = new TreeSet<Vec2D>();
    pts.add(a.a); pts.add(a.b);
    pts.add(b.a); pts.add(b.b);
    pts.add(c.a); pts.add(c.b);
    if(pts.size()!=3) return null;
    Iterator<Vec2D> iterator = pts.iterator();
    Triangle2D t = new Triangle2D();
    t.a = iterator.next();
    t.b = iterator.next();
    t.c = iterator.next();
    return t;
}

Here the lines (begin point, end point):

[ {x:568.051, y:286.209}, {x:505.477, y:411.501} ]
[ {x:505.477, y:411.501}, {x:696.271, y:462.066} ]
[ {x:696.271, y:462.066}, {x:568.051, y:286.209} ]
[ {x:696.271, y:462.066}, {x:672.033, y:213.228} ]
[ {x:672.033, y:213.228}, {x:568.051, y:286.209} ]
[ {x:145.374, y:290.304}, {x:176.77, y:455.729} ]
[ {x:176.77, y:455.729}, {x:332.868, y:284.48} ]
[ {x:332.868, y:284.48}, {x:145.374, y:290.304} ]
[ {x:332.868, y:284.48}, {x:191.991, y:192.966} ]
[ {x:191.991, y:192.966}, {x:145.374, y:290.304} ]
[ {x:176.77, y:455.729}, {x:505.477, y:411.501} ]
[ {x:505.477, y:411.501}, {x:332.868, y:284.48} ]
[ {x:261.672, y:132.32}, {x:574.957, y:159.359} ]
[ {x:568.051, y:286.209}, {x:574.957, y:159.359} ]
[ {x:332.868, y:284.48}, {x:568.051, y:286.209} ]
[ {x:261.672, y:132.32}, {x:332.868, y:284.48} ]
[ {x:332.868, y:284.48}, {x:574.957, y:159.359} ]

Answer 1

I suggest that you start by considering what it means for two points to be the same vertex.

In the toxiclibs library, a Vec2D consists of an x- and y-coordinate, each stored as a float. In shareVertex(), you've defined two Vec2Ds to be the "same" point if they are less than one unit apart. (Using == to compare floats is generally a bad idea, so setting some threshold for equality is good, though 1.0 might be a bit sloppy relative to the precision that a float is capable of.)

However, in getTraingle() [sic], you use a different criterion for equality of Vec2Ds. You're relying on a TreeSet<Vec2D> to do the de-duplication for you. In the absence of any comparator given to the TreeSet constructor, it will use Vec2D.compareTo(). Vec2D.compareTo() is a bit weird: it compares vectors by their distance from the origin (the weirdness being that if two points are the same distance from the origin, the ordering will be somewhat arbitrary, thus breaking the Comparable consistency requirement — but that's of no concern to you). What does matter to you, though, are:

• All you care about is equality, but you'll end up doing a lot of wasted magnitude calculations instead.
• Your criterion for equality in shareVertex() (less than one unit separation) is inconsistent with the criterion for equality in Vec2D.compareTo() (strict float equality).

---

Once you've figured out which endpoints of the line segments coincide, the actual coordinates no longer matter. At that point, you would be better off treating this as a problem in graph theory rather than one in computational-geometry. Your algorithm is currently O(n³) due to the three nested loops. You could probably do better with a smarter algorithm.