Prädikate und DE-9IM
Räumliche Prädikate beantworten Ja/Nein-Fragen zur Beziehung zweier Geometrien: Schneiden sie sich, enthält die eine die andere, berühren sie sich nur. Alle beruhen auf dem vollen DE-9IM-Modell von OGC und NetTopologySuite (ADR 0013) und rechnen exakt auf den Eingabekoordinaten, ohne Gitter.
Die Schnittmatrix
Für zwei Geometrien a und b liefert a.Relate(b) eine IntersectionMatrix: für jede Kombination aus Inneres (I), Rand (B) und Äußerem (E) von a und b die Dimension ihres Schnitts (F = leer, 0 = Punkte, 1 = Linien, 2 = Flächen).
var square = Wkt.Read<IPolygon2D>("POLYGON((0 0, 10 0, 10 10, 0 10, 0 0))");
var edge = Wkt.Read<IPolyline2D>("LINESTRING(0 0, 10 0)"); // lies on the boundary of the square
Console.WriteLine(square.Contains(edge)); // False - DE-9IM: no point of the edge lies in the interior
Console.WriteLine(square.Covers(edge)); // True - boundary points count
Console.WriteLine(square.Touches(edge)); // True
Console.WriteLine(square.Relate(edge)); // FF2101FF2
Die Matrix wird zeilenweise in der Reihenfolge I, B, E von a gegen I, B, E von b geschrieben (II IB IE BI BB BE EI EB EE); die neun Werte gibt es auch als Properties (II, IB, …, EE). a.Relate(b, pattern) prüft die Matrix gegen ein Muster aus neun Zeichen: T (nicht leer), F (leer), * (beliebig), 0, 1, 2 (genau diese Dimension). T*F**F*** ist zum Beispiel „within“.
Ein Muster lesen
Ein Muster hat neun Zeichen, eines für jedes Paar aus den drei Teilen von a und den drei Teilen von b. Die drei Teile einer Geometrie sind ihr Inneres (I), ihr Rand (B) und ihr Äußeres (E): bei einer Fläche das Innere, die Kante und der Rest der Ebene; bei einer Linie alles außer den beiden Endpunkten, die Endpunkte und der Rest; bei einem Punkt der Punkt selbst, nichts und der Rest. Die neun Positionen, Zeile für Zeile:
Inneres von b |
Rand von b |
Äußeres von b |
|
|---|---|---|---|
Inneres von a |
1. (II) |
2. (IB) |
3. (IE) |
Rand von a |
4. (BI) |
5. (BB) |
6. (BE) |
Äußeres von a |
7. (EI) |
8. (EB) |
9. (EE) |
Jedes Zeichen sagt, was die beiden Teile teilen:
| Zeichen | Bedeutet |
|---|---|
T |
sie teilen etwas (Punkte, eine Linie oder eine Fläche; die Dimension ist egal) |
F |
sie teilen nichts (leer) |
* |
egal |
0, 1, 2 |
sie teilen genau Punkte (0), eine Linie (1) oder eine Fläche (2) |
T und F sagen nicht, dass das Prädikat wahr oder falsch ist; das Prädikat ist wahr, wenn alle neun Positionen zu seinem Muster passen. Als Beispiel ist T*F**F*** das Muster von Within: T bei II, die Inneren teilen etwas; F bei IE, das Innere von a teilt nichts mit dem Äußeren von b; F bei BE, der Rand von a auch nicht; der Rest ist egal. In Worten: Die Inneren treffen sich, und nichts von a ragt aus b heraus. Die Matrix FF2101FF2 des Quadrats und seiner Kante weiter oben liest sich genauso: II F (die Inneren teilen nichts), IE 2 (das Innere des Quadrats teilt eine Fläche mit dem Äußeren der Kante), BI 1 (der Rand des Quadrats und das Innere der Kante teilen eine Linie: Die Kante liegt darauf), BB 0 (die Endpunkte der Kante berühren den Rand) und so weiter.
Die Prädikate
Alle Prädikate sind Extension-Methoden auf IGeometry2D:
| Prädikat | Bedeutung |
|---|---|
Intersects |
die Geometrien haben mindestens einen Punkt gemeinsam |
Disjoint |
die Geometrien haben keinen Punkt gemeinsam (FF*FF****) |
Contains(a, b) |
b liegt in a, und sie haben einen inneren Punkt gemeinsam (T*****FF*) |
Within(a, b) |
a liegt in b (T*F**F***) |
Covers(a, b) |
kein Punkt von b liegt außerhalb von a; Randpunkte zählen mit |
CoveredBy(a, b) |
kein Punkt von a liegt außerhalb von b; Randpunkte zählen mit |
Touches |
die Geometrien treffen sich nur in Randpunkten |
Crosses |
die Geometrien kreuzen sich (OGC; abhängig von den Dimensionen) |
Overlaps |
gleichdimensionale Geometrien überlappen sich teilweise |
EqualsTopo |
die Geometrien sind topologisch gleich (T*F**FFF*); falsch, wenn eine leer ist |
Contains gegenüber Covers ist der Unterschied, der die meisten überrascht: Ein Polygon enthält eine Linie auf seinem Rand nicht (die Linie hat keinen Punkt im Inneren), es überdeckt sie aber. Wer „liegt drin, der Rand zählt mit“ meint, nimmt Covers/CoveredBy.
Regeln, die für alle Prädikate gelten:
- Leere Geometrien. Ist eine Geometrie leer, ist nur
Disjointwahr; alle anderen Prädikate sind falsch, undRelateliefert eine Matrix nur ausF. - Flächen nach Even-Odd. Flächen folgen der Even-Odd-Regel (ADR 0003).
- Linienränder nach Mod-2. Die Endpunkte einer Linie sind ihr Rand, geschlossene Pfade haben keinen Rand, und bei einer Polylinie mit mehreren Pfaden zählt in einem Punkt nur eine ungerade Zahl von Pfadenden.
- Ungültige Eingaben werden deterministisch und ohne Exception behandelt, aber ohne Zusage, dass die Prädikate untereinander konsistent sind.
Die Situationen
Die Tabellen auf den Seiten der einzelnen Prädikate nutzen dieselben 27 Situationen. a ist die erste, b die zweite Geometrie; die Matrix ist a.Relate(b) (Die Schnittmatrix). Eine Zelle zeigt true, wo das Prädikat gilt.
| Situation | Matrix | Intersects | Disjoint | Contains | Within | Covers | CoveredBy | Touches | Crosses | Overlaps | EqualsTopo |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Ein Punkt in einer Fläche | 0FFFFF212 |
true | true | true | |||||||
| Ein Punkt auf dem Rand einer Fläche | F0FFFF212 |
true | true | true | |||||||
| Ein Punkt außerhalb einer Fläche | FF0FFF212 |
true | |||||||||
| Ein Punkt im Loch einer Fläche | FF0FFF212 |
true | |||||||||
| Ein Punkt auf einer Linie (nicht an ihrem Ende) | 0FFFFF102 |
true | true | true | |||||||
| Ein Punkt am Ende einer Linie | F0FFFF102 |
true | true | true | |||||||
| Ein Punkt an einem Knick (Stützpunkt) mitten in einer Linie | 0FFFFF102 |
true | true | true | |||||||
| Ein Punkt neben einer Linie | FF0FFF102 |
true | |||||||||
| Zwei gleiche Punkte | 0FFFFFFF2 |
true | true | true | true | true | true | ||||
| Zwei Linien, die sich kreuzen | 0F1FF0102 |
true | true | ||||||||
| Zwei Linien, die Ende an Ende liegen | FF1F00102 |
true | true | ||||||||
| Eine Linie, die auf einer anderen Linie endet (ein T) | FF10F0102 |
true | true | ||||||||
| Zwei Linien, die ein Stück zusammen laufen | 1010F0102 |
true | true | ||||||||
| Zwei gleiche Linien (eine umgekehrt) | 1FFF0FFF2 |
true | true | true | true | true | true | ||||
| Eine Linie in einer Fläche | 1FF0FF212 |
true | true | true | |||||||
| Eine Linie, die den Rand einer Fläche quert | 1010F0212 |
true | true | ||||||||
| Eine Linie entlang des Rands einer Fläche | F1FF0F212 |
true | true | true | |||||||
| Eine Linie außerhalb einer Fläche, die an ihrem Rand endet | FF1F00212 |
true | true | ||||||||
| Eine Linie außerhalb einer Fläche | FF1FF0212 |
true | |||||||||
| Eine kleine Fläche in einer großen | 2FF1FF212 |
true | true | true | |||||||
| Eine Fläche in einer anderen, die deren Rand von innen berührt | 2FF11F212 |
true | true | true | |||||||
| Zwei Flächen mit gemeinsamer Kante | FF2F11212 |
true | true | ||||||||
| Zwei Flächen, die sich in einer Ecke berühren | FF2F01212 |
true | true | ||||||||
| Zwei Flächen, die sich überlappen | 212111212 |
true | true | ||||||||
| Zwei gleiche Flächen (anderer Startpunkt und Umlaufsinn) | 2FFF1FFF2 |
true | true | true | true | true | true | ||||
| Zwei getrennte Flächen | FF2FF1212 |
true | |||||||||
| Eine Fläche im Loch einer anderen | FF2FF1212 |
true |
Die Geometrien
| Situation | a |
b |
|---|---|---|
| Ein Punkt in einer Fläche | POINT (5 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Ein Punkt auf dem Rand einer Fläche | POINT (10 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Ein Punkt außerhalb einer Fläche | POINT (15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Ein Punkt im Loch einer Fläche | POINT (5 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0), (4 4, 6 4, 6 6, 4 6, 4 4)) |
| Ein Punkt auf einer Linie (nicht an ihrem Ende) | POINT (5 0) |
LINESTRING (0 0, 10 0) |
| Ein Punkt am Ende einer Linie | POINT (0 0) |
LINESTRING (0 0, 10 0) |
| Ein Punkt an einem Knick (Stützpunkt) mitten in einer Linie | POINT (5 0) |
LINESTRING (0 0, 5 0, 5 5) |
| Ein Punkt neben einer Linie | POINT (5 1) |
LINESTRING (0 0, 10 0) |
| Zwei gleiche Punkte | POINT (1 1) |
POINT (1 1) |
| Zwei Linien, die sich kreuzen | LINESTRING (0 0, 10 10) |
LINESTRING (0 10, 10 0) |
| Zwei Linien, die Ende an Ende liegen | LINESTRING (0 0, 5 5) |
LINESTRING (5 5, 10 0) |
| Eine Linie, die auf einer anderen Linie endet (ein T) | LINESTRING (5 0, 5 5) |
LINESTRING (0 0, 10 0) |
| Zwei Linien, die ein Stück zusammen laufen | LINESTRING (0 0, 10 0) |
LINESTRING (5 0, 15 0) |
| Zwei gleiche Linien (eine umgekehrt) | LINESTRING (0 0, 10 0) |
LINESTRING (10 0, 0 0) |
| Eine Linie in einer Fläche | LINESTRING (2 2, 8 8) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine Linie, die den Rand einer Fläche quert | LINESTRING (5 5, 15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine Linie entlang des Rands einer Fläche | LINESTRING (0 0, 10 0) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine Linie außerhalb einer Fläche, die an ihrem Rand endet | LINESTRING (10 5, 15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine Linie außerhalb einer Fläche | LINESTRING (12 0, 12 10) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine kleine Fläche in einer großen | POLYGON ((2 2, 4 2, 4 4, 2 4, 2 2)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Eine Fläche in einer anderen, die deren Rand von innen berührt | POLYGON ((0 0, 5 0, 5 5, 0 5, 0 0)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Zwei Flächen mit gemeinsamer Kante | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 0, 20 0, 20 10, 10 10, 10 0)) |
| Zwei Flächen, die sich in einer Ecke berühren | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 10, 20 10, 20 20, 10 20, 10 10)) |
| Zwei Flächen, die sich überlappen | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((5 0, 15 0, 15 10, 5 10, 5 0)) |
| Zwei gleiche Flächen (anderer Startpunkt und Umlaufsinn) | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 0, 10 10, 0 10, 0 0, 10 0)) |
| Zwei getrennte Flächen | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((20 0, 30 0, 30 10, 20 10, 20 0)) |
| Eine Fläche im Loch einer anderen | POLYGON ((4.5 4.5, 5.5 4.5, 5.5 5.5, 4.5 5.5, 4.5 4.5)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0), (4 4, 6 4, 6 6, 4 6, 4 4)) |
Exaktheit gegenüber Overlays
Prädikate rechnen exakt auf den übergebenen Koordinaten. Overlays runden auf ein Gitter (Overlays, Füllregeln und das Gitter). Bei Beinahe-Berührungen unterhalb der Gitterweite kann a.Intersects(b) deshalb wahr und a.Intersection(b) leer sein.
Exaktheit in der Praxis, und die Alternativen mit Toleranz
Die Prädikate verlangen numerische Exaktheit: Intersects ist nur true, wenn die beiden Geometrien einen Punkt bis zum letzten Bit ihrer Koordinaten teilen. Das macht die Ergebnisse verlässlich und untereinander stimmig, und es ist, was NetTopologySuite und JTS tun. Bei gemessenen oder berechneten Daten ist es fast nie erfüllt: Eine Koordinate ist ein gerundeter double, ein Punkt, den Sie durch Klicken, Projizieren oder Rechnen auf eine Linie setzen, liegt etwa 4e-16 daneben, und eine gemeinsame Grenze zweier Flurstücke ist nur so genau wie die beiden Vermessungen. Ein Punkt auf einem Stützpunkt ist exakt, weil er genau dieselben Zahlen hat; ein Punkt auf einem Segment ist praktisch nie exakt.
Wenn „nah genug“ gemeint ist, und bei Vermessungsdaten ist es das, sagen Sie es mit einer Toleranz. Die Bibliothek hat keine globale Toleranz für die Prädikate; sie hat die Werkzeuge, um nach einer zu fragen:
double t = 0.01; // die Toleranz, in der Einheit Ihrer Koordinaten (hier 1 cm)
bool intersects = a.IsWithinDistance(b, t); // Intersects: näher als t
bool disjoint = !a.IsWithinDistance(b, t); // Disjoint: weiter als t
bool contains = a.Buffer(t).Contains(b); // Contains: b liegt in a, höchstens t über den Rand
bool within = b.Buffer(t).Contains(a); // Within
bool covers = a.Buffer(t).Covers(b); // Covers
bool coveredBy = b.Buffer(t).Covers(a); // CoveredBy
bool touches = a.IsWithinDistance(b, t) && !a.Buffer(-t).Intersects(b); // Touches (areas): sie treffen sich und überlappen um weniger als t
bool overlaps = a.Buffer(-t).Intersects(b.Buffer(-t)) // Overlaps (areas): sie überlappen um mehr als t,
&& !a.Buffer(t).Covers(b) && !b.Buffer(t).Covers(a); // und keines liegt im anderen
bool equal = a.HausdorffDistance(b) <= t; // EqualsTopo: no vertex of one is weiter als t from the other
| Prädikat | Mit Toleranz t |
Bedeutet |
|---|---|---|
Intersects |
a.IsWithinDistance(b, t) |
der Abstand ist höchstens t |
Disjoint |
!a.IsWithinDistance(b, t) |
der Abstand ist größer als t |
Contains(a, b) |
a.Buffer(t).Contains(b) |
b liegt in a oder ragt höchstens um t heraus |
Within(a, b) |
b.Buffer(t).Contains(a) |
a liegt in b oder ragt höchstens um t heraus |
Covers(a, b) |
a.Buffer(t).Covers(b) |
wie Contains, Randpunkte zählen |
CoveredBy(a, b) |
b.Buffer(t).Covers(a) |
wie Within, Randpunkte zählen |
Touches (Flächen) |
a.IsWithinDistance(b, t) && !a.Buffer(-t).Intersects(b) |
sie treffen sich und überlappen um weniger als t |
Overlaps (Flächen) |
a.Buffer(-t).Intersects(b.Buffer(-t)) && !a.Buffer(t).Covers(b) && !b.Buffer(t).Covers(a) |
sie überlappen um mehr als t, keine liegt in der anderen |
EqualsTopo |
a.HausdorffDistance(b) <= t |
kein Stützpunkt ist weiter als t von der anderen Geometrie entfernt (siehe unten) |
Crosses, Relate |
keine | siehe unten |
Anmerkungen zur Tabelle:
IsWithinDistancehört auf, sobald es die Antwort kennt, und prüft zuerst die Envelopes; es ist also billig. Für viele Abfragen gegen eine Geometrie nutzen SiePrepare()undprepared.IsWithinDistance(b, t). Keiner dieser Aufrufe verändertaoderb; die Buffer sind neue Geometrien.Bufferist der teure Teil der Alternativen. Für viele Tests gegen dasselbeaberechnen Siea.Buffer(t)(unda.Buffer(-t)) einmal und behalten es.Buffer(-t)schrumpft eine Fläche; das geht für Polygone, nicht für Linien oder Punkte,TouchesundOverlapsstehen also für Flächen. Für eine Linie oder einen Punkt nehmen Sie den Abstand: Sie berühren sich, wennIsWithinDistance(b, t).HausdorffDistanceist diskret (sie sieht Stützpunkte und, mit einemdensifyFractionunter 1, Punkte dazwischen) und eine untere Schranke; geben SiedensifyFractionan (etwa 0,1), wenn die Geometrien lange Segmente haben. Ein Stützpunkt auf einem Stützpunkt ist der Fall, den sie exakt entscheidet.CrossesundRelatehaben kein einfaches Gegenstück: Eine Kreuzung oder eine DE-9IM-Matrix ist eine Aussage über die Inneren, und „fast kreuzen“ hat keine einheitliche Bedeutung. Fragen Sie nach dem, was Sie meinen:IsWithinDistancefür „sie treffen sich“ undNearestPointsfür „wo“.- Oder zuerst fangen und dann exakt fragen (ADR 0046):
a.Touches(b.SnapTo(a, t, SnapMode.Vertices))verschiebt die Stützpunkte vonb, die näher alstanaliegen, aufaund fügt die Stützpunkte vonain die Segmente vonbein, sodass eine gemeinsame Grenze exakt wird. Das funktioniert für jedes Prädikat und fürRelate, behält die Bedeutung der exakten Prädikate und ist der Schritt, der auch den Overlays undCuthilft; es verändertbum bis zut. - Um die Daten exakt zu machen statt die Frage tolerant, runden Sie sie einmal beim Einlesen auf ein Gitter (
ReducePrecision(0.01)). Das macht Stützpunkte, die in einer Zelle liegen, identisch, was hilft, wo Geometrien an Stützpunkten zusammenstoßen, aber es hilft nicht bei einem Punkt mitten auf einem Segment (Maße und Konstruktionen).
Der Playground zeigt deshalb neben jedem Prädikat den Abstand, nennt darunter die Alternative mit Toleranz und sagt es, wenn ein false nur eine Rundungsdifferenz ist.
Wiederholte Prädikate: Prepare()
Wer viele Geometrien gegen dieselbe testet (etwa ein Polygon gegen tausende Punkte), bereitet sie einmal vor:
// a and b are the two polygons from the quick start.
// Several expensive predicates against the same geometry: prepare it once.
PreparedGeometry prepared = a.Prepare();
bool inside = prepared.Contains(Wkt.Read<IPolygon2D>("POLYGON((1 1, 2 1, 2 2, 1 2, 1 1))"));
// Full DE-9IM: matrix and pattern matching.
string matrix = a.Relate(b).ToString(); // "212101212"
Eine PreparedGeometry kopiert einen Schnappschuss der Koordinaten und baut daraus einen Segment-Index (und eine Punkt-in-Polygon-Struktur). Spätere Änderungen am Host-Objekt wirken nicht auf sie, was wichtig ist, weil Host-Geometrien veränderbar sind. Sie bietet Intersects, Disjoint, Contains, Covers, Within, CoveredBy und Touches, immer mit denselben Ergebnissen wie die nicht vorbereiteten Prädikate; schnelle Wege gibt es für Intersects/Disjoint und Punkt-in-Fläche, alles andere läuft über das exakte Relate. Eine PreparedGeometry ist nach dem Bauen thread-sicher (ADR 0024): einmal vorbereiten und zwischen Threads teilen. Sie beantwortet außerdem Distance, IsWithinDistance und NearestPoints gegen andere Geometrien, mit denselben Ergebnissen wie die unvorbereiteten Methoden (nur bei gleich nahen Paaren können die nächsten Punkte abweichen).