[Feature request] Dynamic planar convex hull

[sumeetshirgure]

Issue Details

I propose CGAL support real time dynamic planar convex hulls implemented as part of the software library. It has documented applications that can be found in the references in this Wikipedia page.

Source Code

I have implemented a header library that is robust and exact, and I'd like to integrate it with CGAL. Link to the repo.

[afabri]

Hello, Thank you for your proposal. Did you compare it with the CGAL 2D Delaunay triangulation? It is also dynamic and the vertices incident to the infinite vertex are the convex hull. Best, Andreas

[sumeetshirgure]

You're right, the Delaunay triangulation's boundary is the convex hull. But the data structure used to store a triangulation doesn't allow for quickly querying tangents and extreme point queries using binary search. I don't mean to imply that there are applications in computer graphics, just that there might be in the future in computational geometry.

I propose to make it part of the convex hull algorithms library : https://doc.cgal.org/latest/Manual/packages.html#PartConvexHullAlgorithms

[sumeetshirgure]

Just following up on this request.

[mglisse]

I have implemented a header library that is robust and exact,

Note that those 2 words have a very specific meaning in computational geometry. Could you describe what specific steps you have taken to ensure said robustness and exactness?

[sumeetshirgure]

Hello! Thank you for your response. Following is the title and abstract of the paper I've written that is under review. If you like, I can email you a pre-print. I'm technically not allowed to post it on servers until it is published.

Title: Robust implementations of real time algorithms for maintaining the convex hull of a dynamic set in the plane

Abs: "This paper documents the implementation details and the interface of a C++ software package that allows for maintaining the convex hull of a dynamic set of points in the 2D plane. By maintaining the convex hull we mean the following things (a) point insertion and point deletion requests are handled by updating the data structures in memory, and (b) said structures allow for efficiently querying standard questions like determining whether another point lies inside the resulting convex polygon, finding tangents from an external point, and finding the farthest points along a given direction. By real time we mean that the individual requests are handled quickly and the time complexity analysis is not amortized over multiple queries. The presented software package is robust and exact, in the sense that if geometric errors arise because of floating point imprecision, they will not be due to code written within our scope. In particular if all numerals are exact to arbitrary precision, the code provided will always find the exact convex hull of a given set of points, and answer queries exactly to given precision. This feature is possible due to the use of C++ template meta programming."

I myself don't need to take steps to ensure arbitrary precision, the users of the convex hull library (currently named dpch) can instantiate an object by passing a data type provided by high-precision libraries like GMP.

E.g they could do #include <gmp.h> ... dpch::DynamicHull<mpz_t> dynamic_hull; I just use dpch::DynamicHull<int> for a proof of concept.

Edit: There are also little things, like not using division, but rather multiplying the common denominator : https://github.com/sumeetshirgure/DynamicPlanarHull/blob/65545b0d5c1e8c5ef229b5864afb7c5e09f4f7c9/include/dpch/dynamic/MergeableLowerHull.hh#L51

Using a single comparison operator so the Field argument doesn't have to provide a lot of operator overloads https://github.com/sumeetshirgure/DynamicPlanarHull/blob/65545b0d5c1e8c5ef229b5864afb7c5e09f4f7c9/include/dpch/dynamic/MergeableLowerHull.hh#L73

[sumeetshirgure]

On second thought, I've made the paper public. You can find it in the following link : https://sumeetshirgure.github.io/assets/pdfs/papers/dpch.pdf

[afabri]

Are you familair with CGAL from a user perspective? Did you look at the CGAL 2D convex hull package. Instead to parameterize the algorithm with a number type, we parameterize it with a traits class that provides things like a number type, a point type, and an orientation predicate for this point type. You would have to adapt your contribution to this design. In fact in one of the tutorials we explain this for CGAL::convex_hull_2().

[afabri]

So you will see that we offer a solution that is almost as fast as the computation with floating point numbers, but as correct as if we used Gmpq all the time. As you do not fiddle around with magic epsilons to make it robust, I would expect that it is straightforward to make your code work with the CGAL::Exact_precdicates_inexact_constructions_kernel. And then we could compare it with the 2D triangulation. What do you think?

[afabri]

@sumeetshirgure any thoughts on what I proposed last week?

[sumeetshirgure]

@afabri Thanks for your response, and I'm sorry mine is late. Actually I'm not too familiar with CGAL's user interface. But I think I understand what you mean. I'll have to adapt the code so that it takes a traits class and use CGALs exact predicates tags. But I'm afraid I won't have the time to go ahead with it this fall. Perhaps this could be something of a GSoC project? I was also contacted by another student interested in this and they seem to have some good ideas about implementing potentially faster binary search trees. As it stands there are still a few corners that need to be polished in my current implementation. I'd be more than happy to assist them or anyone else who participates in GSoC.