Incorrect polygon area and problem with the boost::geometry::correct

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Incorrect polygon area and problem with the boost::geometry::correct

Vishnu
I have two problems with a slightly edited version of the example program 'c06_custom_polygon_example.cpp'. My revisions to the example are very minor, the substitution of a  boost_array for holes with an std::vector, and a call to 'correct' the polygon prior to calculating the area. The differences between the example and my edited file are shown following the problem description below.

1) The polygon area is correct when I use boost-geometry 0.6 along with boost_1_43. The polygon area is wrong when I use boost-geometry 0.8 along with boost_1_46_1. The correct area of the polygon is 0.92. However, with boost geometry 0.8, I get an area of 1.08, so it appears that the areas of the holes are added instead of being subtracted.

2) My edited version of the program compiles and builds with MS Visual Studio 2008 with both versions of boost-geometry. However, on RHEL4 with g++ 4.2.4, I can build it only with boost-geometry 0.6. The compilation error with g++ when I use boost-geometry 0.8 is shown below (the boost geometry files were put inside the boost_1_46_1  hierarchy). The program compiles if I do not call 'correct'.

g++ -I/usr/raidhome/vishnu/boost_1_46_1 -o c06_custom_polygon_example.2.using.bg0.8 c06_custom_polygon_example.2.cpp
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp: In static member function ‘static void boost::geometry::detail::correct::correct_polygon<Polygon>::apply(Polygon&) [with Polygon = my_polygon]’:
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:238:   instantiated from ‘void boost::geometry::correct(Geometry&) [with Geometry = my_polygon]’
c06_custom_polygon_example.2.cpp:134:   instantiated from here
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:161: error: no matching function for call to ‘boost::geometry::detail::correct::correct_ring<my_ring, std::less<double> >::apply(my_ring)’
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:122: note: candidates are: static void boost::geometry::detail::correct::correct_ring<Ring, Predicate>::apply(Ring&) [with Ring = my_ring, Predicate = std::less<double>]


The diff output is shown below.

>diff D:\users\vishnu\boost-geometry-0.8.0\example\c06_custom_polygon_example.cpp   c06_custom_polygon_example.2.cpp
9a10
> #include <vector>
38c39
<     boost::array<my_ring, 2> holes;
---
>     std::vector<my_ring> holes;
64c65
<     typedef boost::array<my_ring, 2> type;
---
>     typedef std::vector<my_ring> type;
83c84
<     typedef boost::array<my_ring, 2> holes_type;
---
>     typedef std::vector<my_ring> holes_type;
101a103,104
>     using namespace boost::geometry;
>
104,121c107,134
<     // Fill it the my-way, triangle
<     p1.boundary.push_back(my_point(2, 0));
<     p1.boundary.push_back(my_point(1, 5));
<     p1.boundary.push_back(my_point(5, 5));
<     p1.boundary.push_back(my_point(2, 0));
<
<     // Triangle
<     p1.holes[0].push_back(my_point(2, 1));
<     p1.holes[0].push_back(my_point(1.9, 2));
<     p1.holes[0].push_back(my_point(2.4, 2));
<     p1.holes[0].push_back(my_point(2, 1));
<
<     // Box
<     p1.holes[1].push_back(my_point(3, 3));
<     p1.holes[1].push_back(my_point(3, 4));
<     p1.holes[1].push_back(my_point(4, 4));
<     p1.holes[1].push_back(my_point(4, 3));
<     p1.holes[1].push_back(my_point(3, 3));
---
>     // Fill it with a square
>     p1.boundary.push_back(my_point(0, 0));
>     p1.boundary.push_back(my_point(0, 1));
>     p1.boundary.push_back(my_point(1, 1));
>     p1.boundary.push_back(my_point(1, 0));
>     p1.boundary.push_back(my_point(0, 0));
>
>     // Hole 1
>     my_ring ring;
>     ring.push_back(my_point(0.2, 0.2));
>     ring.push_back(my_point(0.2, 0.4));
>     ring.push_back(my_point(0.4, 0.4));
>     ring.push_back(my_point(0.4, 0.2));
>     ring.push_back(my_point(0.2, 0.2));
>
>     p1.holes.push_back(ring);
>
>     ring.clear();
>
>     ring.push_back(my_point(0.6, 0.6));
>     ring.push_back(my_point(0.6, 0.8));
>     ring.push_back(my_point(0.8, 0.8));
>     ring.push_back(my_point(0.8, 0.6));
>     ring.push_back(my_point(0.6, 0.6));
>
>     p1.holes.push_back(ring);
>
>     correct(p1);
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
Hi Vishnu,


On 17-3-2011 16:57, Vishnu wrote:
> I have two problems with a slightly edited version of the example program
> 'c06_custom_polygon_example.cpp'. My revisions to the example are very
> minor, the substitution of a  boost_array for holes with an std::vector, and
> a call to 'correct' the polygon prior to calculating the area. The
> differences between the example and my edited file are shown following the
> problem description below.(...)

Thanks for your problem report, I'll have a look soon.

Regards, Barend

--
Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
In reply to this post by Vishnu
Hi Vishnu,



On 17-3-2011 16:57, Vishnu wrote:

> I have two problems with a slightly edited version of the example program
> 'c06_custom_polygon_example.cpp'. My revisions to the example are very
> minor, the substitution of a  boost_array for holes with an std::vector, and
> a call to 'correct' the polygon prior to calculating the area. The
> differences between the example and my edited file are shown following the
> problem description below.
>
> 1) The polygon area is correct when I use boost-geometry 0.6 along with
> boost_1_43. The polygon area is wrong when I use boost-geometry 0.8 along
> with boost_1_46_1. The correct area of the polygon is 0.92. However, with
> boost geometry 0.8, I get an area of 1.08, so it appears that the areas of
> the holes are added instead of being subtracted.
I cannot reproduce your steps. It is right that without calling correct,
the polygon area is incorrect: holes (in the sample accidentally turned
clockwise) are added. That was already in 0.6 and it is still the case
in 0.8, it is by design.

I retrieved 0.6.0 from the sandbox-tags and it was already the case.

I will update the example such that the holes are in correct
orientation, thanks for the report.

> 2) My edited version of the program compiles and builds with MS Visual
> Studio 2008 with both versions of boost-geometry. However, on RHEL4 with g++
> 4.2.4, I can build it only with boost-geometry 0.6. The compilation error
> with g++ when I use boost-geometry 0.8 is shown below (the boost geometry
> files were put inside the boost_1_46_1  hierarchy). The program compiles if
> I do not call 'correct'.
I do not have g++ 4.2.4. Using gcc 4.4 it runs fine. Are you sure you
have defined the correct ring-types traits? There were changes between
0.6.0 and trunk.

In the diff output you sent some < > tags are missing, probably by the
HTML-parsing, so I cannot see exactly what you're doing there.

Regards, Barend

--
Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Vishnu
In reply to this post by Vishnu
Hi Barend,

On Mar 18-3-2011 04:39am, Barend wrote:

>>I cannot reproduce your steps. It is right that without calling correct, the polygon area is incorrect: holes (in the sample accidentally turned clockwise) are added. That was already in 0.6 and it is still the case in 0.8, it is by design.


Let me clarify. With boost-geometry-0.8, I see no difference when I use 'correct'. Here are the results I get with MS Visual Studio 2008:

Area when using 'correct' with boost-geometry-0.6:           0.92
Area when *not* using 'correct' with boost-geometry-0.6:  1.08
Area when using 'correct' with boost-geometry-0.8:           1.08
Area when *not* using 'correct' with boost-geometry-0.8:  1.08


>>I do not have g++ 4.2.4. Using gcc 4.4 it runs fine.

I get the compiler error with g++ 4.4.3. Just to be sure, did you use boost_1_46_1 with boost-geometry-0.8? If not, what version of boost did you use?

bagend vishnu 230% g++ --version
g++ (GCC) 4.4.3
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

bagend vishnu 231% g++ -I/usr/raidhome/vishnu/boost_1_46_1 -o c06_custom_polygon_example.2.using.bg0.8 c06_custom_polygon_example.2.cpp
In file included from /usr/raidhome/vishnu/boost_1_46_1/boost/geometry/geometry.hpp:43,
                 from c06_custom_polygon_example.2.cpp:12:
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp: In static member function ‘static void boost::geometry::detail::correct::correct_polygon<Polygon>::apply(Polygon&) [with Polygon = my_polygon]’:
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:238:   instantiated from ‘void boost::geometry::correct(Geometry&) [with Geometry = my_polygon]’
c06_custom_polygon_example.2.cpp:134:   instantiated from here
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:161: error: no matching function for call to ‘boost::geometry::detail::correct::correct_ring<my_ring, std::less<double> >::apply(my_ring)’
/usr/raidhome/vishnu/boost_1_46_1/boost/geometry/algorithms/correct.hpp:122: note: candidates are: static void boost::geometry::detail::correct::correct_ring<Ring, Predicate>::apply(Ring&) [with Ring = my_ring, Predicate = std::less<double>]



>>Are you sure you have defined the correct ring-types traits? There were changes between 0.6.0 and trunk.


What do I need to do here? I haven't changed anything with respect to the ring traits in the example which is taken from the boost-geometry-0.8 distribution. I only use an std::vector instead of a boost::array for the holes and add a call to 'correct'.

>>In the diff output you sent some < > tags are missing, probably by the HTML-parsing, so I cannot see exactly what you're doing there.


I am attaching the whole program below.

Vishnu

// Boost.Geometry (aka GGL, Generic Geometry Library)
//
// Copyright Barend Gehrels 2007-2009, Geodan, Amsterdam, the Netherlands
// Use, modification and distribution is subject to 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)
//
// Custom Polygon Example
#include <iostream>
#include <vector>

#include <boost/geometry/geometry.hpp>

#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/ring.hpp>


struct my_point
{
    my_point(double an_x = 0, double an_y = 0)
        : x(an_x)
        , y(an_y)
    {}

    double x, y;
};

struct my_ring : std::deque<my_point>
{};

// Define a struct of a polygon, having always two holes
// (of course this can be implemented differently, usually
// with a vector or deque, but it is just an exampe)
struct my_polygon
{
    // required for a polygon: an outer ring...
    my_ring boundary;
    // ... and a Boost.Range compatible inner ring collection
    std::vector<my_ring> holes;

    // just for the sample
    std::string name;

    my_polygon(std::string const& n = "") : name(n) {}
};


// We can conveniently use macro's to register point and ring
BOOST_GEOMETRY_REGISTER_POINT_2D(my_point, double, cs::cartesian, x, y)
BOOST_GEOMETRY_REGISTER_RING(my_ring)



// There is currently no registration macro for polygons
// and besides that a boost::array<T,N> in a macro would
// be very specific, so we show it "by hand":
namespace boost { namespace geometry { namespace traits
{

template<> struct tag<my_polygon> { typedef polygon_tag type; };
template<> struct ring_type<my_polygon> { typedef my_ring type; };

template<> struct interior_type<my_polygon>
{
    typedef std::vector<my_ring> type;
};


template<> struct exterior_ring<my_polygon>
{
    static my_ring& get(my_polygon& p)
    {
        return p.boundary;
    }

    static my_ring const& get(my_polygon const& p)
    {
        return p.boundary;
    }
};

template<> struct interior_rings<my_polygon>
{
    typedef std::vector<my_ring> holes_type;

    static holes_type& get(my_polygon& p)
    {
        return p.holes;
    }

    static holes_type const& get(my_polygon const& p)
    {
        return p.holes;
    }
};

}}} // namespace boost::geometry::traits



int main()
{
                using namespace boost::geometry;
               
    my_polygon p1("my polygon");

    // Fill it with a square
    p1.boundary.push_back(my_point(0, 0));
    p1.boundary.push_back(my_point(0, 1));
    p1.boundary.push_back(my_point(1, 1));
    p1.boundary.push_back(my_point(1, 0));
    p1.boundary.push_back(my_point(0, 0));
   
    // Hole 1
    my_ring ring;
    ring.push_back(my_point(0.2, 0.2));
    ring.push_back(my_point(0.2, 0.4));
    ring.push_back(my_point(0.4, 0.4));
    ring.push_back(my_point(0.4, 0.2));
    ring.push_back(my_point(0.2, 0.2));
       
    p1.holes.push_back(ring);

                ring.clear();
                 
    ring.push_back(my_point(0.6, 0.6));
    ring.push_back(my_point(0.6, 0.8));
    ring.push_back(my_point(0.8, 0.8));
    ring.push_back(my_point(0.8, 0.6));
    ring.push_back(my_point(0.6, 0.6));

                p1.holes.push_back(ring);

    correct(p1);

    std::cout << "Representation of " << p1.name << ": "
        << boost::geometry::dsv(p1) << std::endl;
    std::cout << "Area of " << p1.name << ": "
        << boost::geometry::area(p1) << std::endl;
    std::cout << "Perimeter of " << p1.name << ": "
        << boost::geometry::perimeter(p1) << std::endl;
    std::cout << "Centroid of " << p1.name << ": "
        << boost::geometry::dsv(boost::geometry::make_centroid<my_point>(p1)) << std::endl;

    return 0;
}
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
Hi Vishnu,

Are you sure you have it defined like this:
template<> struct interior_rings
{
typedef std::vector holes_type;
(...)

Because that is wrong - I'm note sure why it compiles for you using
MSVC, but it really should have template parameters. But probably they
are there and eliminated by the HTML layout.

If they are not there, that is probably the reason for both errors - the
area and the not-compiling under RHEL. But this cannot be - it will not
compile like this using MSVC.

So I cannot test your program in this form...  Can you paste it into
codepad.org?

Regards, Barend



_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Vishnu
In reply to this post by Vishnu
The 2 lines below the comment "Custom Polygon Example" should #include the iostream and vector headers. It appears that the '<' and '>' cause them to be tossed out.

Vishnu
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Vishnu
In reply to this post by Barend
Here's a link to the program I pasted in codepad.org.

http://codepad.org/RuShA7hf

Vishnu
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
Hi Vishnu,

Thanks for the paste, I come back to it tomorrow.

Regards, Barend


On 18-3-2011 18:29, Vishnu wrote:

> Here's a link to the program I pasted in codepad.org.
>
> http://codepad.org/RuShA7hf
>
> Vishnu
>
> --
> View this message in context: http://boost-geometry.203548.n3.nabble.com/Incorrect-polygon-area-and-problem-with-the-boost-geometry-correct-tp2694059p2698836.html
> Sent from the Boost Geometry mailing list archive at Nabble.com.
> _______________________________________________
> ggl mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/ggl
>


--
Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
In reply to this post by Vishnu
Hi Vishnu,


On 18-3-2011 18:18, Vishnu wrote:
The 2 lines below the comment "Custom Polygon Example" should #include the
iostream and vector headers. It appears that the '<' and '>' cause them to
be tossed out.
It was not only that, the same thing was happening with all the std::vector< > definitions. But thanks for the codepad paste, it helped me with that.

Let me clarify. With boost-geometry-0.8, I see no difference when I use
'correct'. Here are the results I get with MS Visual Studio 2008:

Area when using 'correct' with boost-geometry-0.6:           0.92
Area when *not* using 'correct' with boost-geometry-0.6:  1.08
Area when using 'correct' with boost-geometry-0.8:           1.08
Area when *not* using 'correct' with boost-geometry-0.8:  1.08

I can now confirm this is indeed the case. My confusion was that I tested with Trunk, not with 0.8.

So version 0.8 appears to have an error indeed in the "correct" function. That error is solved shortly afterwards. I know what it is - rings were accidentally copied by value there for reversal, with the changes in interior-ring-types for better support for custom polygon types. I suspect that this same error also causes the compilation issue in 0.8

The best I can do is create a new tagged version (0.9). Is that OK for you?

Regards, Barend

-- 
Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Vishnu
>>So version 0.8 appears to have an error indeed in the "correct" function. That error is solved shortly afterwards. I know what it is - rings were accidentally copied by value there for reversal, with the changes in interior-ring-types for better support for custom polygon types. I suspect that this same error also causes the compilation issue in 0.8. The best I can do is create a new tagged version (0.9). Is that OK for you?

Hi Barend,

Thanks for confirming the problem. I checked out code from the trunk using this:

> svn co http://svn.boost.org/svn/boost/trunk/boost/geometry boost-geometry

This gives me only some of the files that appear in a tagged branch (e.g., 0.8). So I made a copy of my entire boost_1_46_1 hierarchy that included the boost-geometry folders from version 0.8 and replaced only the folder boost_1_46_1/boost/geometry with the boost/geometry files I got from the trunk.

Using this newer code from the trunk, even the unmodified example 'c06_custom_polygon_example.cpp' will not compile with g++ 4.5.1 (on ubuntu 10.10). Previously, it was only the modified example with the call to 'correct' that did not compile on linux. Maybe the libs/geometry folder that came with v0.8 is incompatible with the boost/geometry folder in the trunk?

If you are confirming that the code I pasted into codepad will work with a tagged version, having a tagged version would be very helpful. Of course, I assume that would include not only code from the boost/geometry folder but also stuff from libs/geometry (and whatever else is making it work for you but not for me).

>>Are you sure you have defined the correct ring-types traits? There were changes between 0.6.0 and trunk.

You didn't mention this in your most recent post. Do you think this is no longer an issue?


Vishnu
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
Hi Vishnu,

> Thanks for confirming the problem. I checked out code from the trunk using
> this:
>
>> svn co http://svn.boost.org/svn/boost/trunk/boost/geometry boost-geometry
> This gives me only some of the files that appear in a tagged branch (e.g.,
> 0.8). So I made a copy of my entire boost_1_46_1 hierarchy that included the
> boost-geometry folders from version 0.8 and replaced only the folder
> boost_1_46_1/boost/geometry with the boost/geometry files I got from the
> trunk.

This will not work indeed, the boost/geometry folder and libs/geometry
folder should always go together.


> If you are confirming that the code I pasted into codepad will work with a
> tagged version, having a tagged version would be very helpful. Of course, I
> assume that would include not only code from the boost/geometry folder but
> also stuff from libs/geometry (and whatever else is making it work for you
> but not for me).

I'll create one tonight.

> You didn't mention this in your most recent post. Do you think this is no
> longer an issue?

Yet, it is still relevant. Might be the problem indeed. So I create 0.9
tonight, that will probably help everything.

Regards, Barend

--
Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect polygon area and problem with the boost::geometry::correct

Barend
In reply to this post by Vishnu
Hi Vishnu,

> If you are confirming that the code I pasted into codepad will work with a
> tagged version, having a tagged version would be very helpful. Of course, I
> assume that would include not only code from the boost/geometry folder but
> also stuff from libs/geometry (and whatever else is making it work for you
> but not for me).

The code now works in tag 0.9.0
<http://svn.boost.org/svn/boost/sandbox-tags/geometry/boost-geometry-0.9.0/>

I tested your version (with std::vector and other points) and it works
for me, using MSVC, with and without correct (giving different results).
Because c06 example runs under Linux too, this sample will also do.

I pasted it here:

http://codepad.org/3bGrQAXQ

Regards, Barend

Barend Gehrels
http://about.me/barendgehrels

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl