Custom point type

[LeoPizzo1]

Now, to use the library, it is necessary to create the Vt2d<> vector. It should be interesting to allow the caller to use a different point type (i.e.: boost::geometry), to avoid useless data transfer. It will be interesting, as it is done in boost::geometry to allow the definition of a wrapper that doesn't rely on "x" and "y" fields directly, but mediated, allowing also to simple types like this to be used directly:

struct pt{
  double c[2];
};

[artem-ogre]

Boost is not a hard dependency of CDT and I would prefer to keep it that way.

One way is to implement a similar model-concept approach as in boost::geometry to support custom point types. It will require significant effort and will significantly reduce readability of the code. Maybe a simpler concept-based template duck typing approach can be used. Either way it requires a significant re-write, which I am not willing to do at the moment.

Pull-request or other help is welcome though :)

[LeoPizzo1]

It could be enough to define the point in a slightly different way and passing it to the Triangulation as a template argument:

template<class T>
struct Vtx2d
{
  T c[2];
  T& x(){ return c[0];} ///< X-coordinate
  T& y(){ return c[1];} ///< Y-coordinate
  const T& x( ) const  { return c[0]; } ///< X-coordinate
  const T& y( ) const  { return c[1]; } ///< Y-coordinate

  const double* raw( ) const { return c; }
  /// Create vector from X and Y coordinates
  static Vtx2d<double> make( const double x, const double y )
  {
    Vtx2d<T> out = { x, y };
    return out;
  }
};

template <typename T, class V2d = Vtx2D<t>  >
class Triangulation
{
  ...

The changes to the code should be really minimal. In this way, a user can, if needed, provide a custom type, considering it has the same functions defined in Vtx2d class.

Sometime it is important to associate to the point some information, related to the client software data structure, to make some reasoning after the tessellation. I.E.: if I am tessellating a 2d view of a 3d domain, I might already have the 3d points of the boundaries. I do non need to re-compute them from the 2d coordinates, if I can know what point it is that tessellation vertex. Now it is only possible specializing the V2d template for the data type ( in my case), before instantiating the Triangulation class:

namespace CDT {

struct TessPoint {
  int iIndex = -1;
  int iLoop = -1;
  bool Boundary = false;
};

template<>
struct V2d<double>
{
  double x; ///< X-coordinate
  double y; ///< Y-coordinate
  TessPoint data;  /// to retrieve the 3d point already computed
  const double* raw( ) const { return &x; }
  /// Create vector from X and Y coordinates
  static V2d<double> make( const double x, const double y )
  {
    V2d<double> out = { x, y, 0 };
    return out;
  }
  static V2d<double> make( const double* pt, int idx )
  {
    V2d<double> out = { pt[0], pt[1], {idx, -1, false} };
    return out;
  }
  static V2d<double> make( const double* pt, int idx, int loopIdx )
  {
    V2d<double> out = { pt[0], pt[1], {idx, loopIdx, (loopIdx > 0 ? true : false) } };
    return out;
  }
  static V2d<double> make( const double* pt, TessPoint &tessPt )
  {
    V2d<double> out = { pt[0], pt[1], tessPt };
    return out;
  }
  static V2d<double> make( const double* pt, int idx, int loopIdx, bool bound )
  {
    V2d<double> out = { pt[0], pt[1], {idx, loopIdx, bound} };
    return out;
  }
};
}

[artem-ogre]

@LeoPizzo1 After thinking more about this issue here are some thoughts I got.

When inserting new points into triangulation CDT will store copies of each point (2D coordinates X and Y).

I would like to understand better what problem would you like to solve. Depending on the problem there might be different ways to approach it:

1. I would like to have a more ergonomic API for inserting my custom points into CDT. Storing copies is fine as long as I have a convenient way to put my points in the triangulation. Answer: In that case I have a suggestion of API that takes a pair of iterators and you need to specify getters for X and Y for your custom point. For example it can be done by providing a function overload: double CDT::x(const MyCustomPoint& p)

2. I have extra information associated with my points. I would like to access this information after triangulation is performed. (e.g., TessPoint in your example). CDT storing copies is fine as long as I can associate extra-information with triangulation vertices. Answer: CDT will not change the order of points you insert. So you can use point indices to access extra information. One only needs to take into account that if super-triangle is not removed first 3 vertices will be auto-generated super-triangle vertices.

3. I would like CDT to use my custom points with extra data directly. Storing copies is not fine. I would like to inject my custom point-type in CDT. Answer: That's the trickiest case. The only solution I see is to implement a triangulation class that does not own vertices directly and has access to them via a pair or iterators. Re-implementing non-owing triangulation makes it harder to use for 90% of cases that don't require such tight integration. Another potential problem: is custom point has a lot of data attached to it -- that makes data less cache-friendly and performance can suffer as a result.

[LeoPizzo1]

@artem-ogre Thanks for your thoughts, now some of mine.

1. It is fine for me to have a copy of the points inside the tessellation. The iterator range insertion is really interesting: maybe a user need to tessellate just a small part of a enormous vector. What I would like to avoid, generally, is the double copy of the data as vectors: MyPoint->CDT::V2d->CDT::Tessellation::vertices Usually an already existing application already has its 2d point (used maybe in basic geometry), thus adding a function overload can be a mess because of un-needed #include (it must derive from a base class). A possible solution is to furthermore templatize the insertVertices method, providing an optional template parameter, an object that is able to extract the x and y value from the custom point type: something like this:

   
   struct pt2d {
   double c[2];
   };

template class ptExtractor { public: inline V2d operator()( const pt2d& pt ) const inline { return V2d::make(pt[0], pt[1]); } };

template class V2dExtractor { public: inline V2d operator()( const V2d& pt ) const inline { return pt; } };

template class Triangulation { public: ... template<class PT_T, class V2D_EXTRACTOR = V2dExtractor > void insertVertices( const std::vector& newVertices ) { if( vertices.empty( ) ) addSuperTriangle( Box2d::envelop< V2D_EXTRACTOR>( newVertices ) ); vertices.reserve( vertices.size( ) + newVertices.size( ) ); V2d pos; typedef typename std::vector::const_iterator Cit; for( Cit it = newVertices.begin( ); it != newVertices.end( ); ++it ) insertVertex( V2D_EXTRACTOR( )( (*it) ) ); }

A little bit similar to what is done in the std::sort algorithm when you need to provide a custom comparer.
I didn't test the code: it might even not compile, and also the Box2d::envelope function should be templatized, too.
Probably a more elegant declaration/implementation can be done if it is allowed to use C++14/17 .

2. I understand your point, and I can agree, but for the case of usage of RemoveDuplicate and RemapEdges. I didn't yet dig into the functions yet, but I guess that with some degree of complexity it will be solvable. 

3. It is not the case, **for my needs**, once agreed that at least a copy is mandatory to get a correct, fast and stable implementation.

Generally speaking, to improve the interface and to make it more general, I continue proposing you to allow to specify the point type as a template parameter, and pass through functions when accessing to coordinates, like this:

template struct V2d { T x; ///< X-coordinate T y; ///< Y-coordinate

inline const T& X( ) const { return x; }
inline const T& Y( ) const { return y; }
inline T& X( ) { return x; }
inline T& Y( ) { return y; }

/// Raw address getter to use as plain array T[3]
const T* raw() const;
/// Create vector from X and Y coordinates
static V2d make(const T x, const T y);

};

template <typename T, typename POINT_T = V2d > class Triangulation { public: ... ...

If the user has a real need of using its point type, then it is possible, provided that the X() and Y() functions are defined in the custom point type.
If the custom point has a lot of data attached, then it will be up to it to take care.
It could be even more general, and easy, to use the index access rather than the variable access in the point data structure:

template struct V2d { T c[2]; ///< coordinates inline const T& operator[]( int idx ) const { return c[idx]; } inline T& operator[]( int idx ) { return c[idx]; } /// Raw address getter to use as plain array T[2] const T* raw( ) const { return &c[0]; } /// Create vector from X and Y coordinates V2d( const T x, const T y ) { c[0] = x; c[1] = y; } V2d( ) { c[0] = c[1] = 0.; } };

Consider that these are only my considerations, based on my experience.
I can survive with solution of point 1, if I am able to solve the mess problem at point 2 (remapping for duplication).
I agree that these are not "easy" changes, that need a deep reasoning before deciding to go or drop them, but, please, keep thinking on them.

[artem-ogre]

@LeoPizzo1 I've made a PoC that uses iterator ranges and function objects for X and Y getters to provide generic way of dealing with custom point types. Please let me know what you think and feel free to ask if you have any questions.

[artem-ogre]

For your example above the usage should look like that:

struct pt2d { double c[2]; };
double getX(const pt2d& p) { return p.c[0]; }
double getY(const pt2d& p) { return p.c[1]; }

std::vector<pt2d> points = ...;
triangulation = CDT::Triangulation<double>(...);
triangulation.insertVertices(points.begin(), points.end(), getX, getY);

Also generic variants of functions for dealing with duplicates were added.

[LeoPizzo1]

Yes, it seems reasonable, too. My suggestion allows to specify a default behaviour as per std:: implementations with an extractor class, your one uses functions, but the underlying logic is the same.

[artem-ogre]

Hi, just FYI there was a fix in #25 so it is now possible to pass lambdas or functors to insertVertices and insertEdges :)

[LeoPizzo1]

Great!

On Fri, 27 Nov 2020 at 08:51, Artem Amirkhanov notifications@github.com wrote:

Hi, just FYI there was a fix in #25 https://github.com/artem-ogre/CDT/pull/25 so it is now possible to pass lambdas or functors to insertVertices and insertEdges :)

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/artem-ogre/CDT/issues/21#issuecomment-734696554, or unsubscribe https://github.com/notifications/unsubscribe-auth/AROY35OBN7DKQOMQ6BDGOGLSR5K7LANCNFSM4TD3AL7Q .