Geometry Boost List: Re: [geometry] within(Poly, Poly) and error in touches()

Subject: Re: [geometry] within(Poly, Poly) and error in touches()
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-24 08:20:31

Adam Wulkiewicz wrote:
> Hi,
>
> I'm playing with the implementation of missing boolean operations. 
> Currently I'm implementing within(Poly, Poly). I figured out that I'll 
> check if there is some point of the first polygon within the second 
> one using detail::within::point_in_polygon and then check if the first 
> polygon's exterior ring doesn't overlap the second polygon rings. I 
> can't use detail::disjoint::disjoint_linear because this will return 
> false for polygons which boundries overlap. And within() should return 
> true also for those cases. I thought I'll use 
> boost::geometry::get_turns, the same like it's used in the 
> implementation of the touches() algorithm. Basically I need to detect 
> if the boundries crosses or just touches itself. Is it possible to use 
> get_turns this way?
>
> Another thing, for Polygons I set the default strategy to winding<> 
> which works for Points, which I then pass to 
> detail::within::point_in_polygon. Is this valid?
>
> And diving into the touches() implementation I discovered that there 
> is a bug, or am I missing something? E.g. 2 bottom tests fails.
>
> template <typename Geometry>
> Geometry from_wkt(std::string const& wkt)
> {
>     Geometry res;
>     boost::geometry::read_wkt(wkt, res);
>     return res;
> }
>
> typedef bgm::point<float, 2, bg::cs::cartesian> Pt;
> typedef bgm::polygon<Pt, false, false> P;
>
> BOOST_CHECK(!bg::touches(from_wkt<P>("POLYGON((1 1, 5 1, 5 5, 1 5))"), 
> from_wkt<P>("POLYGON((0 0, 9 0, 9 9, 0 9),(5 5,8 5,8 8,5 8))"))); // OK
> BOOST_CHECK(bg::touches(from_wkt<P>("POLYGON((0 0, 1 0, 1 1, 0 1))"), 
> from_wkt<P>("POLYGON((1 1, 9 1, 9 9, 1 9),(5 5,8 5,8 8,5 8))"))); // FAIL
> BOOST_CHECK(bg::touches(from_wkt<P>("POLYGON((0 0, 1 0, 1 5, 0 5))"), 
> from_wkt<P>("POLYGON((1 1, 9 1, 9 9, 1 9),(5 5,8 5,8 8,5 8))"))); // FAIL
>
> In detail::touches::has_only_turns()
> the condition it->has(detail::overlay::operation_intersection)
> is true for all cases so the function returns false.
>
> Is it a bug or am I missing something? If it is a bug I may try to fix 
> it, after I figure out how get_turns() works.

For CW rings and polygons it works, e.g. those tests are passed:

typedef bgm::ring<Pt, true, false> RCW;
typedef bgm::polygon<Pt, true, false> PCW;

BOOST_CHECK(!bg::touches(from_wkt<PCW>("POLYGON((1 1, 1 5, 5 5, 5 1))"), 
from_wkt<PCW>("POLYGON((0 0, 0 9, 9 9, 9 0),(5 5,5 8,8 8,8 5))")));
BOOST_CHECK(bg::touches(from_wkt<PCW>("POLYGON((0 0, 0 1, 1 1, 1 0))"), 
from_wkt<PCW>("POLYGON((1 1, 1 9, 9 9, 9 1),(5 5,5 8,8 8,8 5))")));
BOOST_CHECK(bg::touches(from_wkt<PCW>("POLYGON((0 0, 0 5, 1 5, 1 0))"), 
from_wkt<PCW>("POLYGON((1 1, 1 9, 9 9, 9 1),(5 5,5 8,8 8,8 5))")));
BOOST_CHECK(bg::touches(from_wkt<RCW>("POLYGON((0 0, 0 5, 1 5, 1 0))"), 
from_wkt<RCW>("POLYGON((1 1, 1 9, 9 9, 9 1))")));
BOOST_CHECK(bg::touches(from_wkt<RCW>("POLYGON((0 0, 0 1, 1 1, 1 0))"), 
from_wkt<RCW>("POLYGON((1 1, 1 9, 9 9, 9 1))")));

And after passing values based on the point_order of Geometries as 
Reversed1 and Reversed2 parameters of boost::geometry::get_turns<> the 
touches() for CCW polygons works as well. Something like in the attached 
patch.
Do you think this solution is valid?

Regards,
Adam