11

Ok, I have to admit, I don't really delve too deep into the semantics of the spatial operators list below, I'm more of a user, I write software to drive the SQL most of the time and don't really think about it too much.

However, I have a situation where a spatial operation I'm doing is going dog slow, on a table that has great indexes on and has never caused a problem before now.

As a result, I'm trying to figure out which of the following is my best bet to use, that will give me the best performance, however, sometimes I find my searches don't return anything when I know they should, and sometimes return stuff when they shouldn't.

SO I'm reaching out, to ask if some one can give me the actual definition, such as criteria to match, fully within enclosing geometry, or within outer ring etc etc of each of the following operations:

Equals(Geom1, Geom2):int
Disjoint(Geom1, Geom2):int
Touches(Geom1, Geom2):int
Within(Geom1, Geom2):int
Overlaps(Geom1, Geom2):int
Crosses(Geom1, Geom2):int
Intersects(Geom1, Geom2):int
Contains(Geom1, Geom2):int
Relate(Geom1, Geom2):int

If you can give a concrete example of when they will and will not match too, that would be great.

For reference, I'm searching on a table of Linestrings, using a rectangular polygon, rotated to be pointing in the direction of travel (It's part of a traffic managment app)

For further reference, here is a sample of the SQL the app generates to perform a search:

SELECT recordID,AsBinary(geometry) AS geometry,Distance(GeomFromText('POINT(-1.84101 54.85078)',4326), geometry) AS distanceFromGps FROM linegrid WHERE Intersects(GeomFromText('POLYGON ((-1.8413149820810311 54.850782468607292, -1.8409507853094111 54.850952257034713, -1.8408279009723911 54.850864894077496, -1.8411920982612455 54.850695105650068, -1.8413149820810311 54.850782468607292))'), geometry)

You can see in this example I'm using intersects trying the others as mentioned doesn't quite give the results I expect, hence why I'm asking the question.

Please note, I'm not particularly bothered about actual faster/other ways of doing this at the moment, BUT if you do happen to spot a better way do feel free to shout up :-)

For now all I'm mostly trying to understand is the differences between each of the operations.

As for doing it faster/better I intend to open a different question for that at a later date.

For more reference, the Spatial engine this is working against is Spatilite 2.3.0, and I can't upgrade it due to the devices it's running on not having a more up to date build for it (Windows CE)


I'm going to choose mintix'es answer here as that provided a super easy to understand grid and description of all the various operations, which answered my question.

I'm still faced with getting performance on the routines up, but I do now have a few strategies to try on that one, I may still seek advice here from the group with regards to that.

@Vince deserves some credit too, as that white paper is definitely the definitive answer, but it's also quite challenging to read (I had to read through it several times) , for anyone wanting the real I am on these operations The Clementini paper is the way to go, if you need an easy to understand overview while developing solutions however, the FME link should be open in another browser tab.

6
  • Possible speed up - perhaps test bounding box intersection with "MbrIntersects" before testing that the geometry intersects?
    – user2856
    Jan 20, 2014 at 22:45
  • Hi Luke. I did originally try using an MBR, but then realized I can't rotate it. Unfortunately I have to rotate the box to point in the direction of a GPS bearing so it has to be a polygon. Thanks for the suggestion though.
    – shawty
    Jan 21, 2014 at 21:22
  • the suggestion wasn't to use an MBRIntersects test only. It was to use MbrIntersects to reduce the number of geometries that the Intersects function tests against. Narrowing the search this way is a pretty standard method of speeding up overlays.
    – user2856
    Jan 21, 2014 at 22:47
  • Ah yes, now I reread that, I understand what you mean.
    – shawty
    Jan 23, 2014 at 19:20
  • If there are a lot of rows in the linegrid, and you aren't going to hit most of them, a spatial index might help.
    – BradHards
    Feb 1, 2014 at 7:10

2 Answers 2

17

You're looking for the "Dimensionally Extended 9 Intersection Matrix" or DE-9IM for short.

DE-9IM by FME

That FME link has great examples of the spatial operators you listed above. It breaks it down into a 3x3 true/false matrix with examples and descriptions of each predicate attribute.

2
  • WOW!! The link is super useful, had a quick scan, going to read it in more detail a little later.
    – shawty
    Jan 21, 2014 at 21:20
  • Link is broken. Mar 2, 2016 at 18:48
8

The reference work I use for expectations of spatial operators is the Clementini paper ("A Small Set of Formal Topological Relationships Suitable for End-User Interaction", Eliseo Clementini, Paolino Di Felice, and Peter van Oosterom, 1993). It lays out the theory behind the operators with respect to interiors, exteriors, and dimensionality, which eliminates the guesswork of which relationships are captured by which operators between which types.

Whether all implementations honor all aspects of Clementini operators is, unfortunately, another issue.

1
  • Yea, i hear ya there... the world of I.T is full of standards that no one ever seems to honour, thanks for the info I'll go look for a copy of the paper.
    – shawty
    Jan 21, 2014 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.