title: QuadTree Triangle insert and search
body: <p>I am trying to implement QuadTree data structure with triangle objects, so I can do ray triangle intersection. But it is querying unnecessary triangles. I don't know if that is a property of QuadTree's.</p>
  
  <p>Here is my QuadTree insert code:</p>
  
  <pre><code>//First check if triangle is inside the node box. If it does,
  //then subdivide until to insert triangle into the lowest node.
  //If it doesn't insert into its child, then insert into the root's
  //data.
  bool insert(const Triangle&amp; triangle, uint depth = 0) {
      if (!triangle.isInside(bound) || depth &gt;= 10) return false;
      if (!divided) subdivide();
      //insert into root if no nodes can support it
      if (!(NW-&gt;insert(triangle, depth + 1) || NE-&gt;insert(triangle, depth + 1) ||
          SW-&gt;insert(triangle, depth + 1) || SE-&gt;insert(triangle, depth + 1))) {
          triangles.push_back(triangle);
      }
      return true;
  }
  </code></pre>
  
  <p>Search code: </p>
  
  <pre><code>void searchTriangles(const QuadTree&amp; tree, const Line&amp; line, vector&lt;Vertex&gt;&amp; vertices, Color color) {
      Vector2f hit;
      const Boundary* treeBounds = tree.getBound();
      //if ray doesn't intersect the box, then exit.
      if (!intersect(treeBounds-&gt;topLeft, treeBounds-&gt;bottomRight, line.p1, line.p2, hit)) return;
  
      //Get all the triangles from this node and childern.
      const vector&lt;Triangle&gt;* triangles = tree.getTriangles();
      for (const Triangle&amp; t : *triangles) {
          vertices.push_back(Vertex(Vector2f(t.getP1()-&gt;x, t.getP1()-&gt;y), color));
          vertices.push_back(Vertex(Vector2f(t.getP2()-&gt;x, t.getP2()-&gt;y), color));
          vertices.push_back(Vertex(Vector2f(t.getP3()-&gt;x, t.getP3()-&gt;y), color));
      }
      if (!tree.subdivided()) return;
      searchTriangles(*tree.getNW(), line, vertices, color);
      searchTriangles(*tree.getNE(), line, vertices, color);
      searchTriangles(*tree.getSW(), line, vertices, color);
      searchTriangles(*tree.getSE(), line, vertices, color);
  }
  </code></pre>
  
  <p>Example output: </p>
  
  <p><img src="https://i.imgur.com/9wbgdpn.png" alt="Example Output"></p>