Are there better ways to find all triangles containing a certain edge?

[pan3rock]

My project involves an operation of find all triangles containing a certain edge, similar to MATLAB function edgeAttachments. Through the profile analysis, this operation accounted for more than 80% of the total runtime in my project. Could anyone provide some suggestions to make it faster? My Implements with a simple example is provided below. Any advice is welcome.

#include <CDT.h>

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

using V2d = CDT::V2d<double>;

CDT::TriangleVec edge_attachments(const CDT::TriangleVec &elements,
                                  const CDT::Edge &edge) {
  auto v1 = edge.v1();
  auto v2 = edge.v2();
  CDT::TriangleVec attach;
  for (auto it = elements.begin(); it != elements.end(); ++it) {
    if (it->containsVertex(v1) && it->containsVertex(v2)) {
      attach.push_back(*it);
    }
  }
  return attach;
}

int main() {
  // generate random nodes
  std::random_device dev;
  std::mt19937 rng(dev());
  std::uniform_real_distribution<double> dist(0.0, 1.0);
  const int num_node = 5000;
  std::vector<V2d> nodes;
  for (int i = 0; i < num_node; ++i) {
    double x = dist(rng);
    double y = dist(rng);
    nodes.push_back(V2d::make(x, y));
  }

  CDT::Triangulation<double> cdt;
  cdt.insertVertices(nodes);
  cdt.eraseSuperTriangle();
  auto elements = cdt.triangles;
  auto edges = CDT::extractEdgesFromTriangles(elements);

  auto start = std::chrono::high_resolution_clock::now();
  for (auto it = edges.begin(); it != edges.end(); ++it) {
    auto attach = edge_attachments(elements, *it);
  }
  auto stop = std::chrono::high_resolution_clock::now();
  auto duration =
      std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
  std::cout << "Elapsed time: " << duration.count() << " ms" << std::endl;
  return 0;
}

[artem-ogre]

There is a private method in Triangulation called edgeTriangles you could make it public and see if it is fast enough for your needs. If you want the absolutely fastest lookup possible and are willing to sacrifice some preprocessing time and some memory, the fastest way would be to generate an unordered_map that maps edges to triangles. It can be created with a single pass over all the triangles.

[pan3rock]

Thanks for your suggestion. I used the way of unordered_map and reduced percentage of elapsed time to 12%. Thanks again for CDT, it helped me a lot!