de9im: DE9IM utilities
As part of my continuing education about the theory and methods underlying Shapely, GEOS, JTS, and the OGC's Simple Features specs, I've written a small package of utilities for working with DE9IM 1 matrices and patterns: http://bitbucket.org/sgillies/de9im/. Shapely provides the standard predicates (these are probably my favorite OGC standards) as geometry class methods,
>>> from shapely.wkt import loads >>> p = loads('POLYGON ((1.0 0.0, 0.0 1.0, 1.0 0.0, 0.0 1.0, 1.0 0.0))') >>> q = loads('POLYGON ((3.0 0.0, 2.0 1.0, 1.0 0.0, 2.0 1.0, 3.0 0.0))') >>> p.disjoint(q) False >>> p.intersects(q) True >>> p.touches(q) True
but what if you wanted to test whether the features touched at exactly one point only? A "side hug", you might say. Instead of computing the intersection and checking its geometry type, you can use the de9im package to define a DE9IM matrix pattern and test it against the relation matrix for the two features. The 0 in the pattern below requires that the intersection of the boundaries of the features be a 0dimensional figure. In other words: a point.
>>> from de9im import pattern >>> side_hug = pattern('FF*F0****') >>> im = p.relate(q) >>> print im FF2F01212 >>> side_hug.matches(im) True
The de9im package is 100% tested, which gives me a good starting point for experimenting with more optimal implementations.
There seems to be almost enough standardization between GeoDjango, Shapely, and SQLAlchemy that I could make these patterns callable, and call the relate method on a pair of objects:
class Pattern(object): def __call__(self, a, b): return self.matches(a.relate(b))
to use like so:
>>> side_hug(p, q) True
 1

C. Strobl, “Dimensionally Extended NineIntersection Model (DE9IM),” Encyclopedia of GIS, S. Shekhar and H. Xiong, Eds., Springer, 2008, pp. 240245. [PDF]
Comments
reading list
Author: Jonathan Hartley
Hey Sean,
Recently I think you published a small reading list of geometric papers and the like on topics such as this, and now I can't find it again. Did I imagine this? Can you point me to it? Thanks.
Jonathan
Re: de9im: DE9IM utilities
Author: Sean
It's http://www.zotero.org/groups/geographyandcomputing. If you're interested in adding references, let me know.
Re: de9im: DE9IM utilities
Author: Jonathan Hartley
Thanks! That link once again, without the terminating period included: