Convex Hull gives wrong output for 3D points.

[sudo-panda]

The Graham Andrew strategy has been implemented for 2D cartesian geometry but it doesn't assert if the supplied geometry is 2D and gives wrong output when supplied with 3D geometry.

[vissarion]

Thanks for noticing. Could you please add a minimal example to reproduce this behaviour.

[sudo-panda]

@vissarion , yeah sure. The below example uses a 3D multipoint as an input and gives out a 3D multipoint as an output. The input provided is that contains the corners of a cube and the centroid of it.

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>

BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)

int main()
{
  typedef boost::tuple<double, double, double> point;
  typedef boost::geometry::model::multi_point<point> multi_pt;

  multi_pt input;
  boost::geometry::read_wkt("multipoint((0 0 0), (1 1 1), (1 1 0), (1 0 1), (0 1 1), (0 0 1), (0 1 0), (1 0 0), (0.5 0.5 0.5))", input);

  multi_pt hull;
  boost::geometry::convex_hull(input, hull);

  using boost::geometry::wkt;
  std::cout
    << "input: " << wkt(input) << std::endl
    << "hull: " << wkt(hull) << std::endl
    ;

  return 0;
}

The output that we get is:

input: MULTIPOINT((0 0 0),(1 1 1),(1 1 0),(1 0 1),(0 1 1),(0 0 1),(0 1 0),(1 0 0),(0.5 0.5 0.5))
hull: MULTIPOINT((0 0 0),(0 1 1),(1 1 1),(1 0 1),(0 0 0))

While the hull should contain all the points except (0.5 0.5 0.5).

Also in my opinion if the supplied output geometry is multipoint we should not append the start point at the end as it is self implied. it should be added only when a polygon of ring type is provided. Although I am unfamiliar with the design rationale that was there when this was implemented.

Since Graham Andrew Strategy cannot be extended to 3D space I would like to implement Chan's Algorithm for cartesian geometry. I am applying for the 2nd Project in GSoC and I think it will be a good base for the project and can be extended to cover non-cartesian systems. What is your opinion on this?

[vissarion]

It probably discards the 3rd coordinate and computes the convex hull of the projection in the first two. However, the user should be notified for this behaviour. This notification should be the same for all algorithms that does not handle correctly the 3d geometries.

Regarding, 3D convex hull algorithms. You should do some research on algorithms and implementations if you want to add it to your application or implement it at some point. As far as I know currently one of the best choices (performance-wise) is qhull (http://www.qhull.org/) which implements the quickhull algorithm (https://en.wikipedia.org/wiki/Quickhull).

[sudo-panda]

I think we should give a compile time warning stating that Supplied argument(s) is/are 3D but will be treated as 2D. We can generalize the template stating supplied type isn't supported and will revert to a lower type. Once we agree on what is best I will start working on adding the functionality.

As for the 3D convex hull algorithms, after thinking it over I think it better to add Quickhull ( O(n log n), worst case O(n²)) as 3D implementations of it exist widely while implementations of Chan's Algorithm ( O(n log h) ) in 3D are almost non existent. If you give the go ahead I would implement a Quickhull strategy for 2D, 3D and, if I can, 4D convex hulls too.

[Siddharth-coder13]

Hey, @vissarion I want to work on this issue and implement the Quickhill algorithm for 3D points and also work on other algorithms in general that do not handle 3D geometries correctly.

[vissarion]

Hi @Siddharth-coder13, sure you can create an PR on 3D convex hull algorithm and discuss the details there.

[barendgehrels]

Hi @Siddharth-coder13 , thanks for your intention!

There are many other algorithms not handling 3d (at all, in general in our library). It will be a huge effort. The best is to start with relatively simple ones, and convex hull would, indeed, probably be not the most complex one (though I would start with volume probably).

However, the best first point to start with, is defining a geometry (model, and concept) of a polyhedral surface. Because it's not there yet and you will need it as a result of the convex hull in 3D.

A second point to start with (apart from Volume or ConvexHull) could be WKT, a.o. because we always use them in unit tests.

So this would be POLYHEDRALSURFACE
https://en.wikipedia.org/wiki/Well-known_text_representation_of_geometry

[vissarion]

Indeed, as @barendgehrels note the output of 3D convex hull cannot be just an ordered list (opposed to 2D) so you need a new geometry. For volume things could be a bit simpler since the input could be a 3d pointset and the output a numeric value.

[Siddharth-coder13]

It seems that I have to implement volume by scratch. So, I will make a separate header file in the algorithms directory and implement its functions, Is it fine?

[barendgehrels]

It seems that I have to implement volume by scratch. So, I will make a separate header file in the algorithms directory and implement its functions, Is it fine?

Sure, that sounds right!

[vissarion]

Indeed, as @barendgehrels note the output of 3D convex hull cannot be just an ordered list (opposed to 2D) so you need a new geometry. So an alternative starting point could be volume of an input 3d pointset which outputs a numeric value. But I agree that the best start is to define the polyhedral surface.

[Siddharth-coder13]

@vissarion will you please explain about defining polyhedral surfaces, I'm not getting any clue on how to start?

[vissarion]

You can start by reading the OGC standard, and see how this is done in postGIS.

…

On Thu, Dec 24, 2020, 12:45 Siddharth Kumar ***@***.***> wrote: @vissarion <https://github.com/vissarion> will you please explain about defining polyhedral surfaces, I'm not getting any clue on how to start? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#683 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA35UTQZFZYCL67TOML3GNLSWMLTXANCNFSM4LIG2YDA> .