Geometry Boost List: [geometry] Indexable - Geometry intersection and spatial query predicates (was: Box - Geometry intersection)

Subject: [geometry] Indexable - Geometry intersection and spatial query predicates (was: Box - Geometry intersection)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2012-12-11 19:02:32

Barend Gehrels wrote:
> Yesterday I checked intersection but not intersects. I did check it this
> morning - both algorithms are implemented for polygon/box and
> polygon/ring. So you must have another problem here, do you know which?
> What is the message exactly?
Yes, you're right. I have tests for Points and Boxes, probably seen that 
they don't compile and thought that intersects() is not implemented for 
both (like in the case of other operations). Sorry for confusion. It's 
just not implemented for Points.

For now all predicates work for Box Geometries (except for touches()). 
intersects(), which is probably the most important, works for Polygons 
and Rings already and this is nice functionality (for Box Indexables). 
I'd say that for now all we need is intersects() for Points.

Below you may find detailed info about all spatial query predicates. 
About algorithms which need to be implemented in order to have specific 
predicates working. Read only if you have too much free time ;)

In the spatial query the tree is traversed. In the process, predicates 
are checked for Nodes and Values/Indexables. intersects() is an example 
of predicate which is checked both for Values and Nodes. Other 
predicates may require different checks. So even if disjoint() is 
implemented for Box and Polygon it won't work because the Node must be 
checked using covered_by(Box, Polygon) which is not implemented. I 
present the full list of predicates checked during spatial query.

Passed         |  Checked          |  Checked
predicate      |  for Indexable    |  for Node
---------------+-------------------+------------------
G              | intersects(I, G)  | intersects(B, G)
intersects(G)  | intersects(I, G)  | intersects(B, G)
covered_by(G)  | covered_by(I, G)  | intersects(B, G)
disjoint(G)    | disjoint(I, G)    | !covered_by(B, G)
overlaps(G)    | overlaps(I, G)    | intersects(B, G)
within(G)      | within(I, G)      | intersects(B, G)
!intersects(G) | !intersects(I, G) | !covered_by(B, G)
!covered_by(G) | !covered_by(I, G) | !covered_by(B, G)
!disjoint(G)   | !disjoint(I, G)   | !disjoint(B, G)
!overlaps(G)   | !overlaps(I, G)   | true
!within(G)     | !within(I, G)     | !within(B, G)
---------------+-------------------+------------------
Commented out
---------------+-------------------+------------------
touches(G)     | touches(I, G)     | intersects(B, G)
!touches(G)    | !touches(I, G)    | !intersects(B, G)
---------------+-------------------+------------------

G stands for Geometry
I stands for Indexable (Point or Box)
B stands for Box (or BoundingObject)

Regards,
Adam