1
\$\begingroup\$

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

enter image description here

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} ]
\$\endgroup\$
  • 2
    \$\begingroup\$ Can two or more lines that form a line themselves (parallel with same endpoint) be used as the side of a triangle? \$\endgroup\$ – David Harkness May 26 '14 at 22:11
  • \$\begingroup\$ I haven't thought it.. I would say no but if it really simplifies the code readability and performance.. yes \$\endgroup\$ – nkint May 26 '14 at 22:22
  • \$\begingroup\$ It would most assuredly complicate the solution. :) Unless this is for a production-grade library, I doubt it's needed. \$\endgroup\$ – David Harkness May 26 '14 at 22:27
  • \$\begingroup\$ What's with the spelling variations? "Trinagles", "Traingle" \$\endgroup\$ – 200_success May 26 '14 at 23:22
  • \$\begingroup\$ Sorry for the typo errors I'll correct them \$\endgroup\$ – nkint May 27 '14 at 9:30
2
\$\begingroup\$

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 theory rather than one in . Your algorithm is currently O(n3) due to the three nested loops. You could probably do better with a smarter algorithm.

\$\endgroup\$
  • \$\begingroup\$ Ok so you point out 2 issues: 1) align ComparatorVec2D and ComparatorTriangle2D to have consistence (but remove the magnitude? Thresholded distance instead of strict float equality seems more flexible to me) and 2) use a different algorithm to find triangles.. \$\endgroup\$ – nkint May 27 '14 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.