Patent Document ID: 20150317358
Application ID: 14754210
Patent Status: 0

Claim One:
1. A method comprising: receiving a query requesting a spatial relationship between a query object formed from a plurality of line segments and at least one test object; obtaining a minimum bounding box containing the at least one test object; obtaining an In-Memory R-tree (IMR-tree) for accessing one or more bounding boxes of the query object, wherein each bounding box contains one or more of the plurality of line segments of the query object; determining at least one first value in a set of spatial relationship values for the at least one test object by searching the IMR-tree with the minimum bounding box of the at least one test object; wherein the set of spatial relationship values includes one or more values that describe whether a boundary, an interior or an exterior of the at least one test object intersects a boundary, an interior, or an exterior of the query object; determining if the spatial relationship can be resolved based on the at least one first value; if the spatial relationship cannot be resolved based on the at least one first value: obtaining the at least one test object; determining at least one second value in the set of spatial relationship values for the at least one test object by searching the IMR-tree using the at least one test object; wherein the spatial relationship can be resolved based on the set of spatial relationship values after determining the at least one second value; wherein the method is performed by one or more computing devices.