Find triangles from line

Question

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} ]

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

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.

• nkint: 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..