The Problem
Given two non-convex polygons without holes, I want to calculate the corresponding 9 Intersection Matrix.
A 9 intersection matrix is of the form:
| I | B | E
I | I ∩ I | I ∩ B | I ∩ E
B | B ∩ I | B ∩ B | B ∩ E
E | E ∩ I | E ∩ B | E ∩ E
I - Interior
B - Border
E - Exterior
At each cell of the matrix, I'm interested in knowing whether the intersection exists or not, and if it exists I want to know whether it is a point, line or polygon.
It is worth noting that for a given cell, the intersection between the polygons may be composed by a set of geometries. However, if the set is composed by a point and a line, I'm only interested in knowing about the line. In this logic, points have lowest priority and polygons highest.
Therefore, if we consider that a point is 0-dimensional, a line 1-dimensional and a polygon 2-dimensional, I want to know the highest dimension of the intersection.
What I have so far
Ok, so there are algorithms, such as the Vatti clipping algorithm, that clip a polygon to another. This means that these algorithms provide the intersection geometric object, which may be a collection of objects. After having this result, I believe it to be possible to derive the 9-Intersection Matrix, even though I haven't really thought it through.
One of the problems with this approach is the quadratic complexity of the clipping algorithms, since this algorithm is to be included in a GIS for efficient topological query answering.
I do believe however that it is possible to fill out the matrix using solely the intersections between the borders, computable in O(Nlog(N) + k) where K is the number of intersections using the algorithm proposed by Balaban, and simple point location.
However, I also believe that this approach will lead to a very big set of conditions. So far I have the following set of conditions:
- The intersection between exteriors is always 2-dimensional
- If the border of the two polygons intersects in at a point that is not a corner, the intersection of the interiors is 2-dimensional
- If the borders do not intersect and at least one point of a polygon is contained in the other, then the first is contained in the second (and a lot of matrix cells can be filled out)
- If the borders do not intersect and at least one point of a polygon lies outside the other, then the polygons are disjoint (and all matrix cells can be filled out)
The problem is that this set of rules is by far incomplete. For example, I still don't have a good rule for the case in which the borders intersect at a point that is also a corner for at least one of the polygons.
The Actual Question
Given two non-convex polygons without holes nor self-intersections, what is the most efficient way of calculation the 9-Intersection Matrix that relates the two geometric objects?
