Possible to export a vector of all (not just fixed) unique edges in a triangulation?

[ilia-nikiforov]

Hi, my question is in the title. I already have a pretty fast way to do this as a post-processing step, but I was wondering if there was a neater built-in way that I was missing. Thank you!

[artem-ogre]

@ilia-nikiforov thank you for the question. You are right: edges are not stored explicitly and need to be extracted from the triangles. There is no built-in way of doing so. It could be added to the API as a free function, I think it could be useful. How do you extract edges now?

[ilia-nikiforov]

Hi @artem-ogre
The implementation I have right now is for http://paulbourke.net/papers/triangulate/, I am switching to CDT because I need constraints. I use an unordered_set. The implementation for CDT will be very similar and probably a little neater, because you use an array of vertices for each triangle instead of separate variables for each vertex.

class TedgeCompare {
public:
	bool operator()(const Tedge& e1, const Tedge& e2) const
	{
		return ((e1.v1 == e2.v1) && (e1.v2 == e2.v2));
	}
};

class TedgeHash {
public:
	size_t operator()(const Tedge& e) const
	{
		return (hash<int>()(e.v1));
	}
};

void extractEdges(unordered_set <Tedge, TedgeHash,TedgeCompare>& sEdge, const triMesh& mesh)
{
	sEdge.clear();
	for (int i = 0; i < mesh.nTri; i++)
	{
		ITRIANGLE curTri = mesh.aTri[i];
		if (curTri.p1 > curTri.p2) sEdge.insert({ curTri.p2, curTri.p1 });
		else sEdge.insert({ curTri.p1, curTri.p2 });

		if (curTri.p2 > curTri.p3) sEdge.insert({ curTri.p3, curTri.p2 });
		else sEdge.insert({ curTri.p2, curTri.p3 });

		if (curTri.p3 > curTri.p1) sEdge.insert({ curTri.p1, curTri.p3 });
		else sEdge.insert({ curTri.p3, curTri.p1 });
	}
}

[artem-ogre]

@ilia-nikiforov
Great, same approach was the first thing that came to my mind too.
CDT already supports hashing edges and using smaller vertex index as a first edge's vertex, so the code to extract edges is very minimal.
Here's a PR: #55
I did not test this but I can merge it after you confirm that it works for you.

[ilia-nikiforov]

@artem-ogre May be a week or two until I try it, but I will definitely let you know. Cheers!

[ilia-nikiforov]

@artem-ogre I see that you've already merged it, but I can confirm that it works for my needs. CDT is very fast, thank you for your work!

[artem-ogre]

@ilia-nikiforov Awesome! :)

[ilia-nikiforov]

@artem-ogre If you are wondering why I need the edges, there is a very highly cited method for creating variable-density meshes that involves a mechanics analogy where the edges of a triangulation are springs, and the desired local density is achieved by minimizing the force of those springs:
http://persson.berkeley.edu/distmesh/persson04mesh.pdf

Thank you for your work!