Is there a way to get the indices from the original array of the triangle vertices?

[chetgnegy]

I imagine most people are using this to make a 3D mesh, not just trying to plot the result, and as such it would be nice to know which points in the input array make up each triangle. For example, if I know the input points are (0, 2) (.4, 0) (-.4, 0) (0, -2), I can run the algorithm and get two triangles. Suppose it tells me that the triangles are
(.4, 0) (-.4, 0) (0, -2) and (0, 2) (.4, 0) (-.4, 0). That's enough to draw lines, but if my goal is to tell OpenGL or something how to triangulate my points with an indexed VBO, I's like the answer in this form: 2,3,4 and 1,2,3. This allows me to reference the original vertex arrays if I want by iterating over the indices and doing vert[2], vert[3], vert[4].

I've tried doing pointer subtraction between the vertices array (both the original and the one owned by the Delauney class) and I'm getting out of bounds numbers:
for (const auto& tri : triangles) {
int index = tri.a - triangulation.getVertices();
// or
int index = std::distance(triangulation.getVertices(), tri.a);
}
I get negative numbers and things that indicate that the pointer doesn't point into that vector. If I'm not mistaken, I have to do a linear search through all of the input vertices for each point in the triangle and do floating point comparison to figure out the index. A linear search through each of the 4 points isn't a big deal, but O(N^2) isn't cool if I have a million. Am I missing something?

Thanks for writing this library, it does most of the heavy lifting for what I need.

[chetgnegy]

I've started reworking the code a bit. A lot of the floating point comparisons go away if you keep track of indices instead of raw points. There's a bit more indirection, though.

[chetgnegy]

Check this out. As far as I can tell it has all the same advantages as the checked in code, but it avoids a bunch of floating point math and has a lot of nice simplifications that fell out of using indices instead of raw coordinates.

Feel free to do whatever with this (or not).
https://pastebin.com/NtVzLSCn

Thanks again.

[bl4ckb0ne]

I have never used the algorithm in 3D, but i think it would be possible.

Your code seems fine, have you benchmarked it against the latest master? If you want it in the code you can make a pull request so I can properly review it.

[chetgnegy]

Ah, right. There's a detail I didn't mention. I make a 3D mesh by deforming the 2D surface. The convenient part is that I triangulate while it's still 2D so I don't have to deal with 3D triangulation. Now that I say this I'm wondering what other people are doing with the library, cause it might not be the same.

How do you envision checking this in might work? Algorithm changes aside, it's a pretty big refactor because it mostly removes the need for other headers. Are you OK with a breaking change? I put the code on pastebin so that those with the same need could fine it, but I feel like if I were to check it in I'd need to be aware of what your users are doing with this to know if it's a regression in some dimension I don't personally use it for or am not aware of.

[bl4ckb0ne]

I can release a new major and let people adapt to it. Regarding the tests there's a few test cases in the repo, otherwise it's a check by eye. If you're scared of the fallbacks, you can always for the project and maintain your fork as you need.

[chetgnegy]

I have a few tests as well that check that edges don't cross and the the number of triangles on a grid is correct. I'll try and find time for this this week.