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