Basic polygon join non-functional for specific polygons

notgapriel commented 2 months ago

Issue Details

I have found that the CGAL::join mostly works but for very few specific cases that I have isolated, it does not. These do not appear to have any obvious edge-case logic in them, they are basic octagons that should be able to compute a union but do not. This is using the inexact kernel.

The example given has two octagons that overlap each other. This is shown below.

Image of the two polygons in Desmos:

The resultant polygon should have 15 vertices but has 0. A reading of the docs would suggest this behaviour is unintended. Will also note that when calling CGAL::join many other times in one of my geometric projects prior to calling it for these two octagons, I did manage to get a 15-sided Polygon_with_holes_2 generating but it is impossible to generate a minimum example for this as I have not found what triggers it to output something and what triggers it to output nothing. The 15-sided shape it did output had all of the right points but they were incorrectly ordered so as to make a degenerate, self-intersecting polygon.

Image of the 15-sided degenerate output in Desmos:

The cause for this issue is possibly related to the strange logic for handling both aggregating and non-aggregating inputs to the CGAL::join function that was pointed out in #6840.

Source Code

#include <iterator>

#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>

using Kernel             = CGAL::Epick;
using Point              = CGAL::Point_2<Kernel>;
using Polygon            = CGAL::Polygon_2<Kernel>;
using Polygon_with_holes = CGAL::Polygon_with_holes_2<Kernel>;

static const Point pgn1_points[] = {
  { -3, 0 }, { 560, 1466 }, { 769, 1466 }, { 1369, 0 }, { 1148, 0 }, { 977, 444 }, { 364, 444 }, { 203, 0 },
};

static const Point pgn2_points[] = {
  { 481, 1601 }, { 534.5, 1727 }, { 661, 1780 }, { 788, 1726.5 }, { 841, 1597 }, { 788, 1467 }, { 662, 1414 }, { 534, 1467.5 },
};

int main(const int argc, const char *const *const argv) {
  const Polygon pgn1(std::cbegin(pgn1_points), std::cend(pgn1_points));
  const Polygon pgn2(std::cbegin(pgn2_points), std::cend(pgn2_points));

  // both shapes oriented CLOCKWISE
  std::cerr << "Input polygon #1, orientation: " << CGAL::orientation_2(pgn1.begin(), pgn1.end()) << ", " << pgn1.size() << " point(s):" << std::endl;
  for (const Point& point : pgn1) {
    std::cerr << "(" << point.x() << "," << point.y() << ")" << std::endl;
  }
  std::cerr << "Input polygon #2, orientation: " << CGAL::orientation_2(pgn2.begin(), pgn2.end()) << ", " << pgn1.size() << " point(s):" << std::endl;
  for (const Point& point : pgn2) {
    std::cerr << "(" << point.x() << "," << point.y() << ")" << std::endl;
  }

  Polygon_with_holes pgn_out;

  // docs state that the return of this function should indicate whether the two polygons overlap
  const bool polygons_do_overlap = CGAL::join(pgn1, pgn2, pgn_out);

  // the two input polygons overlap, good.
  assert(polygons_do_overlap);

  // the joined result has no holes, good
  assert(std::size(pgn_out.holes()) == 0);

  // !! should have fifteen points, has zero
  std::cerr << "Resultant polygon, " << pgn_out.outer_boundary().size() << " point(s): " << std::endl;
  for (const Point& point : pgn_out.outer_boundary()) {
    std::cerr << "(" << point.x() << "," << point.y() << ")" << std::endl;
  }

  return 0;
}

Output

Input polygon #1, orientation: -1, 8 point(s):
(-3,0)
(560,1466)
(769,1466)
(1369,0)
(1148,0)
(977,444)
(364,444)
(203,0)
Input polygon #2, orientation: -1, 8 point(s):
(481,1601)
(534.5,1727)
(661,1780)
(788,1726.5)
(841,1597)
(788,1467)
(662,1414)
(534,1467.5)
Resultant polygon, 0 point(s):

Environment

Operating system (Windows/Mac/Linux, 32/64 bits): Ubuntu 23.10 "Mantic", 64-bit
Compiler: GNU v13.2.0
Release or debug mode: Release
Specific flags used (if any):
CGAL version: libcgal-dev v5.6-1
Boost version: libboost-dev v1.74.0.3ubuntu7
Other libraries versions if used (Eigen, TBB, etc.):

lrineau commented 2 months ago

Efi (@efifogel), the bug report from @notgapriel is nicely done. Do you have a solution?

lrineau commented 2 months ago

Efi (@efifogel), the bug report from @notgapriel is nicely done. Do you have a solution?

I mean: is that fixed in more recent versions of the code? Maybe in a development branch?

efifogel commented 2 months ago

There is no bug. First, the input polygons are invalid, as they are clockwise oriented. Second, you should use Epeck (and not Epick). If you fix both problems the program works fine.

//) o /__ // (__ ( ( ( (/ (/-(-'(/ /

On Mon, 29 Apr 2024 at 17:37, Laurent Rineau @.***> wrote:

Efi @.*** https://github.com/efifogel), the bug report from @notgapriel https://github.com/notgapriel is nicely done. Do you have a solution?

I mean: is that fixed in more recent versions of the code? Maybe in a development branch?

— Reply to this email directly, view it on GitHub https://github.com/CGAL/cgal/issues/8172#issuecomment-2082921294, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABVBNOEAJOBDJOQ7QBRYK7LY7ZLKJAVCNFSM6AAAAABG4VFZFKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAOBSHEZDCMRZGQ . You are receiving this because you were mentioned.Message ID: @.***>

lrineau commented 2 months ago

Thanks Efi. I close the bug. @notgapriel I think you can continue and discuss in the closed bug if needed.

notgapriel commented 2 months ago

Sure, thank you very much, @efifogel and @lrineau. I missed the mention of "valid" polygons to the regularised 2D boolean-set operations as I only looked at the "Union Functions" documentation. I will leave that link versioned in case this is of any help to any future person in my position. Confusion may arise from the expectation that boolean operations on "inverse" polytopes (in this case, clockwise polygons) will work the same as in CGAL::Polygon_mesh_processing::corefine_and_compute_boolean_operations, where the operation is logically inverted on inverted input.

CGAL / cgal