How can I optimize my code that uses nested for loops?

Question

I am working to solve a problem where I need to determine if a Point lies on a line connecting two other Points. For example, if I have Point a, b, c, I want to determine if c is on the line segment connecting a and b. In my code, I have a point, me (a in the example) and two lists of points, hits (b in the example) and reachable (c in the example). For each point in hits, I want to determine if there is any point in reachable that is on the line segment that connects me and the point in hits. If there is a point on that line segment, then numHits needs to be decremented. Here is my code:

Point me; //Point a from the example above
ArrayList<Point> hits = new ArrayList<>();  //a list of Point b's from the example above
ArrayList<Point> reachable = new ArrayList<>();  //a list of point c's from the example above

for(Point hit : hits) {
    for(Point p : reachable) {
        if(!hit.equals(p) && !me.equals(p)) {
            //find the equation of a line from me to hit
            if(hit.x - me.x == 0) { //if the line has an undefined slope... if the line is vertical
                if( (((p.y <= hit.y) && (p.y >= me.y)) || ((p.y >= hit.y) && (p.y <= me.y))) && p.x - me.x == 0) {  //if there is any occupied point on that line in between me and the hit, that point blocks the hit
                    numHits--;
                    break;
                }
            } else {
                //create a line from me to the hit... if there is any occupied point on that line in between me and the hit, that point blocks the hit
                double deltaY = hit.y - me.y;
                double deltaX = hit.x - me.x;

                double m = deltaY / deltaX; //slope
                double b = me.y - (double)(m*me.x);  //y intercept

                if((double) p.y == ((double)(m * p.x) + b)) {  //if this point is on the same line 
                    if( ((p.x <= hit.x && p.x >= me.x) && (p.y <= hit.y && p.y >= me.y)) ||
                                ((p.x <= hit.x && p.x >= me.x) && (p.y >= hit.y && p.y <= me.y)) || 
                                ((p.x >= hit.x && p.x <= me.x) && (p.y >= hit.y && p.y <= me.y)) ||
                                ((p.x >= hit.x && p.x <= me.x) && (p.y <= hit.y && p.y >= me.y))) {  //if the point is in between me and the hit
                        numHits--;
                        break;
                    }
                }
            }
        }
    }
}

My code works to determine if there is any point in reachable between me and each point in hits, it just gets incredibly slow the larger hits and reachable get. For example, if hits has a size of 780,000 and reachable has a size of 1,500,000 the code takes a very long time to run. I was wondering how I may be able to optimize this to run more quickly. I'm not sure if the bottleneck issue lies in the loops themselves or in the code within the loops. Any help or optimization ideas are greatly appreciated. Thank you!

Answer 1

Project each line ac to x = 0 or y = 0, whichever is of smaller magnitude (so as to minimize rounding errors). Sort or hash these intercepts, keeping a reference to each c, making sure to preserve duplicates.

Then for each line ab, project that also to x = 0 or y = 0, whichever is of smaller magnitude, and search a matching intercept in your sorted or hashed collection. This gives you a small number of candidate line segments which all lie on the same line through a, b and c; you only need to check that the point lies within the endpoints (a.x < c.x < b.x or a.x > c.x > b.x and again for y).

Be careful about rounding errors.

Answer 2

One way you can optimise the code is by shifting the point me to origin, after that divide all points to respective quadrants, so now you only have to compare the points which are in same quadrants.

I will write a rough algorithm below.

1. Shift the point me to origin

2. Shift all other points, ie hits and reachable to origin ( this can be done by  subtracting X and Y of point me from all other X and Y ) 

3. Now divide hits and reachable to 4 quadrants based on their X and Y components, now you will have 4 arrays for hits and 4 arrays for reachable


4. You can also reduce the number of points in reachable by comparing them against the greatest point in hits like below, do this for all quadrants


    a. find greatest |X| (mode(X)) and greatest |Y| of hits in each quadrant, lets call it me.|x| and me.|y|

     b. for(Point p : reachable) {
              if(p.|x| > me.|x| or p.|y| > me.|y|) then remove p from reachable }
    since these points will be outside of the  line segment formed by me and hits

5. Now you can compare the values, using nested for loops as you did, you will have to use different conditions for each quadrant

Don't forget to add edge conditions and to shift back from origin

Answer 3

I recommend you look at Line2D.Double. It has many methods including ones to determine if a point or even a line is on a given line segment.

I would also suggest that you use a map to memoize existing points and other information that you may have already encountered. That way you won't keep repeating calculations. Because floating point operations can result in miniscule differences you will probably have to use some acceptable error to determine the validity of the result.