Iterate over every triangle in a field of points

Question

I have a method that adds points to a field of random, unconnected points, and the next point to be added must be within the largest empty triangle drawn between three points. The four corners of the field are the first points to be added.

My problem is that my current solution for calculating every triangle uses four nested enhanced-for loops '(foreach style), and takes a long time as the numbers of points add up. I am looking at processing this in parallel (maybe with Java 8 parallel streams?), but is there a more efficient way select the points or test if they are inside the triangle?

Many thanks

for(Point p1 : POINTS) {
        for(Point p2 : POINTS) {
            if(p2==p1) {continue;}
            for(Point p3 : POINTS) {
                if(p3==p2 || p3==p1) {continue;}

                Polygon p = new Polygon(new int[]{p1.x,p2.x,p3.x}, new int[]{p1.y,p2.y,p3.y}, 3);//Construct a triangle from these points
                boolean empty = true;

                for(Point p4 : POINTS) {//test the remaining points if they are in the triangle
                    if(p4==p3 || p4 == p2 || p4 == p1) {continue;}
                    if(p.contains(p4)){
                        empty = false;
                        break;
                    }
                }
                if(empty==true) {
                    emptyTriangles.add(new Triplet<Point,Point,Point>(p1,p2,p3));//emptyTriangles contains the coordinates of the empty triangles
                }

            }
        }
    }

For much better performance, consider sorting `POINTS` and then only look at the first 2 closest points in the x & y direction for each point. — 4castle, Jun 15 '16 at 14:01
@4castle but that would mean that extremely large open spaces would get ignored as only the near points would get searched — Luke Moll, Jun 15 '16 at 14:06
Yeah, I'm thinking it should just look at the following points until it finds a point contained in the previously found triangles. This might need a mathematicians touch, or a computer scientist. For questions concerning algorithms, there are other StackExchange networks better suited. — 4castle, Jun 15 '16 at 14:08
I have to admit I ignored the "empty triangle" condition in my solution, so 4castle has the better approach I guess, although it would truly involve more theory :-) — GreenThor, Jun 15 '16 at 14:14
@GreenThor @4castle I'll try @GreenThor 's solution with either `Thread`-based or `Stream`-based parallel processing and see if I make any headway, otherwise I'll reword it and have a look at some other networks. Thanks both for your help — Luke Moll, Jun 15 '16 at 14:23

score 1 · Answer 1 · answered Jun 15 '16 at 14:11

I think you can speed it up by not looking at a combination again (the 3 outer for-loops). For example, If you have the points {a,b,c}, your algorithm only needs 1 combination (3 over 3) but goes through 27 (3^3) and calculates 6 completely (3 over 3 times 3!). With N points, this becomes N^3 iterations and N*(N-1)*(N-2) calculations where only (N over 3) = N*(N-1)*(N-2) / 6 are needed. So a speedup by factor 6 is a start.

Given POINTS is an array, you can just write

for (int i1 = 0; i1 < POINTS.length-2; i1++) {
    for (int i2 = i1+1; i2 < POINTS.length-1; i2++) {
        for (int i3 = i2+1; i1 < POINTS.length; i3++) {
            ...
        }
    }
}

You shouldn't loop p4 the same way as the vertices of the triangle are interchangeable between each other for your algorithm, but the point to check is not.

I understand your point about only needing to calculate combinations and not permutations, I don't get how this prevents calculating a combination that has already been done (`{b,a,c}` given `{a,b,c}` has been done). Would a list of combinations already tried (using a `Triplet`) and then seeing if p1,p2,p3 are in that combination in any order work? — Luke Moll, Jun 15 '16 at 14:17
{b,a,c} never happens because we say that second point has to be after first point (`i2 = i1+1`) and third point has to be after second point (`i3 = i2+1`). With 4 points you would have (in that order) {abc}, {abd}, {acd}, {bcd}. — GreenThor, Jun 15 '16 at 14:29

score 1 · Accepted Answer · answered Jun 15 '16 at 14:21

1

So if I understand correctly, you got a list of points. All these points are then looped over to create all possible triangles, and you put a random point in the largest triangle.

When the new point is added, you don't have to actually calculate everything again. You just have to calculate every triangle that uses the new point. All the others can be saved somewhere.

answered Jun 15 '16 at 14:21

Wesley De Keirsmaeker

1,026
9
29

I can't believe I missed this, I will try this. Thank you – Luke Moll Jun 15 '16 at 14:34
1

After rewriting my method, I saw a **HUGE** increase of performance. The time to calculate the next point dropped significantly ( [before](http://i.stack.imgur.com/JLv6n.png) , [after](http://i.stack.imgur.com/R5c62.png) ) – Luke Moll Jun 15 '16 at 17:15

score 0 · Answer 3 · edited May 23 '17 at 12:31

Since you know the polygons are triangles, you should swap Polygon#contains() for an algorithm that uses barycentric coordinates to find if the point is in a triangle. This will be faster because triangles have much simpler rules for containing a point than larger polygons.

Also, the POINTS should be sorted. That way you can iterate only over the points that come after each point. I currently can't think of a way to do this that isn't O(n²) or uses short-circuiting in some way, but it's a start.

Iterate over every triangle in a field of points

3 Answers3