# Find triangles from line

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

TreeSet<Vec2D> pts2 = new TreeSet<Vec2D>();

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 ) {
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>();
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} ]

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

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:
• Your criterion for equality in shareVertex() (less than one unit separation) is inconsistent with the criterion for equality in Vec2D.compareTo() (strict float equality).