Vertex handle usage after vertex removal

[weigangd]

Hello,

first of all thank you for sharing this library!

For my usecase I need to remove vertices often. But I also need to store some vertex handles for later. Like written in your documentation the removal function will invalidate all Handles.
Do you have a workaround for this like should i store points instead of the vertex handles.

If I were to try try alter the implementation, so that removal doesn't invalidate all handles, where should I start to look at. Do you have any hints for me?

Thanks

[Stoeoef]

Those are good points that you raise there. That use case certainly crossed my mind before (although I didn't need it myself yet).

Like written in your documentation the removal function will invalidate all Handles.

Well, there are a few more details that the docs (purposefully) don't mention:

• All (fixed) handles (vertex, edge, faces) are usize values behind the scenes
• The first inserted vertex has the handle value 0, the second 1... and so on. Inserting into a triangulation with n points will return a new handle with value n. (Exception: A vertex with the same position already exists, then the existing handle is returned)
• Removing a vertex will swap remove the vertex. That means: Only the vertex with the highest value is being invalidated and gets re-assigned the handle of the removed vertex. The vertex with the highest handle value is always triangulation.num_vertices() - 1 (prior to removal). This information may already be enough to track and update any stored vertex handle.
• Removing a vertex will also remove edges and faces. Their handles are swap removed as well. This is harder to track as multiple edges and faces get removed.

The reason why all of this is glossed over in the docs is to keep it as an implementation secret. However, there is no chance at the moment that that will change. Depending on your use case, tracking which vertex handles really get invalidated may already be enough.

Is this already sufficient? Or do you need a solution that does not invalidate any vertex handle (there are some)?

Let me know if you have any further questions!

[mikwielgus]

Just like the OP, I have a use case where vertexes are dynamically removed but handles of existing vertexes must never be invalidated. As is noted above, spade currently doesn't allow this because the .remove() method invalidates all vertex, edge, and face handles.

One way I can imagine spade supporting this is by having an option to use StableVec or thunderdome::Arena for the underlying collections of vertexes, edges, and faces instead of the currently used Vec with swap-remove.