Subject: Re: [geometry] within(Poly, Poly)
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-09-24 08:44:50
On 24-9-2013 1:22, Adam Wulkiewicz wrote:
> 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?
Yes. One detail, in case you are not aware of this: within should return
false even if the whole polygon is more or less inside, touching only
the border from the inside. So there should be no intersections at all.
So yes, the plan is good, I would use get_turns, returning immediately
as soon as one turn is detected (exactly as done in disjoint.,
disjoint_linear - so also specify not skipping any turn). If there is
any turn it is not within. If there are no turns at all, you only need
to check if the complete polygon is within the other, using
point_on_border. This will work for both polygon/multi_polygon and also
So it will closely similar to disjoint and probably you can share code
> 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 skip the rest to answer your follow up ;-)
Geometry list run by mateusz at loskot.net