Methods For Query Processing Of Topological Relationships Among Complex Spatial Objects

FIELD OF THE INVENTION

0001The present invention generally relates to spatial query systems and geographical information systems and more particularly to topological query processing.

BACKGROUND

0002Spatial database systems operate to provide storage and processing of spatial objects. One special type of spatial database system is a geographical information system (GIS), which is configured to store and operate on geo spatial data, i.e., data relating to features on the Earth's surface

0003One useful operation on spatial data is to determine a topological relationship between spatial objects. Most of the topological relationships between spatial objects are expressible in terms of intersections of a boundary, an interior, and an exterior of one spatial object with a boundary, interior and exterior of another spatial object. For example, the topological relationship of ‘B inside A’ means that the interiors of objects A and B intersect and the exterior of object B intersects the interior of object A, but the boundary of object B does not intersect the boundary or the exterior of object A and the interior of object B does not intersect the boundary or the exterior of object A.

0004Performing these topological relationship queries quickly is one of the most important aspects of GIS and spatial database systems. A typical query could be one that requests the relationships between a query object such as a complex polygon and a large number of test objects. The query object, a complex polygon with thousands of line segments, could represent one of over a 1000 local regions within the U.S. and the test objects could represent the approximately 1 million highway segments in the U.S. This query could be performed by using a vertical line to sweep from left to right, intersecting the highway line segments of the test objects. However, a sweep line based algorithm can perform poorly for at least two reasons: (1) the very large number of test geometries; and (2) the complexity of test geometries and query geometries.

0005When there are a large number of test geometries, a system can organize test geometries using a spatial index to improve query performance. A filtering step uses the spatial index to return a candidate set and a refinement step determines the precise relationships for the objects in the candidate set.

0006When the complexity of the test geometries or query geometries is high, interior approximations and TR*-tree can help improve performance. Interior approximation determines whether a point or a minimum bounding rectangle (MBR) is inside an interior tile of a tessellated query polygon. The TR*-tree decomposes polygons into trapezoids and builds an R*-tree on these trapezoids to improve performance of an INTERSECTS operation.

0007Additionally, different types of test geometries such as multi-point, line, multi-line, polygon and multi-polygon pose challenges for topological queries against query polygons.

0008The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

SUMMARY

0009An embodiment implements queries to discover topological relationships between spatial objects using In-Memory R-tree (IMR-tree) techniques. The embodiment supports polygons, points, lines, and collections of points, lines and polygons. Further, it supports the processing of non-geodetic as well as geodetic 2D geometries. The embodiment uses IMR-Tree techniques in a filtering step in which some relationships can be completely determined using certain optimizations. The embodiment uses IMR-Tree techniques in a refining step, in which some relationships, not completely determined in the filtering step, can be determined using certain optimizations. Because the IMR-Tree techniques are used in both the filtering and refining steps, query performance is significantly improved without user tuning. In one embodiment, the time to answer the query is reduced by approximately a factor of 15 relative to the query without the IMR-tree filtering and refining steps and their optimizations.

0010One method in accordance with an embodiment is a method for processing queries of spatial objects. The method includes receiving a query requesting a description of a spatial relationship between a query polygon and a test object, obtaining the query polygon formed from a plurality of line segments, where the query polygon has a boundary, an interior, and an exterior, obtaining a minimum bounding box (MBR) containing the test object, the test object having one or more features including one or more of a boundary, an exterior, or an interior, obtaining an In-Memory R-tree (IMR-tree) for accessing one or more bounding boxes of the query polygon, where each bounding box contains a particular group of line segments of the query polygon, determining a first spatial relationship between the MBR of the test object and the query polygon by searching the IMR-tree with the MBR of the test object, adjusting values in a 9-intersection matrix to describe the first spatial relationship, where the values of the matrix describe intersections of any features of the test object with the boundary, the interior, or the exterior of the query polygon. If the first spatial relationship does not specify the requested description, the method includes determining a second spatial relationship between the test object and the query polygon by searching the IMR-tree using one or more features of the test object, adjusting the values in the 9-intersection matrix to describe the second spatial relationship. The method further includes returning the adjusted 9-intersection matrix as an answer to the query.

0011Another method in accordance with an embodiment includes receiving a query requesting a description of a spatial relationship between a query line and a test object, obtaining the query line formed from a plurality of line segments, where the query line has a boundary, an interior, and an exterior, obtaining a minimum bounding box (MBR) containing the test object, the test object having one or more features including one or more of a boundary, exterior, or interior, obtaining an In-Memory R-tree (IMR-tree) for accessing one or more bounding boxes of the query line, where each bounding box contains a particular group of line segments of the query line, determining a first spatial relationship between the MBR of the test object and the query line by searching the IMR-tree with the MBR of the test object, adjusting values in a 9-intersection matrix to capture the first spatial relationship, wherein the values of the matrix describe intersections of any features of the test object with the boundary, the interior, or the exterior of the query line. If the first spatial relationship does not specify the requested description, the method includes determining a second spatial relationship between the test object and the query line by searching the IMR-tree using the test object, adjusting values in the 9-intersection matrix to capture the second spatial relationship. The method further includes returning the adjusted 9-intersection matrix as an answer to the query.

BRIEF DESCRIPTION OF THE DRAWINGS

0012In the drawings:

0013<figref idref="DRAWINGS">FIG. 1</figref> depicts various possible topological relations between two objects;

0014<figref idref="DRAWINGS">FIG. 2A</figref> depicts a query polygon with bounding boxes;

0015<figref idref="DRAWINGS">FIG. 2B</figref> depicts an In Memory R-tree (IMR-tree) for the query polygon in <figref idref="DRAWINGS">FIG. 2A</figref>;

0016<figref idref="DRAWINGS">FIGS. 3A-3D</figref> depict a flow chart for an embodiment;

0017<figref idref="DRAWINGS">FIG. 4A</figref> depicts an MBR for a test object completely inside a query polygon;

0018<figref idref="DRAWINGS">FIG. 4B</figref> depicts an MBR for a test object completely outside a query polygon;

0019<figref idref="DRAWINGS">FIG. 4C</figref> depicts an MBR for a test object that intersects a query polygon and has a right edge completely outside the query polygon;

0020<figref idref="DRAWINGS">FIG. 4D</figref> depicts an MBR for a test object that intersects a query polygon and has a left edge completely inside the query polygon;

0021<figref idref="DRAWINGS">FIG. 5</figref> depicts an example relationship between test points and a query polygon;

0022<figref idref="DRAWINGS">FIG. 6</figref> depicts an example relationship between a test line and a query polygon;

0023<figref idref="DRAWINGS">FIG. 7</figref> depicts an example relationship between a test polygon and a query polygon;

0024<figref idref="DRAWINGS">FIG. 8A</figref> depicts an example relationship between an MBR for a test object and a query line;

0025<figref idref="DRAWINGS">FIG. 8B</figref> depicts an example relationship between an MBR for a test object and a query line;

0026<figref idref="DRAWINGS">FIG. 8C</figref> depicts an example relationship between a test point and a query line;

0027<figref idref="DRAWINGS">FIG. 8D</figref> depicts an example relationship between a test line and a query line;

0028<figref idref="DRAWINGS">FIG. 8E</figref> depicts an example relationship between a test polygon and a query line;

0029<figref idref="DRAWINGS">FIG. 9A</figref> depicts an example query collection with bounding boxes;

0030<figref idref="DRAWINGS">FIG. 9B</figref> depicts an example query collection and a test line;

0031<figref idref="DRAWINGS">FIG. 9C</figref> depicts an example query collection and a test multi-line;

0032<figref idref="DRAWINGS">FIG. 9D</figref> depicts an example query collection and multiple line segments; and

0033<figref idref="DRAWINGS">FIG. 10</figref> depicts an example system setting suitable for embodiments.

DESCRIPTION

0034In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

0035The following conventions apply to points, lines, polygons, and query collections. A point or multi-point is a 0-dimensional geometry and its boundary is null.

0036A line segment is considered to be a 1-dimensional geometry and the boundaries of the line segment are its endpoints. A multi-line segment is also considered a 1-dimensional geometry whose boundaries are the endpoints of the multi-line segment. In the convention adopted herein, a line segment or a multi-line can be self-crossing. When a line or multi-line crosses itself, an additional convention is adopted to determine boundaries of the line or multi-line. The additional convention is that if endpoints touch any point of the line or multi-line, they are considered interior points and not boundaries.

0037A polygon and a multi-polygon are 2-dimensional geometries and restrictions are imposed on these geometries. The restrictions include that: a polygon or multi-polygon (1) cannot be self-crossing; (2) must be oriented correctly; and (3) has interiors that are connected, meaning that any two points between interiors can be joined by a path within the polygon or multi-polygon. Correct orientation means that exterior ring boundaries have a counter-clockwise orientation and interior ring boundaries have a clockwise orientation. These rules permit the system to determine whether a point or a line resides inside or outside of query polygon locally.

0038A query collection is a collection of polygons, points, or lines, where the polygons are not self-crossing, and the points and lines are not on or inside the polygons. When an end point of a line in a collection touches a polygon in a collection, the point is an interior point.

0039The table in <figref idref="DRAWINGS">FIG. 1</figref> sets out a basic set of topological relations between two objects A and B, based on their boundaries, interiors, and exteriors. The relations include DISJOINT, TOUCH, ON, OVERLAPBDYDISJOINT, OVERLAPBDYINTERSECT, EQUAL, CONTAINS, INSIDE, COVERS, COVEREDBY, and ANYINTERACT. For example, the relation ON requires that only the interior of object B intersect the boundary of A and the exterior of B intersect the interior of A.

0040<figref idref="DRAWINGS">FIG. 1</figref> also sets out the values of a 9-intersection matrix, which captures the relationships listed above. The 9-intersection matrix as used herein describes the values (null=0, not null=1) of all possible intersections of the interior, boundary, and exterior of a first object with the interior, boundary, and exterior of a second object. The columns of the matrix relate to the first object and the rows of the matrix relate to the second object. Thus, the following matrix equation

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mo>*</mo></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>*</mo></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0041is equivalent to nine equations, one for each row and column position in the matrix. Matrix equation (1) is equivalent to bb=*, ib=1, eb=*, bi=0, ii=0, ei=1, be=0, ie=0 and ee=*. This means that the interior of the first object intersects the boundary of the second object; the exterior of the first object intersects the interior of the second object; and the remaining intersections are null or don't care. In this example, the value of the matrix describes the relationship of “ON.”

In-Memory R-Tree (IMR-Tree)

0042Embodiments use an IMR-Tree to represent the query polygon. <figref idref="DRAWINGS">FIG. 2B</figref> depicts an IMR-tree for an example query polygon depicted in <figref idref="DRAWINGS">FIG. 2A</figref>. As the figure shows, an IMR-tree is built from the boundary line segments of a query polygon as shown in <figref idref="DRAWINGS">FIG. 2A</figref>. This technique improves processing speed and makes it easy to extend the technique to geodetic polygons, such as geocentric 3D surfaces. It also makes it easy to include other query geometries such as query points, query lines, and collections of query point, query lines, and query polygons. It is assumed that an IMR-tree is built on a query polygon, unless otherwise stated.

0043In figure <figref idref="DRAWINGS">FIG. 2A</figref>, the query polygon has 15 line segments. Each line segment is used to delimit a minimum bounding rectangle (MBR), the line segment being the diagonal of the rectangle. This results in 15 MBRs labeled D, E, F, G, H, I, J, K, L, N, O, P, Q, R, S in the figure. The MBRs are advantageously organized as nodes in an in-memory R-tree (IMR-Tree). In the figure, node T represents the entire query polygon, and boxes <b>204</b>-<b>238</b> are nodes in the IMR-Tree. Node A is a node that contains descendent nodes D, E, F, G, H, and S. Node B is a node that contains descendent nodes I, J, K, O, L, and N. Node C is a node that contains descendent nodes P, Q, and R. Thus, each intermediate node represents the MBRs of multiple query polygon line segments. Building the IMR-Tree for the query polygon is an infrequent operation so that the cost of building the IMR-Tree is amortized over a large number of queries using the query polygon.

Overview

0044Referring to <figref idref="DRAWINGS">FIG. 3A</figref>, an embodiment performs the steps depicted to determine the spatial relationship between one of a plurality of test objects and a query object. The test objects are preferably arranged in an R-tree index for MBRs of the test objects to facilitate access to the MBRs. The R-tree for test objects thus includes leaf and non-leaf node MBRs. The non-leaf nodes include the MBRs of one or more descendent nodes. The leaf node MBRs are the terminal nodes in the R-tree.

0045In step <b>302</b>, the system receives a query that requests a description of the relationship between at least one of the test objects and a given query object. In step <b>304</b>, the system builds an IMR-tree on the query object if one is not already built or obtains an already built IMR-tree for the query object, as described above. In step <b>306</b>, the system accesses the R-tree spatial index for the test objects to obtain the MBR for the test object. In step <b>308</b>, the system determines a first spatial relationship between the test object and the query object using the MBR for the test object and the IMR-tree for the query object. Being based on the relationship between the query object and the MBR for the test object, this step acts as a filtering step, because, in some circumstances, depending on the particular relationship, a relationship is resolved without further processing. In step <b>310</b>, the system determines a second spatial relationship between the test object itself and the query object using the IMR-tree. Being based on the relationship between the test object itself and the query object, this step resolves the relationship between the two that the filtering step did not. In step <b>312</b>, the system returns the value of the 9-intersection matrix as a query result.

0046<figref idref="DRAWINGS">FIGS. 3B and 3C</figref> depict step <b>308</b> in more detail. Step <b>308</b> determines the first spatial relationship between the test object and the query object, such as a query polygon, by first discovering whether the MBR of the test object, intersects, or is entirely inside or entirely outside the query object. In step <b>314</b> of <figref idref="DRAWINGS">FIG. 3B</figref>, the system searches for intersections between a current MBR for the test object and the line segments of the query object. If there is an intersection as determined in step <b>316</b>, then each child MBR of the MBR is obtained, in step <b>318</b>, as the current MBR and checked for intersections. If there is no intersection for the current MBR as determined in step <b>316</b>, then the system determines in step <b>320</b> if a point of the MBR is inside the query object. If so, then the MBR is determined in step <b>326</b> to be entirely inside the query object. Otherwise, it is determined in step <b>326</b> to be entirely outside, and there is no need to consider the MBR or its descendants any further.

0047One technique for determining that a point of the MBR is inside the query object is to select a point, such as the top-right corner of the MBR, construct a line segment from the right-top corner of the MBR to the largest x-value of the query object, and then search the IMR-Tree of the query object to find the number of line segments of the query object that intersect the constructed line segment. If the number of intersections is odd, then the top-right corner of the MBR is inside the query object. Another technique determines the point on the query object that is closest to the right-top corner point of the MBR and then determines if the right-top corner point is inside the query object.

0048<figref idref="DRAWINGS">FIG. 3C</figref> depicts additional processing that occurs in step <b>308</b> of <figref idref="DRAWINGS">FIG. 3A</figref> either concurrently or sequentially. In step <b>328</b>, the system determines whether the test geometry MBR is a leaf or non-leaf node in the spatial R-tree for the test geometry. If, as determined in step <b>328</b>, the test geometry MBR is a non-leaf MBR, then the system performs non-leaf MBR optimizations in step <b>330</b>. If, as determined in step <b>328</b>, the system determines that the test geometry MBR is a leaf MBR, then the system performs leaf optimizations in step <b>332</b>.

0049<figref idref="DRAWINGS">FIG. 3D</figref> depicts step <b>310</b> in more detail. Step <b>310</b> determines the second spatial relationship between the test object and the query object by searching the IMR-tree and performing certain optimizations, depending on the type of test object.

Query Polygons

A. MBR Optimizations

0050The IMR-tree for the query polygon enables the system to quickly determine whether a leaf or non-leaf MBR node of the test geometry is inside, intersects, or is outside the query polygon. In addition, the following optimizations help speed up the process and apply to all relationships except CONTAINS, COVERS, and EQUAL. For example, if the MBR of the test geometry contains the MBR of the query polygon, then the MBR of the test geometry contains the entire query polygon itself.

MBR is Non-Leaf Node (i.e., the MBR has Descendent Nodes)

0051The IMR-tree for the query polygon permits quick determination of whether the non-leaf MBR is inside, intersects, or is outside the query polygon, along with the following optimizations, depicted as step <b>330</b> in <figref idref="DRAWINGS">FIG. 3C</figref>.

0052<figref idref="DRAWINGS">FIG. 4A</figref> depicts an MBR <b>404</b> for a test object that is completely inside a query polygon <b>402</b>. For the ANYINTERACT and INSIDE relationships, if MBR <b>404</b> is a non-leaf MBR and is completely inside the query polygon <b>402</b>, descendent test geometries of the MBR <b>404</b> need no further checking, as they too are inside the query polygon.

0053<figref idref="DRAWINGS">FIG. 4B</figref> depicts an MBR for a test object that is completely outside a query polygon <b>402</b>. For all relationships except DISJOINT, if MBR <b>406</b> is a non-leaf MBR and is outside the query polygon, descendent test geometries of the MBR <b>406</b> need no further checking, as they too are outside the query polygon <b>402</b>.

0054For the COVERDBY, ON, OVERLAPBDYDISJOINT, OVERLAPBDYINTERSECT, and TOUCH relationships, if MBR <b>404</b>, <b>406</b> do not intersect the query polygon ring <b>402</b>, as in <figref idref="DRAWINGS">FIGS. 4A and 4B</figref>, descendent test geometries of the MBR <b>404</b>, <b>406</b> need no further processing, as they too do not intersect the query polygon ring.

MBR is Leaf Node

0055For the ANYINTERACT and INSIDE relationships, if MBR <b>404</b> is a leaf MBR and is inside the query polygon <b>402</b> as in <figref idref="DRAWINGS">FIG. 4A</figref>, the test geometry needs no further processing, because the relationship is already defined by the MBR <b>404</b>. Leaf optimizations are depicted as step <b>332</b> in <figref idref="DRAWINGS">FIG. 3C</figref>.

0056For all relationships except DISJOINT, if MBR <b>406</b> is a leaf MBR and is outside the query polygon <b>402</b> as in <figref idref="DRAWINGS">FIG. 4B</figref>, the test geometry needs no further processing, because the relationship is already defined by the MBR <b>406</b>.

0057For the COVERDBY, ON, OVERLAPBDYDISJOINT, OVERLAPBDYINTERSECT, and TOUCH relationships, if MBR is a leaf MBR and does not intersect the query polygon ring, as in <figref idref="DRAWINGS">FIGS. 4A and 4B</figref>, the test geometry needs no further processing, because the relationship is already defined by the MBR <b>404</b>, <b>406</b>.

0058Referring to <figref idref="DRAWINGS">FIG. 4C</figref>, if MBR <b>408</b> is a leaf MBR and intersects a query polygon <b>402</b>, additional optimizations can be performed to quickly determine the relationship.

0059For the COVERDBY, INSIDE, and ON relationships, if any of the four boundary edges of the MBR <b>408</b> is outside the query polygon <b>402</b>, as in <figref idref="DRAWINGS">FIG. 4C</figref>, the test geometry needs no further processing. In <figref idref="DRAWINGS">FIG. 4C</figref>, the right boundary edge of the MBR <b>408</b> is totally outside the query polygon <b>402</b>, so the relationship between the test geometry itself and the query polygon cannot be COVERED, INSIDE, or ON.

0060For the ON and TOUCH relationships, if MBR <b>410</b> is a leaf MBR and if any of the four boundary edges of the MBR <b>410</b> are inside the query polygon <b>402</b>, as in <figref idref="DRAWINGS">FIG. 4D</figref>, the test geometry needs no further processing. In <figref idref="DRAWINGS">FIG. 4D</figref>, the left boundary edge is totally inside the query polygon <b>402</b>, so the relationship between the test geometry itself and the query polygon <b>402</b> cannot be ON or TOUCH.

0061For the ANYINTERACT relationship, if any of the four boundary edges is inside the query polygon <b>402</b>, the test geometry needs no further processing. In <figref idref="DRAWINGS">FIG. 4D</figref>, because the left boundary edge of the MBR is totally inside the query polygon <b>402</b>, the included test geometry must intersect the query polygon <b>402</b>, so ANYINTERACT must be true.

B. Test Geometry Optimizations

0062The above filtering and MBR optimizations discard some test geometries from further consideration. The remaining test geometries require further processing. Further optimizations are possible according to whether the test geometry is a point, line, or polygon, as depicted in <figref idref="DRAWINGS">FIG. 3D</figref>. If the test geometry is a point, then test point geometry optimizations are performed in step <b>338</b>. If the test geometry is a line, then line geometry optimizations are performed in step <b>342</b>. If the test geometry is a polygon, then polygon geometry optimizations are performed in step <b>346</b>.

Test Point Geometry Optimizations

0063<figref idref="DRAWINGS">FIG. 5</figref> depicts an example relationship between test points <b>504</b>, <b>506</b>, and a query polygon <b>502</b>. In <figref idref="DRAWINGS">FIG. 5</figref>, the single points <b>504</b>, <b>506</b> are 0-dimensional, having a null boundary, so it is possible to simplify the 9-intersection matrix by ignoring certain values because they are fixed. In the matrix equation,

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mi>ib</mi></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>ii</mi></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>ie</mi></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math></maths>

0000only the middle column carries the needed information. Six cases can be distinguished, three corresponding individual values being set (the test point is either on the boundary, inside, or outside of the query polygon) and the remaining cases depending on combinations of those values. In <figref idref="DRAWINGS">FIG. 5</figref>, test point <b>504</b> is inside the query polygon <b>502</b> and the test point <b>506</b> is outside the query polygon <b>502</b>. Note that ANYINTERACT means any topological relationship except DISJOINT.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>ON</entry><entry>Only ib = 1 (ON is a special case of</entry></row><row><entry /><entry /><entry>TOUCH)</entry></row><row><entry /><entry>INSIDE</entry><entry>Only ii = 1</entry></row><row><entry /><entry>DISJOINT (outside)</entry><entry>Only ie = 1</entry></row><row><entry /><entry>COVEREDBY</entry><entry>ib = ii = 1; ie = 0</entry></row><row><entry /><entry>TOUCH</entry><entry>ib = 1; ii = 0, ie = * (Don't care)</entry></row><row><entry /><entry>OVERLAPBDYDISJOINT</entry><entry>ii = ie = 1; ib = *</entry></row><row><entry /><entry>ANYINTERACT</entry><entry>ib = 1 OR ii = 1</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

Test Line Geometry Optimizations

0064<figref idref="DRAWINGS">FIG. 6</figref> depicts an example relationship between a test line <b>604</b> and a query polygon <b>602</b>. When the test geometry is a line or multi-line (which is 1-dimensional and has an interior), all topological relationships in <figref idref="DRAWINGS">FIG. 1</figref> are possible except CONTAIN, COVERS, and EQUAL, because a 1-dimensional spatial object cannot contain, cover, or equal a two-dimensional spatial object.

0065To arrive at the values in the matrix, the endpoints and the manner in which the test line <b>604</b> intersects the query polygon <b>602</b> are considered.

The Endpoints

0066Referring to <figref idref="DRAWINGS">FIG. 6</figref>, consideration of the line's endpoints involves determining which endpoints are in the boundary according to the definition of “in the boundary” of the test line <b>604</b>, given above. For any end points in the boundary, the system determines if they are inside, on, or outside the query polygon, which corresponds to setting values bb, bi, and be, respectively. In <figref idref="DRAWINGS">FIG. 6</figref>, endpoint S is “in the line boundary” and outside the query polygon <b>602</b>. In addition, if bb is set, eb can also be set; if bi is set then ii can also be set; and if be is set then ie can also be set.

0067For any endpoints not in the line boundary, the system checks to determine if those endpoints are inside, on, or outside the query polygon, which corresponds to setting values ib, ii, and ie, respectively. This is accomplished in a manner similar to the way in which points are processed.

0068After the endpoints are considered, the 9-intersection matrix for the line SE and the depicted query polygon has the values,

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math></maths>

0000because the endpoints of the line are outside the query polygon.

The Manner of Intersection

0069For the other portion of the line or multi-line (i.e., the portion without endpoints), the system determines the manner in which that portion intersects the query polygon, which determines the settings of values ib, ii, and ie. The line or multi-line is broken down into segments and values in the 9-intersection matrix for each segment are determined in a two-step process. In <figref idref="DRAWINGS">FIG. 6</figref>, the segments of the test line <b>604</b> are SA, AB, BC, and CE, based on points S <b>606</b>, A <b>608</b>, B, <b>610</b>, C <b>612</b>, and E <b>614</b>.

Intersection or Collinearity

0070In the first step of the process, a selected line segment is used to search the IMR-tree of the query polygon <b>602</b> to determine whether there is any intersection or collinearity between the selected segment and any boundary line segments of the query polygon <b>602</b>. Bit ib is set if there is any intersection or collinearity. In <figref idref="DRAWINGS">FIG. 6</figref>, line segment AB is collinear with a boundary line segment of the query polygon <b>602</b>. So, at this point, the 9-intersection matrix becomes

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

Non-Collinearity

0071The second step of the process considers each newly generated line segment, SA, AB, BC, and CE in turn. The system uses the intersection point or points of test line SE to search the IMR-tree to determine whether any of the newly generated segments SA, AB, BC, CE, is inside or outside of the query polygon <b>602</b>. If one of the newly generated segments is inside the query polygon, then the ii bit is set and if the segment is outside the query polygon, then the ie bit is set.

0072In the example, segments SA, BC, and CE are not collinear. Segments SA and CE are outside and segment BC is inside the query polygon. The 9-intersection matrix now becomes

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

0073Thus, bb, bi, be, ib, ii, and ie are sufficient to determine the topological relationship between a line or multi-line and a query polygon or multi-polygon. Values eb, ei, and ee can be set because SE does not fully contain the boundary of the query polygon. The final 9-intersection matrix is

0000<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mo>*</mo></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

0000The relationship between line segment SE, according to the 9-intersection matrix, can be described as OVERLAPBDYDISJOINT and the relationship ANYINTERACT is certainly true as well.

Test Polygon Geometry Optimizations

0074When the test geometry is a polygon or a multi-polygon and the query object is a polygon, then all topological relationships are possible except ON. The procedure for determining the relationship assumes that the test geometry is a test polygon, for purposes of discussion, even though it is applicable to multi-polygons.

First Point of Test Polygon

0075<figref idref="DRAWINGS">FIG. 7</figref> depicts an example relationship between a test polygon <b>706</b> and a query polygon <b>702</b>. Referring to <figref idref="DRAWINGS">FIG. 7</figref>, first the system takes the first point S in <figref idref="DRAWINGS">FIG. 7</figref> of the test polygon and determines if this point is inside, on, or outside the query polygon, which corresponds to setting bi, bb, or be, respectively, which are the values in the first column in the 9-intersection matrix.

0076Thus, if the boundary point of the test polygon is inside the query polygon then (bi=1) and an exterior and interior point of the test polygon are inside the query polygon. In this case, the values of ii and ei can also be set, because if a boundary point of a test polygon is inside the query polygon, then an exterior point and interior point of the test polygon are inside the query polygon. Therefore, the matrix would be:

0000<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

0077If a boundary point of the test polygon is outside of the query polygon, such as point S in <figref idref="DRAWINGS">FIG. 7</figref>, then (be=1) and an interior point of the test polygon is outside of the query polygon. In this case, the value ie can also be set, because if a boundary point of a test polygon is outside a query polygon, then an interior point of the test polygon is outside the query polygon. Therefore, the matrix is:

0000<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

Rest of Test Polygon

0078Next, the system considers the rest of test polygon (i.e., except the first point of test polygon). The values in the 9-intersection matrix are determined by the following two steps.

Step 1

0079The test polygon is broken down into its constituent line segments. In the <figref idref="DRAWINGS">FIG. 7</figref>, these are segments SX, XW, WE, and ES, in counter-clockwise order.

0080For each constituent line segment (SX, XW, WE, and ES), the IMR-tree of the query polygon <b>702</b> is searched to determine if there is any intersection or collinearity between any constituent line segment and the line segments of the query polygon <b>702</b>. In the example, segment SE intersects the query polygon at points A, B, and C.

0081If there is an intersection or collinearity, the value of bb bit is set, and newly generated line segments are formed from the intersecting constituent segment according to the intersection points, A, B, and C, with the query polygon <b>702</b>. In the example, newly generated segments SA, AB, BC, and CE are formed according to the intersections of line SE with the query polygon <b>702</b>.

0082Then, the system determines whether each newly generated line segment, SA, AB, BC, or CE, is collinear with a line segment of the query polygon. If a segment is collinear and both segments have the same direction, then values bb and bi are set. If they have different directions, then values bb, ie, and ei can be set. In <figref idref="DRAWINGS">FIG. 7</figref>, segment AB is collinear with a line segment of the query polygon and the lines have opposite directions.

Step 2

0083Next, for each newly generated line segment that is not collinear, the system uses the intersection point to determine if the newly generated line segment is inside or outside the query polygon. If the newly generated line segment is outside the query polygon, then values be and ie can be set. In the example, segments SA and CE are outside the query polygon, so the 9-intersection matrix becomes:

0000<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths>

0084When the newly generated line segment is inside the query polygon, then values bi, ii, and ei can be set. In the example, segment BC is inside the query polygon, so the matrix now becomes:

0000<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths>

0085In some cases, the values ib, ii, and ie can be set based on a theory regarding two intersecting polygons. The theorem states that for two valid polygons P₁and P₂, if P₁'s polygon ring (PR₁) intersects P₂'s polygon ring (PR₂) at point I, consider two line segments HI and IJ on PR₁, where one of HI and IJ is completely inside PR₂while the other is not completely inside PR₂(i.e., it is either completely outside PR₂or on PR₂), then one boundary line segment of P₁must be inside P₂. In the example in <figref idref="DRAWINGS">FIG. 7</figref>, the test polygon <b>706</b> intersects the query polygon at point B with boundary line segment F of the query polygon <b>702</b> inside test polygon <b>706</b> ring and boundary line segment G of the query polygon <b>702</b> on test polygon <b>706</b> ring, so one of boundary line segments in query polygon must be inside test polygon. In the case, boundary line segment F is inside the test polygon. (Importantly, there is a difference between a test polygon ring and a test polygon: if an object is inside a polygon ring, that object is not necessarily in inside the polygon.) Thus values ib, ii, and ie can be set in a manner similar to the steps for handling a line and a query polygon, as described above.

0086In some cases, such as polygons with interior rings, setting values ib, ii, and ie, or eb and ei is more complex. Performing the following procedure, after the two steps above, handles these cases.

0087The system finds the first line segment from each ring of the query polygon and inserts this line segment and its associated data structure into an array. Then the system scans each line of the test polygon to determine the relationship between each line of the test polygon and the query polygon lines in the array. Three outcomes are possible. (1) The line segment in the array is collinear with a line segment of the test polygon. (2) The first point of the line segment in the array is intersected by one or more line segments in the test polygon. (3) The first point of the line segment is either completely outside or completely inside the test polygon.

0088The first outcome is handled by collinearity step above.

0089The second and third outcomes permit the setting of the ib, ii, ie, eb, or ei values.

0090In the second outcome, the system finds the line segment of the test polygon that is closest to the line segment of the query polygon. Next, the system removes the intersection point from the query polygon to convert the line segment of the query polygon to an open line segment. Then, the system determines whether the open line segment of the query polygon is inside or outside the test polygon. If the open line segment is inside the test polygon, then values ib, ii and ie can be set. If it is outside the test polygon, then values eb and ei can be set. Both the proximity test and the open line segment are needed to make the determination.

0091One way to perform the proximity test is by comparing the angles of the test polygon line segments with the first line segment of the query polygon, with lines having the smaller angle being closer.

0092In the third outcome, if the first point of the line segment of the query polygon is outside of the test polygon, then values eb and ei can be set. If the first point of the line segment of the query polygon is inside the test polygon, then values ib, ii, and ie can be set.

0093In the example of <figref idref="DRAWINGS">FIG. 7</figref>, the matrix becomes

0000<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow></math></maths>

0000and the relationship is OVERLAPBDYINTERSECT.

0094Thus, for a test polygon, the 9-intersection values can also be set sequentially, locally, and independently.

0095If any trigger bit for a certain topological relationship is set, the test polygon can be discarded or returned. For example, if bit ii for TOUCH or bit bb, bi, ib, or ii for ANYINTERACT is set, then the test polygon can be discarded or returned.

Geodetic Geometries

0096The IMR-tree described above is applicable not only to 2D non-geodetic geometries, but also to 2D geodetic geometries.

00972D Geodetic coordinates are coordinates for the surface of the earth considered as an oblate ellipsoid of revolution having two coordinates, latitude, and longitude. These coordinates can be converted to 3D Earth centered coordinates and 3D minimal bounding boxes (MBB) can be built on those coordinates and used in an IMR-tree for the query geometry. An MBR in the test geometry now becomes a 3D MBB and the optimizations described above in regard to MBRs apply. For example, the system determines whether each of the six boundary faces in a leaf MBB is inside, intersects, or is outside of the query polygon. If any boundary face is outside the query polygon, its test geometry can be discarded in the cases of COVEREDBY, INSIDE, and ON.

Arc Geometries

0098Both test geometries and query geometries can contain arcs as a component of a line or a polygon. In the case of the query geometry, the IMR-tree is built with any arcs that are present. However, arc-arc and arc line intersections need adjustments, as there can be two possible intersection points for arc-arc and arc-line intersections. To handle this, in one embodiment, the arc is split into several arcs at the intersection points. For each newly generated arc, the system obtains the tangent line from the intersection point and determines which pair of tangent lines is the closest. In one technique, angles between the lines can determine which pair is closest. In another technique, values of an alpha function can be compared, where

0000<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mrow><mi>alpha</mi><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>/</mo><mi>radius</mi></mrow></mtd><mtd><mrow><mi>if</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>arc</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>center</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>to</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>left</mi></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>if</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>line</mi></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><mn>1</mn></mrow><mo>/</mo><mi>radius</mi></mrow></mtd><mtd><mrow><mi>if</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>arc</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>center</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>to</mi><mo></mo><mstyle><mspace width="0.6em" height="0.6ex" /></mstyle><mo></mo><mi>right</mi></mrow></mtd></mtr></mtable><mo>}</mo></mrow></mrow></math></maths>

0099By considering the difference between alpha values, the system can decide which pair in a set of tangent lines is the closest, even if one of the tangent lines is collinear with another tangent line or line.

Composite Topological Relationships

0100Composite topological relationships are those formed by the logical ‘OR’ of the primary relationships. To include such relationships, some adjustments are needed. For example, for the COVEREDBY relationship, if a non-leaf MBR does not intersect the query polygon, its descendent test geometries can be discarded. However, if the composite relationship INSIDE+COVEREDBY is considered, then the descendant geometries cannot be discarded. Additionally, if bit be or bit ie are set for a test geometry, then INSIDE+COVEREDBY can be ruled out. The same test holds true for INSIDE+COVEREDBY+EQUAL.

0101The composite relationship OVERLAPPBDYDISJOINT+OVERLAPBDYINTERSECT can be verified by testing that values ii, ie, and ei are all set.

0102Some relationships between spatial objects are useful even though they are not topological relationships. Such relationships include WITHIN_DISTANCE and nearest neighbor (NN). An embodiment can handle the WITHIN_DISTANCE relationship by building the IMR-tree on the boundary line segments of the original query polygon and performing the above-described MBR optimizations. During those optimizations, the system enlarges the MBR by the distance and uses the new MBR to search the in-memory tree of the query polygon. The system then splits a complex test geometry into simple primitives, point, line, and arc, and searches the IMR-tree with these primitives. If any primitive (point, line, or arc) of the test geometry is already within the distance of a query polygon, the rest of the test geometry need not be considered.

Query Lines

0103In one embodiment, query objects are query lines instead of query polygons. An IMR-tree is constructed on the query lines in a manner similar to constructing the tree for a query polygon. <figref idref="DRAWINGS">FIG. 8A</figref> depicts a query line <b>802</b> as the query object.

MBR Optimizations

0104These optimizations apply to all topological relationships except CONTAINS, COVERS, and EQUAL.

Non-Leaf Optimizations

0105The IMR-tree for the query line permits quick determination of whether a non-leaf MBR for the test object intersects the query line. The following optimizations are used to further determine the topological relationships.

0106For all topological relationships except DISJOINT, if a non-leaf MBR does not intersect the query line, as in <figref idref="DRAWINGS">FIG. 8A</figref>, descendent test geometries of the non-leaf MBR need no further processing.

0107For COVEREDBY, ON, and OVERLAPBDYINTERSECT, if a non-leaf MBR for the test object does not contain any boundary points of the query line as in <figref idref="DRAWINGS">FIG. 8B</figref>, descendent test geometries of the non-leaf MBR need no further processing.

Leaf Optimizations

0108For a leaf MBR, the system uses the IMR-tree to determine if the MBR intersects the query line. The following optimizations are used to further determine the topological relationships.

0109For all topological relationships except DISJOINT, if a leaf MBR does not intersect the query line, as in <figref idref="DRAWINGS">FIG. 8A</figref>, then its test geometry need not be further considered.

0110For COVEREDBY, ON, and OVERLAPBDYINTERSECT, if a leaf MBR does not contain any boundary points of the query line, as in <figref idref="DRAWINGS">FIG. 8B</figref>, its test geometry need not be further considered. (Only a test point can be ON a query line, and the leaf MBR of a test point is the test point itself.)

0111If a leaf MBR does intersect a query line as in <figref idref="DRAWINGS">FIG. 8B</figref>, then the system performs additional optimizations by checking if each of the four boundary edges of the leaf MBR intersects the query line, in the case of COVERDBY, and INSIDE.

0112If any of the four boundary edges does not intersect the query line, its test geometry need not be further considered.

0113In <figref idref="DRAWINGS">FIG. 8B</figref>, the test geometry enclosed by a leaf MBR cannot be COVERED, or INSIDE the query line because the right boundary edge does not intersect the query line.

Test Geometry Optimizations for Query Lines

Test Point Geometry Optimizations

0114When the test geometry is a single point such as <b>808</b> or <b>810</b> in <figref idref="DRAWINGS">FIG. 8C</figref>, only the relationships INSIDE, ON, and DISJOINT are possible with a query line. The system searches the IMR-tree to determine these relationships. If the search discovers that the test point intersects the interior of the query line, then value ii is set. If the search discovers that the test point intersects one of the boundary points of the query line, then value ib is set. If the search discovers that the test point does not intersect the query line, as in <figref idref="DRAWINGS">FIG. 8C</figref>, then the bit ie is set.

0115If the test geometry is a multi-point, each point in the multi-point is tested as described above.

Test Line Geometry Optimizations

0116When the test geometry is a line or multi-line and the query object is a line, all topological relationships, except ON, are possible. <figref idref="DRAWINGS">FIG. 8D</figref> depicts a line test object intersecting a query line.

0117Referring to <figref idref="DRAWINGS">FIG. 8D</figref>, the system first determines the ends point of the test line that are in the boundary of the test line. For the endpoints in the boundary, the system determines if they are inside, on, or, outside, the query line, which corresponds to setting values bi, bb, and be, respectively. Additionally, when bit bi is set, then ei can be set, and when be is set ie can be set.

0118For the remaining end points that are not in the boundary of the test line, the system determines if they are inside, on, or outside the query line, which corresponds to setting values ii, ib, and ie.

0119The system next determines the manner in which the remaining portion of the line intersects the query line, which corresponds to the settings of values ii, ib and ie. Each segment of the line or multi-line is considered separately. When the segment intersects the query line, the system divides the segment into newly generated line segments according to the intersection points.

0120In <figref idref="DRAWINGS">FIG. 8D</figref>, the line segment SE is divided into newly generated segments SA, AB, BC, and CE. Open Line Segment BC is outside the query line. Open Line Segment CE is outside the query line, so bit ie can be set.

Collinearity

0121When one of the newly generated line segments is collinear with a portion of the query line, as AB is in <figref idref="DRAWINGS">FIG. 8D</figref>, then the system determines if value ei can be set. This requires that the system determine whether the next line segment in the query line is collinear with any segment of the test line. If there is no collinear case, then value ei can be set. Determining if a segment of the query line is collinear with any segment of the test line may require that a new IMR-tree be constructed on the test line, so that the new IMR-tree can be searched using segments of the query line.

Test Polygon Geometry Optimizations

0122When the test geometry is a polygon or a multi-polygon, as in <figref idref="DRAWINGS">FIG. 8E</figref>, all relationships, except ON, INSIDE, COVEREDBY, and EQUAL, are possible.

0123The system considers each line segment of the test polygon in turn. Each line segment is assumed to be properly oriented, as exterior ring boundaries traverse counterclockwise and interior ring boundaries traverse clockwise. Each line segment is divided into newly generated line segments according to its intersections with the query line. For example, if segment SE is considered part of a test polygon, then it is divided into four new segments, SA, AB, BC, and CE. For segment AB, the collinear line, values bi and ie can be set. For segments SA, BC, and CE, the system can set values be and ie.

0124Additionally, the system builds a new IMR-tree on the test geometry (polygon or multi-polygon) and uses the intersected line segment of the query line to search this new IMR-tree to determine whether the line segments of the query line are inside of or outside of the test geometry. This determines how to set values ii and ei for the particular line segment of the query line.

Query Collections

0125A collection geometry includes a collection of points, lines, and polygons. In a valid collection geometry, polygons are not self-crossing, and points or lines are not on or inside polygons. Also, in such collections, only interior points of a line touch a polygon. <figref idref="DRAWINGS">FIG. 9A</figref> depicts a query collection that includes a triangle ABC <b>904</b> and a line AD <b>902</b>. Point A is an interior point of the line AD.

0126Additionally, some 9-intersection matrices can only occur when the geometry is a collection geometry. For example, referring to <figref idref="DRAWINGS">FIG. 9B</figref>, the relationship TOUCH-TOUCH can occur when one spatial object is a collection geometry that includes a triangle ABC <b>904</b> and a line AD <b>902</b>, and the other spatial object, the test object, is a line AB <b>906</b>. The 9-intersection matrix for the relationship depicted in <figref idref="DRAWINGS">FIG. 9B</figref> is

0000<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

0127Another example is the relationship COVEREDBY-COVERS, which occurs when one object is a collection geometry that includes a triangle ABC <b>904</b> and a line AD <b>902</b> and the other object, the test object, is a multi-line that includes line ABC <b>908</b> and a non-closed line DAE <b>910</b>, as depicted in <figref idref="DRAWINGS">FIG. 9C</figref>. The 9-intersection matrix for the relationship depicted in <figref idref="DRAWINGS">FIG. 9C</figref> is

0000<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo>.</mo></mrow></mrow></math></maths>

0128The following MBR optimizations pertain to the case when the query object is a collection and an IMR-tree is built on a collection. All topological relationships except CONTAINS, COVERS, and EQUAL are possible.

MBR Optimizations

Non-Leaf MBR Optimizations

0129An IMR-tree built on the contents of a query collection, as depicted in <figref idref="DRAWINGS">FIG. 9A</figref>, <b>9</b>B, or <b>9</b>C, permits quick determination of whether an MBR of the test geometry intersects the query collection. The following optimizations help to further determine the topological relationships.

0130For ANYINTERACT and INSIDE, if a non-leaf MBR is inside a polygon of the query collection, the relationship regarding the descendent geometries of the non-leaf MBR is known and needs no further processing.

0131For all topological relationships except DISJOINT, if a non-leaf MBR does not intersect the query collection, the relationship of the descendent test geometries of the non-leaf MBR is known and needs no further processing.

0132For COVEREDBY, ON, OVERLAPBDYDISJOINT, OVERLAPBDYINTERSECT, and TOUCH, if a non-leaf MBR is inside a polygon of the query collection, the relationship of the descendant geometries of the non-leaf MBR is known and needs no further processing.

0133For COVEREDBY, ON, and OVERLAPBDYINTERSECT, if a non-leaf MBR does not contain any boundary points of lines in the query collection, and does not intersect any polygon rings in the query collection, descendant test geometries of the non-leaf MBR need no further processing.

Leaf MBR Optimizations

0134For a leaf MBR, the IMR-tree permits quick determination of whether the MBR intersects the query collection. The following optimizations help further determine the topological relationships.

0135For ANYINTERACT and INSIDE, if a leaf MBR is inside a polygon of the query collection, test geometries of the leaf MBR need no further processing.

0136For all topological relationships except DISJOINT, if a leaf MBR does not intersect the query collection, the test geometry of the leaf MBR needs no further processing.

0137For COVERDBY, ON, and OVERLAPBDYDISJOINT, OVERLAPBDYINTERSECT, and TOUCH, if a leaf MBR is inside a polygon of the query collection, test geometries of the leaf MBR need no further processing.

0138For COVEREDBY, ON, and OVERLAPBDYINTERSECT, if a leaf MBR does not contain any boundary points of lines in the query collection, and does not intersect any polygon rings in the query collection, the test geometry of the leaf MBR needs no further processing.

0139When a leaf MBR intersects a query collection, the following optimizations help further determine the topological relationships.

0140For COVEREDBY, INSIDE, and ON, if any of the four boundaries edges does not intersect the query collection, the test geometry needs no further processing.

0141For ON and TOUCH, if any of the four boundary edges is inside a polygon of the query collection, the test geometry needs no further processing.

0142For ANYINTERACT if any of the four boundary edges is inside a polygon of the query collection, the test geometry needs no further processing.

0143<figref idref="DRAWINGS">FIG. 9C</figref> shows a relationship between a collection geometry and a multi-line. The collection geometry includes triangle ABC <b>904</b> and a line segment AD <b>902</b>. Multi-line geometry includes closed line ABD and non-closed line DAE.

0144The test geometry is a closed line DAE <b>908</b> and a non-closed line <b>910</b>. The non-closed line DAE <b>910</b> is split into two segments DA and AE. Newly generated line segment DA intersects triangle ABC at point A and at all points except point A outside of triangle ABC. Newly generated line segment DA intersects line DA in the query collection. Line segment AE, except for point A, is inside triangle ABC. Point A of the test line intersects the query collection at point A, so corresponding bit ii is set.

Test Geometry Optimizations for Query Collections

0145In the case of query collections, optimizations to test geometries apply as well.

0146<figref idref="DRAWINGS">FIG. 9D</figref> depicts an example query collection <b>922</b> with triangle ABC and line AD in the collection. The test object is line DAE <b>924</b>.

0147Processing of line DAE <b>924</b> depends on any intersections of that line with the query collection <b>922</b>. In <figref idref="DRAWINGS">FIG. 9D</figref>, test line DAE <b>924</b> intersects the query collection <b>922</b> at point A. This requires that segment DA and segment AE be considered.

0148For line segment DA, the system first determines if segment DA intersects any isolated points of the query collection <b>922</b> if any such points are present. Corresponding values in the 9-intersection matrix are set.

0149Next, line segment DA is considered as an open line segment, i.e., as not including point A. The system determines that open line segment DA is completely outside triangle ABC of the query collection <b>922</b>. Then the system determines how open line segment DA intersects line DA of the query collection <b>922</b>. Additionally, open line segment AE (segment AE without point A) is completely inside triangle ABC of the query collection <b>922</b>, so no further processing of open line segment AE is needed.

0150Finally, the system considers point A itself. Point A intersects the interior of the query collection, permitting value ii to be set in the 9-intersection matrix.

0151Thus, the 9-intersection matrix becomes

0000<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>bb</mi></mtd><mtd><mi>ib</mi></mtd><mtd><mi>eb</mi></mtd></mtr><mtr><mtd><mi>bi</mi></mtd><mtd><mi>ii</mi></mtd><mtd><mi>ei</mi></mtd></mtr><mtr><mtd><mi>be</mi></mtd><mtd><mi>ie</mi></mtd><mtd><mi>ee</mi></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo></mrow></math></maths>

0000which describes the relationship as “COVEREDBY”.

Hardware Overview

0152According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

0153For example, <figref idref="DRAWINGS">FIG. 10</figref> is a block diagram that depicts a computer system <b>1000</b> upon which an embodiment may be implemented. Computer system <b>1000</b> includes a bus <b>1002</b> or other communication mechanism for communicating information, and a hardware processor <b>1004</b> coupled with bus <b>1002</b> for processing information. Hardware processor <b>1004</b> may be, for example, a general-purpose microprocessor.

0154Computer system <b>1000</b> also includes a main memory <b>1006</b>, such as a random access memory (RAM) or other dynamic storage device, coupled to bus <b>1002</b> for storing information and instructions to be executed by processor <b>1004</b>. Main memory <b>1006</b> also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor <b>1004</b>. Such instructions, when stored in non-transitory storage media accessible to processor <b>1004</b>, convert computer system <b>1000</b> into a special-purpose machine that is customized to perform the operations specified in the instructions.

0155Computer system <b>1000</b> further includes a read only memory (ROM) <b>1008</b> or other static storage device coupled to bus <b>1002</b> for storing static information and instructions for processor <b>1004</b>. A storage device <b>1010</b>, such as a magnetic disk or optical disk, is provided and coupled to bus <b>1002</b> for storing information and instructions.

0156Computer system <b>1000</b> may be coupled via bus <b>1002</b> to a display <b>1012</b>, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device <b>1014</b>, including alphanumeric and other keys, is coupled to bus <b>1002</b> for communicating information and command selections to processor <b>1004</b>. Another type of user input device is cursor control <b>1016</b>, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor <b>1004</b> and for controlling cursor movement on display <b>1012</b>. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

0157Computer system <b>1000</b> may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system <b>1000</b> to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system <b>1000</b> in response to processor <b>1004</b> executing one or more sequences of one or more instructions contained in main memory <b>1006</b>. Such instructions may be read into main memory <b>1006</b> from another storage medium, such as storage device <b>1010</b>. Execution of the sequences of instructions contained in main memory <b>1006</b> causes processor <b>1004</b> to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

0158The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operation in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device <b>1010</b>. Volatile media includes dynamic memory, such as main memory <b>1006</b>. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge.

0159Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus <b>1002</b>. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

0160Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor <b>1004</b> for execution. For example, the instructions may initially be carried on a magnetic disk or solid-state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system <b>1000</b> can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus <b>1002</b>. Bus <b>1002</b> carries the data to main memory <b>1006</b>, from which processor <b>1004</b> retrieves and executes the instructions. The instructions received by main memory <b>1006</b> may optionally be stored on storage device <b>1010</b> either before or after execution by processor <b>1004</b>.

0161Computer system <b>1000</b> also includes a communication interface <b>1018</b> coupled to bus <b>1002</b>. Communication interface <b>1018</b> provides a two-way data communication coupling to a network link <b>1020</b> that is connected to a local network <b>1022</b>. For example, communication interface <b>1018</b> may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface <b>1018</b> may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface <b>1018</b> sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

0162Network link <b>1020</b> typically provides data communication through one or more networks to other data devices. For example, network link <b>1020</b> may provide a connection through local network <b>1022</b> to a host computer <b>1024</b> or to data equipment operated by an Internet Service Provider (ISP) <b>1026</b>. ISP <b>1026</b> in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet” <b>1028</b>. Local network <b>1022</b> and Internet <b>1028</b> both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link <b>1020</b> and through communication interface <b>1018</b>, which carry the digital data to and from computer system <b>1000</b>, are example forms of transmission media.

0163Computer system <b>1000</b> can send messages and receive data, including program code, through the network(s), network link <b>1020</b> and communication interface <b>1018</b>. In the Internet example, a server <b>1030</b> might transmit a requested code for an application program through Internet <b>1028</b>, ISP <b>1026</b>, local network <b>1022</b> and communication interface <b>1018</b>.

0164The received code may be executed by processor <b>1004</b> as it is received, and/or stored in storage device <b>1010</b>, or other non-volatile storage for later execution.

0165In the foregoing specification, embodiments have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the embodiments, and what is intended by the applicants to be the scope of embodiments, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.