Proposal: Computational geometry?

[JesseTG]

I'm taking a computational geometry course this semester, and I'm gonna practice it by implementing a bunch of algorithms (triangulation, convex hull, etc.) as GLM functionality and sending a PR. I get to flex my algorithms muscles, and you (and all GLM users, including myself) get the fruits of my labor. Win-win.

My real question; how do you want users to actually interact with it? Do you want me to just take in a Container (where Container is a templated data structure; e.g. std::vector or std::set, etc.) and spit out another one? Do you want me to screw around with input/output iterators as is common in the <algorithm> header?

[Groovounet]

Even if this sounds great, I think it's beyond the scope of GLM. Actually, I thought myself that it could be a great library to make but obviously my time is too limited and already well consumed.

So personally I would encourage you to create such library and if you use GLM, it's still a win win for the GLM community. ;)

[JesseTG]

I'm not talking about anything nearly as complicated as, say, CGAL or Boost.Geometry. Just a few simple functions that are often used in graphics anyway (e.g. convex hulls). That's what your whole GTC/GTX/etc. convention is for, isn't it?

[Groovounet]

Oh yes, that could definitely go into GTX extensions.

[JesseTG]

Excellent. I'll send a PR in a few days when I have something to show.

(Also, some CG libraries let you use your own custom types with a bit of template magic. I might also submit PRs that do that template magic for you as another GTX.)

[regnirpsj]

@JesseTG, how about providing both interface versions, i.e.

template <typename InputIt, typename OutputIt>
OutputIt algotithm(InputIt first, InputIt last)
{
  // ...
}

template <typename Container, typename OutputIt>
OutputIt algotithm(Container& c)
{
  return algorithm(c.begin(), c.end());
}

this supports ranges not encompassing a whole container as well as (probably) allowing

algotrithm({vec4(), vec4(), ...});

[JesseTG]

Should there be an OutputIt in the input as well, in case you want to put the result in another container? Or do people not actually do that?

Also, should I create a whole new vector or similar, or use an existing one?

[regnirpsj]

well, that depends; the pseudo code above is just that: pseudo code. usually there are different kinds of algorithms [see http://en.cppreference.com/w/cpp/algorithm] providing different contracts (e.g., modifiying, non-modifying, partitioning, sorting). the STL prefers to use iterator ranges for algorithm interfaces because then nothing needs to be assumed about the container (other than iterator properties). however, sometimes working on a container instead of an iterator range is more convenient; the above pseudo code only shows that the implementation effort can be made minimal with the container version essentially only being a wrapper around the iterator version.

actually, [http://www.amazon.com/Generic-Programming-STL-Extending-Standard/dp/0201309564] provides a much more in-depth discussion.

[JesseTG]

Yeah, I know about all of that. Algorithm X won't modify the input, while Algorithm Y will go through the input in multiple passes, etc. and I need to ensure that any iterators I use won't break those rules.

I'm asking about what iterator contracts best describe actual GLM use cases.

[regnirpsj]

probably only these:

• input
  • InputIterator (r/o, single)
  • ForwardIterator (r/o, multiple)
• output
  • OutputIterator (w/o, single)

so the convex_hull i/f may look like this:

template <typename ForwardIt, typename OutputIt>
OutputIt convex_hull(ForwardIt first, ForwardIt last, OutputIt destination);

where [first, last) is the input range, destination the start of the output range and the return value indicates the past-of-end element in the output range after convex_hull has finished.

also, i retract asking for a container i/f; that can be added later.

[JesseTG]

I'm still gonna add a container interface anyway. But yes, this too.

[plasmacel]

There is a bunch of way to do convex hulls. Each of them are different in the aspect of construction, dimensionality, performance and precision. If you pick a convex hull method and distribute it with glm, then pick the most advantageous for general usage. However if someone needs to use a convex hull algorithm then that person probably also needs some other geometric functionality. CGAL and similar libraries are complete overkill, a good glm-like computational geometry library would be great, but it's a much higher level of functionality beyond the scope of glm and worths a separate project. So I don't think it's a good direction.

[JesseTG]

You know, on further consideration, I think it might just be a better idea to add a compatibility layer with Boost's math libraries (with a bit of template magic you can use any vector type, including GLM's) as an extension. I'll write up a PR for that at some point soon.