Re: [boost] GGL issues - Access Violation

Subject: Re: [boost] GGL issues - Access Violation
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2009-11-17 17:20:30

Hi,

I'm trying to run a test that will take the boolean difference of two 
polygons, but haven't been able to find an explicit difference function. 
So I've tried instead to get the difference by taking:
A & !B (the intersection of A and the negation of B, where negation is 
done by reversing the winding.) Anyway, when I tried this I got a crash 
when the winding was reversed on B. I've attached a text with the test.

Regards,

Brandon


//
//! Copyright © 2008-2009
//! Brandon Kohn
//
//  Distributed under the Boost Software License, Version 1.0. (See
//  accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//
#ifndef GENERATIVE_GEOMETRY_GGL_REVIEW_TESTBOOLEANS_HPP
#define GENERATIVE_GEOMETRY_GGL_REVIEW_TESTBOOLEANS_HPP
#pragma once

#include <boost/test/unit_test.hpp>
#include <boost/test/floating_point_comparison.hpp>

//////////////////////////////////////////////////////////////////////////
#include <sstream>
#include <fstream>

#include <ggl/util/write_dsv.hpp>

#include <ggl/extensions/gis/io/wkt/read_wkt.hpp>
#include <ggl/extensions/gis/io/wkt/write_wkt.hpp>

#include <ggl/geometries/point_xy.hpp>
#include <ggl/geometries/box.hpp>
#include <ggl/geometries/linear_ring.hpp>
#include <ggl/geometries/polygon.hpp>
#include <ggl/geometries/geometries.hpp>

#include <ggl/algorithms/correct.hpp>
#include <ggl/algorithms/intersection.hpp>
#include <ggl/algorithms/area.hpp>
#include <ggl/algorithms/length.hpp>
#include <ggl/algorithms/num_points.hpp>
#include <ggl/algorithms/simplify.hpp>

#include <ggl/strategies/strategies.hpp>

#define TEST_WITH_SVG 1
#if(TEST_WITH_SVG)
    #include "svg_mapper.hpp" //might need to change this back to your <testutil...path>
#endif

namespace 
{
    template <typename OutputType, typename G1, typename G2>
    void test_intersection( int caseid, 
                            G1 const& g1, 
                            G2 const& g2,
                            int expected_count = 0,
                            int expected_point_count = 0,
                            double expected_length_or_area = 0 )
    {
        static const bool is_line = ggl::geometry_id<OutputType>::type::value == 2;

        std::vector<OutputType> clip;
        ggl::intersection_inserter<OutputType>(g1, g2, std::back_inserter(clip));

        double length_or_area = 0;
        int n = 0;
        for (typename std::vector<OutputType>::const_iterator it = clip.begin();
            it != clip.end(); ++it)
        {
            // instead of specialization we check it run-time here
            length_or_area += is_line
                ? ggl::length(*it)
                : ggl::area(*it);

            // Simplify to get a correct point-count without duplicate points
            // (note that overlay might be adapted to avoid duplicates)
            OutputType simplified;
            ggl::simplify(*it, simplified, 0.0001);
            n += ggl::num_points(simplified);

            //std::cout << std::endl << "case " << caseid << " ";
            //std::cout << ggl::dsv(*it) << std::endl;
        }

        BOOST_CHECK_EQUAL(clip.size(), expected_count);
        BOOST_CHECK_EQUAL(n, expected_point_count);
        BOOST_CHECK_CLOSE(length_or_area, expected_length_or_area, 0.001);

#if defined(TEST_WITH_SVG)
        {
            std::ostringstream filename;
            filename << "intersection" << caseid << ".svg";

            std::ofstream svg(filename.str().c_str());

            svg_mapper<typename ggl::point_type<G2>::type> mapper(svg, 500, 500);
            mapper.add(g1);
            mapper.add(g2);

            mapper.map(g1, is_line
                ? "opacity:0.6;stroke:rgb(0,0,255);stroke-width:5"
                : "opacity:0.6;fill:rgb(0,0,255);stroke:rgb(0,0,0);stroke-width:1");
            mapper.map(g2, "opacity:0.6;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");

            for (typename std::vector<OutputType>::const_iterator it = clip.begin();
                it != clip.end(); ++it)
            {
                mapper.map(*it, "opacity:0.6;fill:none;stroke:rgb(255,0,0);stroke-width:5");
            }
        }
#endif
    }

    template <typename OutputType, typename G1, typename G2>
    void test_one( int caseid, 
                   std::string const& wkt1, 
                   std::string const& wkt2,
                   int expected_count = 0, 
                   int expected_point_count = 0,
                   double expected_length_or_area = 0 )
    {
        G1 g1;
        ggl::read_wkt(wkt1, g1);

        G2 g2;
        ggl::read_wkt(wkt2, g2);

        test_intersection<OutputType>(caseid, g1, g2,
            expected_count, expected_point_count,
            expected_length_or_area);
    }

}

template <typename Point>
void test_ops()
{
    typedef ggl::linestring< Point > linestring;
    typedef ggl::polygon< Point> polygon;
    typedef ggl::box< Point > box;

    std::string p5 = "POLYGON((37.29449462890625 1.7902572154998779,37.000419616699219 1.664225697517395,37.140213012695313 1.3446992635726929,50.974888957147442 -30.277285722290763,57.297810222148939 -37.546793343968417,41.590042114257813 -7.2021245956420898,40.6978759765625 -5.4500408172607422,40.758884429931641 -5.418975830078125,42.577911376953125 -4.4901103973388672,42.577877044677734 -4.4900407791137695,42.699958801269531 -4.4278755187988281,46.523914387974358 -8.5152102535033496,47.585065917176543 -6.1314922196594779,45.389434814453125 -4.5143837928771973,46.296027072709599 -2.4984308554828116,37.43402099609375 1.470055103302002,37.29449462890625 1.7902572154998779))";
    
    //! p7 is p6 in reverse.
    std::string p6 = "POLYGON((42.399410247802734 1.4956772327423096,42.721500396728516 2.2342472076416016,42.721500396728516 3.6584999561309814,51.20102152843122 7.1738039562841562,51.370888500897557 7.4163459734570729,37.43402099609375 1.470055103302002,37.29449462890625 1.7902572154998779,37.000419616699219 1.664225697517395,37.140213012695313 1.3446992635726929,36.954700469970703 1.2597870826721191,26.472516656201325 -3.5380830513658776,27.069889344709196 -4.2926591211028242,30.501169204711914 -2.3718316555023193,32.708126068115234 -2.3611266613006592,32.708126068115234 -2.3611700534820557,32.708168029785156 -2.3611698150634766,32.718830108642578 -4.3281683921813965,29.135100397190627 -8.9262827849488211,29.619997024536133 -9.5368013381958008,30.339155197143555 -8.9838371276855469,30.670633316040039 -8.8180980682373047,30.896280288696289 -9.1206979751586914,30.207040612748258 -10.275926149505661,30.947774887084961 -11.208560943603516,31.669155120849609 -10.653837203979492,32.000633239746094 -10.488097190856934,32.226280212402344 -10.790698051452637,31.682494778186321 -12.133624901803865,32.274600982666016 -12.879127502441406,32.998821258544922 -12.323249816894531,33.339523315429688 -12.147735595703125,33.566280364990234 -12.450697898864746,33.164891643669634 -14.000060288415174,33.598796844482422 -14.546377182006836,34.328716278076172 -13.992490768432617,34.658355712890625 -13.81736946105957,34.886280059814453 -14.120697975158691,34.634240447128811 -15.85007183479255,34.931102752685547 -16.223842620849609,35.656356811523438 -15.66030216217041,35.963497161865234 -15.476018905639648,37.326129913330078 -17.190576553344727,38.823680877685547 -16.296066284179688,39.966808319091797 -17.625011444091797,40.800632476806641 -17.208097457885742,41.821544647216797 -19.211688995361328,41.988733475572282 -19.945838749437218,57.524304765518266 -37.807195733984784,41.590042114257813 -7.2021245956420898,40.6978759765625 -5.4500408172607422,40.758884429931641 -5.418975830078125,42.577911376953125 -4.4901103973388672,42.577877044677734 -4.4900407791137695,42.699958801269531 -4.4278755187988281,46.559533858616469 -8.435196445683264,47.604561877161387 -6.087697464505224,45.389434814453125 -4.5143837928771973,46.695858001708984 -1.6093428134918213,47.263670054709685 -1.784876824891044,47.830955505371094 -0.69758313894271851,48.43512638981781 -0.81299959072453376,49.071769542946825 0.61489892713413252,43.764598846435547 0.93951499462127686,43.644271850585938 0.96149998903274536,42.399410247802734 1.4956772327423096))";
    std::string p7 = "POLYGON((43.644271850585938 0.96149998903274536,43.764598846435547 0.93951499462127686,49.071769542946825 0.61489892713413252,48.43512638981781 -0.81299959072453376,47.830955505371094 -0.69758313894271851,47.263670054709685 -1.784876824891044,46.695858001708984 -1.6093428134918213,45.389434814453125 -4.5143837928771973,47.604561877161387 -6.087697464505224,46.559533858616469 -8.435196445683264,42.699958801269531 -4.4278755187988281,42.577877044677734 -4.4900407791137695,42.577911376953125 -4.4901103973388672,40.758884429931641 -5.418975830078125,40.6978759765625 -5.4500408172607422,41.590042114257813 -7.2021245956420898,57.524304765518266 -37.807195733984784,41.988733475572282 -19.945838749437218,41.821544647216797 -19.211688995361328,40.800632476806641 -17.208097457885742,39.966808319091797 -17.625011444091797,38.823680877685547 -16.296066284179688,37.326129913330078 -17.190576553344727,35.963497161865234 -15.476018905639648,35.656356811523438 -15.66030216217041,34.931102752685547 -16.223842620849609,34.634240447128811 -15.85007183479255,34.886280059814453 -14.120697975158691,34.658355712890625 -13.81736946105957,34.328716278076172 -13.992490768432617,33.598796844482422 -14.546377182006836,33.164891643669634 -14.000060288415174,33.566280364990234 -12.450697898864746,33.339523315429688 -12.147735595703125,32.998821258544922 -12.323249816894531,32.274600982666016 -12.879127502441406,31.682494778186321 -12.133624901803865,32.226280212402344 -10.790698051452637,32.000633239746094 -10.488097190856934,31.669155120849609 -10.653837203979492,30.947774887084961 -11.208560943603516,30.207040612748258 -10.275926149505661,30.896280288696289 -9.1206979751586914,30.670633316040039 -8.8180980682373047,30.339155197143555 -8.9838371276855469,29.619997024536133 -9.5368013381958008,29.135100397190627 -8.9262827849488211,32.718830108642578 -4.3281683921813965,32.708168029785156 -2.3611698150634766,32.708126068115234 -2.3611700534820557,32.708126068115234 -2.3611266613006592,30.501169204711914 -2.3718316555023193,27.069889344709196 -4.2926591211028242,26.472516656201325 -3.5380830513658776,36.954700469970703 1.2597870826721191,37.140213012695313 1.3446992635726929,37.000419616699219 1.664225697517395,37.29449462890625 1.7902572154998779,37.43402099609375 1.470055103302002,51.370888500897557 7.4163459734570729,51.20102152843122 7.1738039562841562,42.721500396728516 3.6584999561309814,42.721500396728516 2.2342472076416016,42.399410247802734 1.4956772327423096,43.644271850585938 0.96149998903274536))";

    test_one<polygon, polygon, polygon>(2, p5, p7, 0, 0, 0);
}

BOOST_AUTO_TEST_CASE( TestBooleanOperations )
{
    test_ops< ggl::point_xy<double> >();
}

#endif