Boost logo

Geometry :

Subject: [ggl] Point/Box in Box Test (Border Cases - 3D)
From: Barend Gehrels (barend)
Date: 2011-06-28 15:06:06

Hi Frank,

> does boost.geometry currently provide a way to do "geometry1 within
> geometry2" tests including border cases?

"within" should be (according to OGC) "completely within", so a point
lying on a border, or a box touching a border, should return false.

Internally, it is handled by a sort of "within code", returning 1 if
within, 0 if on border, -1 if outside. This is not (yet) accessable to
end users.

So your question is not completely clear to me, "tests including border
cases" means "tests returning true if on a border"?

> -------------------------------------------------------------------
> That's my basic question! If required - more details of what I want
> to do:
> 1) Test whether a point lies in a box including being on the border
> based on the boost::geometry::within function.
> Example: boost::geometry::within(Point3D(0, 0, 0),
> Box3D(Point3D(0, 0, 0), Point3D(1, 1, 1)) delivers false.

Yes, it should.

> The test succeeds for points that are within the box but not on the
> border.
> I am aware that boost::geometry::intersects works for point-in-box
> tests including border cases but has two drawbacks:
> i) It seems to be 30% slower for point-in-box tests.
> ii) I would like to use the same call to boost::geometry for
> box-in-box, point-in-box or even polygon in polygon tests
> (boost::within does allow this, although its return values
> aren't as desired).

intersects is a different function, returning true even if a box is
partly outside another box. Intersects point-box should return true if a
point lies on a box. So yes, indeed, you might use it.

> 2) Test whether a box lies within a box, including being on the border?
> Trivial example:
> const Box3D box(Point3D(0,0,0), Point3D(1, 1, 1));
> boost::geometry::within(box, box) delivers false.

Right, it should.

> The test succeeds for boxes that are within the given box but do not
> touch the border.
> 3) What about point/polygon in polygon tests with respect to border
> cases? I haven't tested them yet...

It depends on the strategy but the default strategy (winding) returns
false if on the border, as expected. Other strategies are faster but do
not deliver consequent results (e.g. true if on left-side border, false
if on right-side-border, didn't check). Those are included for people
who don't care, or situations where it is not relevant (e.g. selecting a
feature with a mouseclick), but those are not the default.

So, in summary,
- within should return true iff a geometry is completely within another
- the (not yet published) function within_code (non-OGC-compliant)
should give 1 if it is within, 0 if it is on the border, -1 if it is
outside another geometry
- with intersects you can indeed simulate if something is also on the
border, but you take the risk that it is also partly outside the other

Regards, Barend

Geometry list run by mateusz at