CGAL users discussion list

[Efi Fogel <>]

When I run the program as is (using inexact construction, I get a core dump, which is most probably caused by the inexact constructions.

When I run the program with an exact construction kernel, I get the correct result.

You can simply:

void dumpPoly(CGALPolygon& poly) { std::cout << poly << std::endl; }

When using Exact_predicates_exact_constructions_kernel

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Mon, Sep 12, 2016 at 10:48 PM, Christopher Mitchell <> wrote:

Sebastien: Thanks for the advice. Unfortunately, for speed purposes I'd prefer to stick with inexact constructions. This polygon pair doesn't seem like it's really approaching the limits of numeric precision in terms of the huge overlap area.

Efi: Ask and you shall receive. This code is a little unwieldy for a minimum working example (102 lines), but I figure its longevity will be better here than in a Pastebin. To my great frustration, I tried removing points, and the problem remained, but when I tried subtracting 100.0 from every X coordinate, it indicated that the polygons intersected. Working with doubles, the intersection definitely shouldn't be hitting odd precision problems with coordinates that are only on the order of 10^2 units. This seems like it could possibly be a bug?

Thanks,

Christopher

// -----snip-----

#include <stdio.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Boolean_set_operations_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel CGAL_Kernel;
typedef CGAL_Kernel::Point_2 CGALPoint;
typedef CGAL::Polygon_2<CGAL_Kernel> CGALPolygon;

double pts_p1[][2] = {
        {138.434248, 54.124268},
        {156.251888, 53.447439},
        {159.268861, 55.635141},
        {168.750594, 82.497614},
        {165.721545, 83.640381},
        {159.550635, 86.191099},
        {149.385779, 90.040283},
        {130.971384, 97.216211},
        {119.770956, 101.497880},
        {112.218620, 104.432790},
        {109.481271, 93.899521},
        {108.693051, 87.351571},
        {108.600034, 80.589390},
        {109.019489, 73.333375},
        {109.398422, 60.659113},
        {109.614696, 54.943998},
        {128.132617, 54.352682}
};

double pts_p2[][2] = {
        {139.434399, 57.599339},
        {155.707971, 56.738629},
        {156.812714, 57.672514},
        {165.721545, 83.640381},
        {159.550635, 86.191099},
        {149.385779, 90.040283},
        {130.971384, 97.216211},
        {119.770956, 101.49788},
        {112.218620, 104.43279},
        {109.481271, 93.899521},
        {108.693051, 87.351571},
        {108.600034, 80.589390},
        {109.019489, 73.333375},
        {109.398422, 60.659113},
        {110.103104, 59.601234},
        {127.188178, 57.950231},
        {126.599293, 61.485162},
        {124.600343, 71.709878},
        {139.439351, 66.181265},
        {139.584575, 60.776208}
};

int nodes2Polygon(const double pts[][2], const size_t size, CGALPolygon& poly) {
        printf("Generating %zu-point poly\n", size);
        // Copy points into polygon. Omit the last point if it's a copy of the first point.
        for (size_t i = 0; i < size; i++) {
                if (i == 0 || i != (size - 1) || (pts[i][0] != pts[0][0] || pts[i][1] != pts[0][1])) {
                        CGALPoint point(pts[i][0], pts[i][1]);
                        // Make sure the point is not identical to the previous point in the poly.
                        if (!poly.size() || point != *std::prev(poly.vertices_end())) {
                                poly.push_back(point);
                        }
                }
        }

        if (!poly.is_simple()) {
                return -1;
        }

        // Correct orientation to make it an outline, not a hole
        if (poly.orientation() == CGAL::CLOCKWISE) {
                poly.reverse_orientation();
        }

        return 0;
}

void dumpPoly(CGALPolygon& poly) {
        for(auto it = poly.vertices_begin(); it != poly.vertices_end(); it++) {
                printf("%f %f\n", it->x(), it->y());
        }
        printf("\n");
}

int main(int argc, char* argv[]) {
        CGALPolygon p1;
        CGALPolygon p2;

        nodes2Polygon(pts_p1, sizeof(pts_p1) / sizeof(double) / 2, p1);
        dumpPoly(p1);

        nodes2Polygon(pts_p2, sizeof(pts_p2) / sizeof(double) / 2, p2);
        dumpPoly(p2);

        if (CGAL::do_intersect(p1, p2)) {
                printf("Polygons intersect\n");
        } else {
                printf("Polygons do not intersect\n");
        }

        if (CGAL::do_intersect(p2, p1)) {
                printf("Polygons intersect\n");
        } else {
                printf("Polygons do not intersect\n");
        }
        return 0;
}

On Mon, Sep 12, 2016 at 6:08 AM, Sebastien Loriot (GeometryFactory) <> wrote:

The kernel used does not have exact constructions.
Try again with CGAL::Exact_predicates_exact_constructions_kernel

Sebastien.

On 09/12/2016 12:00 PM, Efi Fogel wrote:

It would easier if you just send the code and the input polygon.
This way we can quickly try to reproduce the problem.

    ____  _        ____             _
   /_____/_) o    /__________  __  //
  (____ (   (    (    (_/ (_/-(-'_(/
                          _/



On Mon, Sep 12, 2016 at 1:03 AM, Christopher Mitchell <
<mailto:>> wrote:

    Thanks for the quick response. The code is sufficiently trivial (ie,
    a single if (CGAL::do_intersect(poly1, poly2)) { ... }) that I'm not
    sure it would help. I'm using a simple loop to convert a set of
    non-CGAL points into a Polygon_2, making sure to not duplicate the
    starting point, as you can see from the image attached to the first
    post. My polygons are CGAL::Polygon_2<CGAL_Kernel>, where
    CGAL_Kernel is CGAL::Exact_predicates_inexact_constructions_kernel.
    I hope this helps. Thanks!

    On Sat, Sep 10, 2016 at 6:25 PM, Efi Fogel <
    <mailto:>> wrote:

        What number type are you using?  Better yet, could you share the
        code?


        On Sep 10, 2016 18:31, "Christopher Mitchell" <
        <mailto:>> wrote:

            I'm attempting to determine if two Polygon_2s overlap in
            anyway, ie, share any portion of their interiors, including
            one being entirely contained by the other. In most cases
            this works, but for a few polygon pairs, do_intersect()
            returns false unexpectedly. I make sure (1) all polygons are
            simple (2) all polygons are not oriented CGAL::CLOCKWISE (I
            call .reverse_orientation() on the polys if they are
            CGAL::CLOCKWISE), and (3) that the starting vertex is not
            duplicated. I have attached an example of a polygon pair for
            which do_intersect() returns false. Thanks in advance for
            any insight; I'd be happy to provide additional information
            as necessary.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss