Generic interface for both integer and floating-point triangulation

[mikwielgus]

It would be nice to not have to decide whether to use floats or integers. Currently, it seems to me that this is impossible -- IntTriangulation works only on i32, whereas Triangulator::triangulate() requires the scalar type to implement FloatNumber, which is currently only implemented for f32 and f64.

It should be possible to use traits to make the current floating-point triangulation interface more generic to also accept integers by implementing the current conversion from and to floats as an identity map for integers.

This would be useful for me because I have a preference for writing code that is generic over both integers and floats to cover more applications. Though in computer graphics, video games, and mechanical CADs floating-point coordinates have been the usual choice for over two decades, fixed-point integer coordinates do not suffer from numerical inrobustness and continue to be widely used in EDA software.

[NailxSharipov]

I'd avoid mixing the float and int APIs.

For most projects, the float API is the better default because it is simpler and easier to use. For large projects, the choice between float and int is important enough to make a concrete choice.

Even if the APIs look similar, they have different tradeoffs and behavior. Combining them into one generic interface could make that distinction less clear and make the API harder to reason about.

[mikwielgus]

From the perspective of a developer of a user-facing project, this makes sense. But I'm developing a library (for any-angle pathfinding), and I don't want to impose my choice on the downstream programmer (especially given that I am going to choose integers). While at the same time I also don't want to have duplicate code to be able to handle both ints and floats.

I can manage this on my end of course. I will create and implement my own traits that demultiplex to the int and float triangulation. They will look more or less like this:

pub trait NetTriangulate<K> {
  type Output: NetTriangulation<K>;

  fn net_triangulate(&self) -> Self::Output;
}

pub trait NetTriangulation<K> {
  fn triangle(index: TriangleIndex) -> [[K; 2]; 3];
  fn neighbors(index: TriangleIndex) -> [TriangleIndex; 3];
}

However, since this is an adapter that is glued only towards i_triangle and nothing else, it may be useful to have this capability upstreamed in some form.

[mikwielgus]

While we're at it:

I'm looking now at i_triangle::float::delaunay::Delaunay and see no way to access adjacency data of triangles (i.e. every triangle's list of neighbors). This makes it impossible for me to run a pathfinding algorithm on the triangulation faces over the floating-point Delaunay triangulation here. I can still do this with ints because i_triangle::advanced::delaunay::IntDelaunay's fields are all public.

[NailxSharipov]

Internally, my libraries are based on integer math. The float API is mostly a convenience wrapper around that integer pipeline. So if you are building another library on top of iTriangle and want to support both int and float, I would recommend following the same structure: implement the core logic using int logic, then provide a float wrapper that converts into that representation.

[mikwielgus]

Internally, my libraries are based on integer math. The float API is mostly a convenience wrapper around that integer pipeline. So if you are building another library on top of iTriangle and want to support both int and float, I would recommend following the same structure: implement the core logic using int logic, then provide a float wrapper that converts into that representation.

Thank you for the explanation of your decision.

Then instead of this, I would like to ask for a different, smaller addition: simple single-method interfaces to obtain the adjacency data from Delaunay, IntDelaunay, RawIntTriangulation.

Adjacency data is useful for performing pathfinding (using e.g. Dijkstra, A* algorithms) over triangulation faces. Right now, it seems to me that it's not possible to obtain this data from the floating-point triangulations and also from RawIntTriangulation.

I have opened a PR for that: #12

[NailxSharipov]

In version 0.45.0, I added generic support for integer types.

It does make the internal math a bit more complex, but from the user’s perspective, I think the result is very convenient.

[mikwielgus]

I appreciate this, but I'm personally interested in having a generic interface that works not just on different types of integers, as you implemented now, but also on floats, because I tend to write code that is generic over scalar types.

But either way, this is not much of an issue. I can always create my own higher-level interfaces when I need them.

In case you are interested how this looks like on my end, here's code for a wrapper that I created for my own purposes over your other library, i_overlay, to have my library (still WIP) have a scalar-generic interface for boolean operations on polygons.

[mikwielgus]

I have implemented this today because I need this for myself anyway. I have opened a PR for you to have an opportunity to look at this, in case you would like to see how this would work or reconsider it nevertheless.