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

It is normally good to break code into several methods. Everything that is inside your

if(!hit.equals(p) && !me.equals(p))

should be moved to a separate method taking as input those 3 points a,b and c

When coding problems of a mathematical flavor it is often very useful to support your code with some kind of theory.

In this case you might want to look up the mathematical terms "dot product" and "cross product". Once you understand those it becomes easy to implement your function.

And remember to make several functions (dotProduct() and crossProduct()) so you can reuse code later.

When it comes to performance you need to look at your algorithm. There is no need to test all pairs of points (hit, p). Maybe you should make a small method that computes the angle of a vector from me to p? If angle is the same they hit, otherwise they miss.

So the question becomes given a list of angles for points in hits and a list of angles in reachable, do they contain a common angle?

Answer 2

I have some suggestions.

Those will not help to make the code faster but cleaner.

Extract some of the logic to methods.

By doing that you will make the code shorter and easier to read. Also, you will be able to remove the comments if the methods name is descriptive enough.

Examples :

    private static boolean isOnSameLine(double py, int px, double m, double b) {
        return py == ((m * px) + b);
    }

    private static boolean isUndefinedSlope(int hitx, int mex) {
        return hitx - mex == 0;
    }

Invert the logic to remove arrow code

In your code, you can invert the if condition to remove one layer of bracket.

//[...]
if (hit.equals(p) || me.equals(p)) {
   continue;
}
//[...]

Extract the expression to variables when used multiple times.

In your code, you have multiple instances where you could extract the evaluations into variables.

int py = p.y;
int hitx = hit.x;
int mex = me.x;

Refactored code

public static void main(String[] args) {
   int numHits = 0;
   Point me = new Point(); //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)) {
            continue;
         }


         //find the equation of a line from me to hit
         int py = p.y;
         int hitx = hit.x;
         int mex = me.x;

         if (isUndefinedSlope(hitx, mex)) {
            if (isOccupiedPointBetweenMeAndHit(me, hit, p, py, hitx, mex)) {
               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 = hitx - mex;

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

            if (isOnSameLine(py, p.x, m, b)) {
               if (isPointBetweenMeAndHit(hitx, mex, hit.y, me.y, py, p.x)) {  //if the point is in between me and the hit
                  numHits--;
                  break;
               }
            }
         }
      }
   }
}

private static boolean isOccupiedPointBetweenMeAndHit(Point me, Point hit, Point p, int py, int hitx, int mex) {
   return (((py <= hitx) && (py >= me.y)) || ((py >= hit.y) && (py <= me.y))) && p.x - mex == 0;
}

private static boolean isPointBetweenMeAndHit(int hitx, int mex, int hity, int mey, int py, int px) {
   return (px <= hitx && px >= mex && py <= hity && py >= mey) ||
          (px <= hitx && px >= mex && py >= hity && py <= mey) ||
          (px >= hitx && px <= mex && py >= hity && py <= mey) ||
          (px >= hitx && px <= mex && py <= hity && py >= mey);
}

private static boolean isOnSameLine(double py, int px, double m, double b) {
   return py == ((m * px) + b);
}

private static boolean isUndefinedSlope(int hitx, int mex) {
   return hitx - mex == 0;
}

Answer 3

(just rewriting, @mlb solution)

Let solve the Algorithm then improve the code

$$ \text{Let }X = \{x_0, x_1, x_2, ... x_p\} \text{ points.}$$ $$ \text{Let }S = \{ \text{all the pairs }(x_i, x_j): i \neq j, (x_i, x_j) \in X\times X\} $$

$$\text{A point }x_m\text{ lies on some segment on } s \in S: \text{ if } \exists i,j,k: (x_i,x_j) \in S\text{ , }(x_i, x_k) \in S\text{ , and }(x_i, x_j) \| (x_i, x_k)$$ In that case, m can be all the three index. We don't know yet. To solve that issue, points need to be sorted.

To detect if two segments are parallels, you have some options. a) just take the difference between the points and normalize. b) calculate the slope of the two segments. They should be the same.

Now, the efficient solution

$$\text{First of all, the solution is }O(N^2)\text{, } $$ $$\text{because creating segments from all the points is }O(N^2).$$

To keep that complexity, operations over segments should be done in constant time.

The idea is keep track of all "lines" that a segment lies on. For each new segment, we verify if the line was already found in our map.

A line is defined by a point and the slope. To be consistent, let us take the point at x coordinate equals to 0. The point would the format (y, 0). There is an edge case when slopes is orthogonal to x-coordinate. In that case, we can take y=0.

public class Line {
    private final Double slope;
    private final Double y_0;
    // override equals and hashcode
    // override the constructor
}

Also, creates a class Point that implements Comparable. One point is less than other point if comes before (x coordinate is less than) and below (as second criteria, y coordinate is less than) the other point.

Sort all the points.

Now, you can build a map Map(Line, List(Point)) and verify for each segment if the same line was already add to the map.

All the points between the last element of the List and the first element of the List are points between other two points.