Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net