title: Checking if two cubic Bézier curves intersect
body: <p>For a personal project, I'd need to find out if two cubic Bézier curves intersect. I don't need to know where: I just need to know if they do. However, I'd need to do it fast.</p>
  <p>I've been scavenging the place and I found several resources. Mostly, there's <a href="https://stackoverflow.com/questions/109364/bezier-clipping">this question here</a> that had a promising answer.</p>
  <p>So after I figured what is a <a href="http://en.wikipedia.org/wiki/Sylvester_matrix" rel="noreferrer">Sylvester matrix</a>, what is a <a href="http://mathworld.wolfram.com/Determinant.html" rel="noreferrer">determinant</a>, what is a <a href="http://mathworld.wolfram.com/Resultant.html" rel="noreferrer">resultant</a> and <a href="https://stackoverflow.com/questions/109364/bezier-clipping#comment-4332265">why it's useful</a>, I thought I figured how the solution works. However, reality begs to differ, and it doesn't work so well.</p>
  <hr />
  <h1>Messing Around</h1>
  <p>I've used my graphing calculator to draw two Bézier splines (that we'll call B<sub>0</sub> and B<sub>1</sub>) that intersect. Their coordinates are as follow (P<sub>0</sub>, P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub>):</p>
  <pre><code>(1, 1) (2, 4) (3, 4) (4, 3)
  (3, 5) (3, 6) (0, 1) (3, 1)
  </code></pre>
  <p>The result is the following, B<sub>0</sub> being the &quot;horizontal&quot; curve and B<sub>1</sub> the other one:</p>
  <p><img src="https://i.stack.imgur.com/ZYVaW.png" alt="Two cubic Bézier curves that intersect" /></p>
  <p>Following directions from the aforementioned question's top-voted answer, I've subtracted B<sub>0</sub> to B<sub>1</sub>. It left me with two equations (the X and the Y axes) that, according to my calculator, are:</p>
  <pre><code>x = 9t^3 - 9t^2 - 3t + 2
  y = 9t^3 - 9t^2 - 6t + 4
  </code></pre>
  <hr />
  <h1>The Sylvester Matrix</h1>
  <p>And from that I've built the following Sylvester matrix:</p>
  <pre><code>9  -9  -3   2   0   0
  0   9  -9  -3   2   0
  0   0   9  -9  -3   2
  9  -9  -6   4   0   0
  0   9  -9  -6   4   0
  0   0   9  -9  -6   4
  </code></pre>
  <p>After that, I've made a C++ function to calculate determinants of matrices using <a href="http://en.wikipedia.org/wiki/Laplace_expansion" rel="noreferrer">Laplace expansion</a>:</p>
  <pre><code>template&lt;int size&gt;
  float determinant(float* matrix)
  {
      float total = 0;
      float sign = 1;
      float temporaryMatrix[(size - 1) * (size - 1)];
      for (int i = 0; i &lt; size; i++)
      {
          if (matrix[i] != 0)
          {
              for (int j = 1; j &lt; size; j++)
              {
                  float* targetOffset = temporaryMatrix + (j - 1) * (size - 1);
                  float* sourceOffset = matrix + j * size;
                  int firstCopySize = i * sizeof *matrix;
                  int secondCopySize = (size - i - 1) * sizeof *matrix;
                  memcpy(targetOffset, sourceOffset, firstCopySize);
                  memcpy(targetOffset + i, sourceOffset + i + 1, secondCopySize);
              }
              float subdeterminant = determinant&lt;size - 1&gt;(temporaryMatrix);
              total += matrix[i] * subdeterminant * sign;
          }
          sign *= -1;
      }
      return total;
  }
  
  template&lt;&gt;
  float determinant&lt;1&gt;(float* matrix)
  {
      return matrix[0];
  }
  </code></pre>
  <p>It seems to work pretty well on relatively small matrices (2x2, 3x3 and 4x4), so I'd expect it to work on 6x6 matrices too. I didn't conduct extensive tests however, and there's a possibility that it's broken.</p>
  <hr />
  <h1>The Problem</h1>
  <p>If I understood correctly the answer from the other question, the determinant should be 0 since the curves intersect. However, feeding my program the Sylvester matrix I made above, it's -2916.</p>
  <p>Is it a mistake on my end or on their end? What's the correct way to find out if two cubic Bézier curves intersect?</p>