Patent Document ID: 9519680
Application ID: 14754210
Patent Status: 1

Claim One:
1. A method comprising: receiving a query requesting a spatial relationship between a query object and at least one test object, the query object comprising a plurality of line segments; 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 of said one or more bounding boxes 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.