Re: [Boost-bugs] [Boost C++ Libraries] #10772: boost::geometry::within() does not recognize empty boxes

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #10772: boost::geometry::within() does not recognize empty boxes
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-08-19 18:48:49

#10772: boost::geometry::within() does not recognize empty boxes
-------------------------------+---------------------------
  Reporter:  bromeon@…         |      Owner:  barendgehrels
      Type:  Bugs              |     Status:  new
 Milestone:  To Be Determined  |  Component:  geometry
   Version:  Boost 1.57.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+---------------------------

Comment (by awulkiew):

 Do you have in mind some specific use case where this is problematic for
 you or do you think that the library is not OGC-conformant enough in this
 case?
 In the first case `covered_by()` could be used instead. If the latter is
 true then see below.

 TL,DR

 The OGC standard doesn't define Box Geometry (or to be more precise axis-
 aligned box), it doesn't define when a Box is valid and what's the
 interior, boundary and exterior of a Box. It's not said that a Box may
 degenerate to a Point or to a Segment and be still valid Geometry. It's
 not clear that the definition of an interior and boundary should be taken
 from other geometries like a Point or a Segment or a Polygon in the case
 of degenerated 3D Box. And even if it'd probably work well both points
 mentioned by you not necessarily are true simply because in the OGC specs
 axis-aligned Boxes doesn't exist.

 Indeed currently the library uses Box definition different than the one
 you presented. That is currently a degenerated Box consists only of a
 boundary (opposed to a Point which has no boundary). It's because this way
 it allows to use only this small set of 3 conditions to check the `within`
 predicate. The last condition is there because for `within` to be `true`
 the interiors must overlap. This way also a small set of conditions is
 needed to check `touches` or `overlaps` predicates and be consistent with
 `within`.

 Btw, I'm calling it "degenerated" because if it was empty it'd probably
 have no interior nor boundary, it'd be treated as an exterior so any
 special predicate should probably return `false` for it.

 Now, if we wanted to treat degenerated Box as a Point (a Geometry with no
 boundary) or Segment (linear interior and 2-point boundary) we couldn't
 remove the 3rd condition. Without the 3rd condition `within` would return
 `true` incorrectly e.g. for a degenerated Box overlapping the boundary of
 a second non-degenerated Box. In order to make it "OGC-conformant" we'd be
 forced to add 2 more conditions:
 - check if a contained degenerated Box/Point is on the boundary of
 containing because then the interiors wouldn't overlap
 - check if containing Box is not degenerated as well because in this case
 it wouldn't have a boundary, so a `within` could return `true` in this
 case (for both degenerated).
 Not to mention that we'd be forced to change the implementation of
 `touches` in a similar way, so add more conditions. Also, since a Box
 might degenerate to a Segment we'd be forced to add more conditions to
 `overlaps` and support Boxes in `crosses`. To sum up, currently `within`
 uses a definition of a Box which is consistent across spatial predicates
 and allows to implement them with a minimal set of conditions.

 With that said, I'm not against removing the third condition. However I'd
 like to hear more "complete" proposal, taking into account other
 predicates and providing a clear definition of a Box. If we removed the
 3rd condition the predicate check would be simpler/faster. The Box is not
 defined in the OGC-specification so we may basically do whatever we think
 is the best. But it would be less consistent across functions and still
 not "OGC-conformant". It would work exactly how `covered_by` works right
 now so wouldn't add functionality.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10772#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.