Retain order of edges.

[DarrenlloydGent]

I've been using your awesome library in Unreal Engine 5 to deal with the triangulation of building data from Ordnance Survey shapefiles and DEFRA lidar data for height. The library works great in 2D, zipping through 100 square kilometers of London in seconds. However, I'm extruding the buildings to the heights identified and with the verts inserted in conforming and the fixedEdges returned with the lowest index first, I can't find a way to tell what vector the lines should be going, so that the extruded sides face the right way.

Below is an image of the problem. I thought of identifying if the difference between point indenices was more than +1 , then its dealing with an inserted vert and I should just flip, but it won't deal with the example here where three new verts were added on the same original edge.

Anything obvious I've missed? Below is a screenshot of all of the buildings...

[artem-ogre]

Hi @DarrenlloydGent, thank you your interest and for opening the issue.

If I understand correctly, would you like to know to which original edge the newly added points belong to?
This can be calculated on demand using the helper functions.

• Triangulation::pieceToOriginals maps each edge in the triangulation to the original constraint.
  For example if original edge (0,1) and point at index 2 was added like this:
  
  pieceToOriginals will look something like:

[(0,2)->[(0,1)], (1,2)->[(0,1)]]

• This piece->original edges mapping can be inverted to make it original edge -> pieces with EdgeToPiecesMapping. The example result should look like

[(0,1)->[(0,2),(1,2)]]

• It can be then passed to EdgeToSplitVertices to get mapping original edge->newly added split points. The example result should be:

[(0,1)->[0,2,1]]

The complete example is:

CDT::Triangulation<...> cdt = /*...*/;
const auto edge_to_split_points = 
    CDT::EdgeToSplitVertices(
        CDT::EdgeToPiecesMapping(cdt.pieceToOriginals), 
        cdt.vertices);

I hope this answers your question. Please let me know.

Note to myself: I need to improve the documentation and add examples to make this functionality more discoverable.

[DarrenlloydGent]

Hey @artem-ogre , got it! However... Not sure if it's me using this in Unreal Engine, but I had an issue with EdgeToSplitVertices. I kept getting errors with CDT.h, lines 412 and 433. It was complaining about the declarations obscuring previous declarations. So I changed the declarations on lines 412 and 414 from it to it2

for(EIt it2 = pieces.begin(); it2 != pieces.end(); ++it2)
{
   const array<VertInd, 2> vv = {it2->v1(), it2->v2()};

and on lines 433 and 435 from it to it3

for(SEIt it3 = splitVerts.begin() + 1; it3 != splitVerts.end() - 1; ++it3)
{
   val.second.push_back(it3->first);

And I got the desired output that I'll put in another post for anyone finding this and working with UE5.

[DarrenlloydGent]

So, anyone coming along after this using UE5,

auto EdgeToPieces = CDT::EdgeToPiecesMapping(cdt.pieceToOriginals);
auto cdtverts = cdt.vertices;
for (auto EdgeToSplitVertex : CDT::EdgeToSplitVertices(EdgeToPieces,cdtverts))
{
	UE_LOG(LogTemp, Log, TEXT("EdgeToSplitVertex %d %d"),EdgeToSplitVertex.first.v1(),EdgeToSplitVertex.first.v2());
	for (auto e : EdgeToSplitVertex.second)
	{
		UE_LOG(LogTemp, Log, TEXT("e = %d"),e);
	}
}

This produces output such as:
Log LogTemp EdgeToSplitVertex 74 75
Log LogTemp e = 170
Log LogTemp e = 169
Log LogTemp e = 171
Log LogTemp EdgeToSplitVertex 72 73
Log LogTemp e = 176

[artem-ogre]

Hey @artem-ogre , got it! However... Not sure if it's me using this in Unreal Engine, but I had an issue with EdgeToSplitVertices. I kept getting errors with CDT.h, lines 412 and 433. It was complaining about the declarations obscuring previous declarations.

Thanks for the find. I will rename the iterators to fix this.

[artem-ogre]

I will close this issue after merging the fix :)