title: How to detect if two paths intersect in android?
body: <p>I'm making a small <a href="https://en.wikipedia.org/wiki/Sprouts_(game)" rel="nofollow">sprouts</a> app where the user can draw paths between dots or on the screen with paths. I create arraylists of the coordinates of the paths and then attempt to compare them four points at a time to see if they intersect with paths already drawn. Right now, it isn't detecting any collisions. Here some of my code so far:</p>
  
  <pre><code>//ArrayList of the currentPath that is being drawn
  ArrayList&lt;float[]&gt; currentPath = new ArrayList&lt;&gt;();
  //ArrayList of Paths that have been drawn so far
  private ArrayList &lt;ArrayList&lt;float[]&gt;&gt; paths = new ArrayList&lt;&gt;();
  
  public boolean checkPath() {
          if (paths.size() == 0) {
          return true;
      } else {
          boolean noCollisions = true;
          for (int i = 0; i &lt; paths.size(); i++) {             //Loop through path array to compare each path
              for (int j = 0; j &lt; paths.get(i).size() - 1; j++) {  //Loop through each path to compare points
                  for (int k = 0; k &lt; currentPath.size() - 1; k++) {
                      float end1Y = currentPath.get(k + 1)[1];
                      float start1Y = currentPath.get(k)[1];
                      float start1X = currentPath.get(k)[0];
                      float end1X = currentPath.get(k + 1)[0];
  
                      float end2Y = paths.get(i).get(j + 1)[1];
                      float start2Y = paths.get(i).get(j)[1];
                      float start2X = paths.get(i).get(j)[0];
                      float end2X = paths.get(i).get(j + 1)[0];
  
                      double A1 = end1Y - start1Y;
                      double B1 = start1X - end1X;
                      double C1 = A1 * start1X + B1 + start1Y;
  
                      double A2 = end2Y - start2Y;
                      double B2 = start2X - end2X;
                      double C2 = A2 * start2X + B2 * start2Y;
  
                      double det = (A1 * B2) - (A2 * B1);
                      if (det == 0) {
                          //Lines are either parallel, are collinear or overlapping partially
                          if ((A1 * start2X) + (B1 * start2Y) == C1) {
                              //they are the on the same line, check if they are in the same space
                              if ((Math.min(start1X, end1X) &lt; start2X) &amp;&amp; (Math.max(start1X, end1X) &gt; start2X)) {
                                  noCollisions = false;
                              }
                              //one end point is okay, now checking the other
                              if ((Math.min(start1X, end1X) &lt; end2X) &amp;&amp; (Math.max(start1X, end1X) &gt; end2X)) {
                                  noCollisions = false;
                              } else{
                                  noCollisions = true;
                              }
                          }
                      } else {
                          //Lines intersect somewhere, but do the segments intersect?
                          double x = (B2 * C1 - B1 * C2) / det;
                          double y = (A1 * C2 - A2 * C1) / det;
  
                          //check to see if the intersection is within the bounding box of the segments.
                          if((x &gt; Math.min(start1X, end1X) &amp;&amp; x &lt; Math.max(start1X, end1X)) &amp;&amp; (y &gt; Math.min(start1Y, end1Y) &amp;&amp; y &lt; Math.max(start1Y, end1Y))){
                              //We are within the bounding box of the first line segment, now check the second
                              if((x &gt; Math.min(start2X, end2X) &amp;&amp; x &lt; Math.max(start2X, end2X)) &amp;&amp; (y &gt; Math.min(start2Y, end2Y) &amp;&amp; y &lt; Math.max(start2Y, end2Y))){
                                  //the segments intersect
                                  noCollisions = false;
                              }
                          } else {
                              noCollisions = true;
                          }
                      }
  
                  }
              }
          }
          return noCollisions;
      }
  }
  </code></pre>
  
  <p>I'm trying to use matrices and determinantes to figure out if there is any intersection occurring. </p>