
Geometry : 
Subject: Re: [geometry] within(Poly, Poly) and error in touches()
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20130924 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
Geometry list run by mateusz at loskot.net