GEOS  3.13.1
RelatePredicate.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (c) 2024 Martin Davis
7  * Copyright (C) 2024 Paul Ramsey <pramsey@cleverelephant.ca>
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Public Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************/
15 
16 #pragma once
17 
18 #include <geos/geom/Location.h>
19 #include <geos/operation/relateng/BasicPredicate.h>
20 #include <geos/operation/relateng/IMPatternMatcher.h>
21 #include <geos/operation/relateng/IMPredicate.h>
22 #include <geos/operation/relateng/RelateGeometry.h>
23 #include <geos/geom/Envelope.h>
24 #include <geos/export.h>
25 
26 
29 
30 
31 namespace geos { // geos.
32 namespace operation { // geos.operation.
33 namespace relateng { // geos.operation.relateng
34 
35 
36 class GEOS_DLL RelatePredicate {
37 
38 public:
39 
40 /************************************************************************
41  *
42  * Creates a predicate to determine whether two geometries intersect.
43  *
44  * The intersects predicate has the following equivalent definitions:
45  *
46  * * The two geometries have at least one point in common
47  * * The DE-9IM Intersection Matrix for the two geometries matches
48  * at least one of the patterns
49  *
50  * [T********]
51  * [*T*******]
52  * [***T*****]
53  * [****T****]
54  *
55  * disjoint() = false
56  * (intersects is the inverse of disjoint)
57  *
58  * @return the predicate instance
59  *
60  * @see disjoint()
61  */
62 class IntersectsPredicate : public BasicPredicate {
63 
64 public:
65 
66  std::string name() const override {
67  return std::string("intersects");
68  }
69 
70  bool requireSelfNoding() const override {
71  //-- self-noding is not required to check for a simple interaction
72  return false;
73  }
74 
75  bool requireExteriorCheck(bool isSourceA) const override {
76  (void)isSourceA;
77  //-- intersects only requires testing interaction
78  return false;
79  }
80 
81  void init(const Envelope& envA, const Envelope& envB) override {
82  require(envA.intersects(envB));
83  }
84 
85  void updateDimension(Location locA, Location locB, int dimension) override {
86  (void)dimension;
87  setValueIf(true, isIntersection(locA, locB));
88  }
89 
90  void finish() override {
91  //-- if no intersecting locations were found
92  setValue(false);
93  }
94 
95 };
96 
97 static std::unique_ptr<BasicPredicate> intersects();
98 
99 /************************************************************************
100  *
101  * Creates a predicate to determine whether two geometries are disjoint.
102  *
103  * The disjoint predicate has the following equivalent definitions:
104  *
105  * * The two geometries have no point in common
106  * * The DE-9IM Intersection Matrix for the two geometries matches
107  * [FF*FF****]
108  * * intersects() = false
109  * (disjoint is the inverse of intersects)
110  *
111  * @return the predicate instance
112  *
113  * @see intersects()
114  */
115 class DisjointPredicate : public BasicPredicate {
116 
117  std::string name() const override {
118  return std::string("disjoint");
119  }
120 
121  bool requireSelfNoding() const override {
122  //-- self-noding is not required to check for a simple interaction
123  return false;
124  }
125 
126  bool requireInteraction() const override {
127  //-- ensure entire matrix is computed
128  return false;
129  }
130 
131  bool requireExteriorCheck(bool isSourceA) const override {
132  (void)isSourceA;
133  //-- intersects only requires testing interaction
134  return false;
135  }
136 
137  void init(const Envelope& envA, const Envelope& envB) override {
138  setValueIf(true, envA.disjoint(envB));
139  }
140 
141  void updateDimension(Location locA, Location locB, int dimension) override {
142  (void)dimension;
143  setValueIf(false, isIntersection(locA, locB));
144  }
145 
146  void finish() override {
147  //-- if no intersecting locations were found
148  setValue(true);
149  }
150 };
151 
152 static std::unique_ptr<BasicPredicate> disjoint();
153 
154 /************************************************************************
155  * Creates a predicate to determine whether a geometry contains another geometry.
156  *
157  * The contains predicate has the following equivalent definitions:
158  *
159  * * Every point of the other geometry is a point of this geometry,
160  * and the interiors of the two geometries have at least one point in common.
161  * * The DE-9IM Intersection Matrix for the two geometries matches
162  * the pattern
163  * [T*****FF*]
164  * * within(B, A) = true
165  * (contains is the converse of within)
166  *
167  * An implication of the definition is that "Geometries do not
168  * contain their boundary". In other words, if a geometry A is a subset of
169  * the points in the boundary of a geometry B, B.contains(A) = false.
170  * (As a concrete example, take A to be a LineString which lies in the boundary of a Polygon B.)
171  * For a predicate with similar behavior but avoiding
172  * this subtle limitation, see covers().
173  *
174  * @return the predicate instance
175  *
176  * @see within()
177  */
178 class ContainsPredicate : public IMPredicate {
179 
180  std::string name() const override {
181  return std::string("contains");
182  }
183 
184  bool requireCovers(bool isSourceA) override {
185  return isSourceA == RelateGeometry::GEOM_A;
186  }
187 
188  bool requireExteriorCheck(bool isSourceA) const override {
189  //-- only need to check B against Exterior of A
190  return isSourceA == RelateGeometry::GEOM_B;
191  }
192 
193  void init(int _dimA, int _dimB) override {
194  IMPredicate::init(_dimA, _dimB);
195  require(isDimsCompatibleWithCovers(dimA, dimB));
196  }
197 
198  void init(const Envelope& envA, const Envelope& envB) override {
199  BasicPredicate::requireCovers(envA, envB);
200  }
201 
202  bool isDetermined() const override {
203  return intersectsExteriorOf(RelateGeometry::GEOM_A);
204  }
205 
206  bool valueIM() override {
207  return intMatrix.isContains();
208  }
209 };
210 
211 static std::unique_ptr<IMPredicate> contains();
212 
213 
214 
215 /************************************************************************
216  * Creates a predicate to determine whether a geometry is within another geometry.
217  *
218  * The within predicate has the following equivalent definitions:
219  *
220  * * Every point of this geometry is a point of the other geometry,
221  * and the interiors of the two geometries have at least one point in common.
222  * * The DE-9IM Intersection Matrix for the two geometries matches
223  * [T*F**F***]
224  * * contains(B, A) = true
225  * (within is the converse of contains())
226  *
227  * An implication of the definition is that
228  * "The boundary of a Geometry is not within the Geometry".
229  * In other words, if a geometry A is a subset of
230  * the points in the boundary of a geometry B, within(B, A) = false
231  * (As a concrete example, take A to be a LineString which lies in the boundary of a Polygon B.)
232  * For a predicate with similar behavior but avoiding
233  * this subtle limitation, see coveredimBy().
234  *
235  * @return the predicate instance
236  *
237  * @see #contains()
238  */
239 class WithinPredicate : public IMPredicate {
240 
241  std::string name() const override {
242  return std::string("within");
243  }
244 
245  bool requireCovers(bool isSourceA) override {
246  return isSourceA == RelateGeometry::GEOM_B;
247  }
248 
249  bool requireExteriorCheck(bool isSourceA) const override {
250  //-- only need to check B against Exterior of A
251  return isSourceA == RelateGeometry::GEOM_A;
252  }
253 
254  void init(int _dimA, int _dimB) override {
255  IMPredicate::init(_dimA, _dimB);
256  require(isDimsCompatibleWithCovers(dimB, dimA));
257  }
258 
259  void init(const Envelope& envA, const Envelope& envB) override {
260  BasicPredicate::requireCovers(envB, envA);
261  }
262 
263  bool isDetermined() const override {
264  return intersectsExteriorOf(RelateGeometry::GEOM_B);
265  }
266 
267  bool valueIM() override {
268  return intMatrix.isWithin();
269  }
270 };
271 
272 static std::unique_ptr<IMPredicate> within();
273 
274 
275 
276 /************************************************************************
277  * Creates a predicate to determine whether a geometry covers another geometry.
278  *
279  * The covers predicate has the following equivalent definitions:
280  *
281  * Every point of the other geometry is a point of this geometry.
282  * The DE-9IM Intersection Matrix for the two geometries matches
283  * at least one of the following patterns:
284  *
285  * * [T*****FF*]
286  * * [*T****FF*]
287  * * [***T**FF*]
288  * * [****T*FF*]
289  *
290  * coveredimBy(b, a) = true
291  * (covers is the converse of coveredimBy())
292  *
293  * If either geometry is empty, the value of this predicate is false.
294  *
295  * This predicate is similar to contains(),
296  * but is more inclusive (i.e. returns true for more cases).
297  * In particular, unlike contains it does not distinguish between
298  * points in the boundary and in the interior of geometries.
299  * For most cases, covers should be used in preference to contains.
300  * As an added benefit, covers is more amenable to optimization,
301  * and hence should be more performant.
302  *
303  * @return the predicate instance
304  *
305  * @see #coveredimBy()
306  */
307 class CoversPredicate : public IMPredicate {
308 
309  std::string name() const override {
310  return std::string("covers");
311  }
312 
313  bool requireCovers(bool isSourceA) override {
314  return isSourceA == RelateGeometry::GEOM_A;
315  }
316 
317  bool requireExteriorCheck(bool isSourceA) const override {
318  //-- only need to check B against Exterior of A
319  return isSourceA == RelateGeometry::GEOM_B;
320  }
321 
322  void init(int _dimA, int _dimB) override {
323  IMPredicate::init(_dimA, _dimB);
324  require(isDimsCompatibleWithCovers(dimA, dimB));
325  }
326 
327  void init(const Envelope& envA, const Envelope& envB) override {
328  BasicPredicate::requireCovers(envA, envB);
329 
330  }
331 
332  bool isDetermined() const override {
333  return intersectsExteriorOf(RelateGeometry::GEOM_A);
334  }
335 
336  bool valueIM() override {
337  return intMatrix.isCovers();
338  }
339 };
340 
341 static std::unique_ptr<IMPredicate> covers();
342 
343 
344 /************************************************************************
345 * Creates a predicate to determine whether a geometry is covered
346 * by another geometry.
347 *
348 * The coveredimBy predicate has the following equivalent definitions:
349 *
350 * Every point of this geometry is a point of the other geometry.
351 * The DE-9IM Intersection Matrix for the two geometries matches
352 * at least one of the following patterns:
353 *
354 * [T*F**F***]
355 * [*TF**F***]
356 * [**FT*F***]
357 * [**F*TF***]
358 *
359 * covers(B, A) = true
360 * (coveredimBy is the converse of covers())
361 *
362 * If either geometry is empty, the value of this predicate is false.
363 *
364 * This predicate is similar to within(),
365 * but is more inclusive (i.e. returns true for more cases).
366 *
367 * @return the predicate instance
368 *
369 * @see #covers()
370 */
371 class CoveredByPredicate : public IMPredicate {
372 
373  std::string name() const override {
374  return std::string("coveredBy");
375  }
376 
377  bool requireCovers(bool isSourceA) override {
378  return isSourceA == RelateGeometry::GEOM_B;
379  }
380 
381  bool requireExteriorCheck(bool isSourceA) const override {
382  //-- only need to check B against Exterior of A
383  return isSourceA == RelateGeometry::GEOM_A;
384  }
385 
386  void init(int _dimA, int _dimB) override {
387  IMPredicate::init(_dimA, _dimB);
388  require(isDimsCompatibleWithCovers(dimB, dimA));
389  }
390 
391  void init(const Envelope& envA, const Envelope& envB) override {
392  BasicPredicate::requireCovers(envB, envA);
393  }
394 
395  bool isDetermined() const override {
396  return intersectsExteriorOf(RelateGeometry::GEOM_B);
397  }
398 
399  bool valueIM() override {
400  return intMatrix.isCoveredBy();
401  }
402 
403 };
404 
405 static std::unique_ptr<IMPredicate> coveredBy();
406 
407 
408 /************************************************************************
409 * Creates a predicate to determine whether a geometry crosses another geometry.
410 *
411 * The crosses predicate has the following equivalent definitions:
412 *
413 * The geometries have some but not all interior points in common.
414 * The DE-9IM Intersection Matrix for the two geometries matches
415 * one of the following patterns:
416 *
417 * [T*T******] (for P/L, P/A, and L/A cases)
418 * [T*****T**] (for L/P, A/P, and A/L cases)
419 * [0********] (for L/L cases)
420 *
421 *
422 * For the A/A and P/P cases this predicate returns false.
423 *
424 * The SFS defined this predicate only for P/L, P/A, L/L, and L/A cases.
425 * To make the relation symmetric
426 * JTS extends the definition to apply to L/P, A/P and A/L cases as well.
427 *
428 * @return the predicate instance
429 */
430 
431 class CrossesPredicate : public IMPredicate {
432 
433  std::string name() const override {
434  return std::string("crosses");
435  }
436 
437  void init(int _dimA, int _dimB) override {
438  IMPredicate::init(_dimA, _dimB);
439  bool isBothPointsOrAreas =
440  (dimA == Dimension::P && dimB == Dimension::P) ||
441  (dimA == Dimension::A && dimB == Dimension::A);
442  require(!isBothPointsOrAreas);
443  }
444 
445  bool isDetermined() const override {
446  if (dimA == Dimension::L && dimB == Dimension::L) {
447  //-- L/L interaction can only be dim = P
448  if (getDimension(Location::INTERIOR, Location::INTERIOR) > Dimension::P)
449  return true;
450  }
451  else if (dimA < dimB) {
452  if (isIntersects(Location::INTERIOR, Location::INTERIOR) &&
453  isIntersects(Location::INTERIOR, Location::EXTERIOR)) {
454  return true;
455  }
456  }
457  else if (dimA > dimB) {
458  if (isIntersects(Location::INTERIOR, Location::INTERIOR) &&
459  isIntersects(Location::EXTERIOR, Location::INTERIOR)) {
460  return true;
461  }
462  }
463  return false;
464  }
465 
466  bool valueIM() override {
467  return intMatrix.isCrosses(dimA, dimB);
468  }
469 };
470 
471 static std::unique_ptr<IMPredicate> crosses();
472 
473 
474 /************************************************************************
475 * Creates a predicate to determine whether two geometries are
476 * topologically equal.
477 *
478 * The equals predicate has the following equivalent definitions:
479 *
480 * The two geometries have at least one point in common,
481 * and no point of either geometry lies in the exterior of the other geometry.
482 * The DE-9IM Intersection Matrix for the two geometries matches
483 * the pattern T*F**FFF*
484 *
485 * @return the predicate instance
486 */
487 class EqualsTopoPredicate : public IMPredicate {
488 
489  std::string name() const override {
490  return std::string("equals");
491  }
492 
493  bool requireInteraction() const override {
494  //-- allow EMPTY = EMPTY
495  return false;
496  };
497 
498  void init(int _dimA, int _dimB) override {
499  IMPredicate::init(_dimA, _dimB);
500  //-- don't require equal dims, because EMPTY = EMPTY for all dims
501  }
502 
503  void init(const Envelope& envA, const Envelope& envB) override {
504  //-- handle EMPTY = EMPTY cases
505  setValueIf(true, envA.isNull() && envB.isNull());
506 
507  require(envA.equals(&envB));
508  }
509 
510  bool isDetermined() const override {
511  bool isEitherExteriorIntersects =
512  isIntersects(Location::INTERIOR, Location::EXTERIOR) ||
513  isIntersects(Location::BOUNDARY, Location::EXTERIOR) ||
514  isIntersects(Location::EXTERIOR, Location::INTERIOR) ||
515  isIntersects(Location::EXTERIOR, Location::BOUNDARY);
516 
517  return isEitherExteriorIntersects;
518  }
519 
520  bool valueIM() override {
521  return intMatrix.isEquals(dimA, dimB);
522  }
523 
524 };
525 
526 static std::unique_ptr<IMPredicate> equalsTopo();
527 
528 
529 /************************************************************************
530  * Creates a predicate to determine whether a geometry overlaps another geometry.
531  *
532  * The overlaps predicate has the following equivalent definitions:
533  *
534  * The geometries have at least one point each not shared by the other
535  * (or equivalently neither covers the other),
536  * they have the same dimension,
537  * and the intersection of the interiors of the two geometries has
538  * the same dimension as the geometries themselves.
539  * The DE-9IM Intersection Matrix for the two geometries matches
540  * [T*T***T**] (for P/P and A/A cases)
541  * or [1*T***T**] (for L/L cases)
542  *
543  * If the geometries are of different dimension this predicate returns false.
544  * This predicate is symmetric.
545  *
546  * @return the predicate instance
547  */
548 class OverlapsPredicate : public IMPredicate {
549 
550  std::string name() const override {
551  return std::string("overlaps");
552  }
553 
554  void init(int _dimA, int _dimB) override {
555  IMPredicate::init(_dimA, _dimB);
556  require(dimA == dimB);
557  }
558 
559  bool isDetermined() const override {
560  if (dimA == Dimension::A || dimA == Dimension::P) {
561  if (isIntersects(Location::INTERIOR, Location::INTERIOR) &&
562  isIntersects(Location::INTERIOR, Location::EXTERIOR) &&
563  isIntersects(Location::EXTERIOR, Location::INTERIOR))
564  return true;
565  }
566  if (dimA == Dimension::L) {
567  if (isDimension(Location::INTERIOR, Location::INTERIOR, Dimension::L) &&
568  isIntersects(Location::INTERIOR, Location::EXTERIOR) &&
569  isIntersects(Location::EXTERIOR, Location::INTERIOR))
570  return true;
571  }
572  return false;
573  }
574 
575  bool valueIM() override {
576  return intMatrix.isOverlaps(dimA, dimB);
577  }
578 };
579 
580 static std::unique_ptr<IMPredicate> overlaps();
581 
582 
583 
584 
585 
586 /************************************************************************
587 * Creates a predicate to determine whether a geometry touches another geometry.
588 *
589 * The touches predicate has the following equivalent definitions:
590 *
591 * The geometries have at least one point in common,
592 * but their interiors do not intersect.
593 * The DE-9IM Intersection Matrix for the two geometries matches
594 * at least one of the following patterns
595 *
596 * [FT*******]
597 * [F**T*****]
598 * [F***T****]
599 *
600 *
601 * If both geometries have dimension 0, the predicate returns false,
602 * since points have only interiors.
603 * This predicate is symmetric.
604 *
605 * @return the predicate instance
606 */
607 class TouchesPredicate : public IMPredicate {
608 
609  std::string name() const override {
610  return std::string("touches");
611  }
612 
613  void init(int _dimA, int _dimB) override {
614  IMPredicate::init(_dimA, _dimB);
615  bool isBothPoints = (dimA == 0 && dimB == 0);
616  require(! isBothPoints);
617  }
618 
619  bool isDetermined() const override {
620  bool isInteriorsIntersects = isIntersects(Location::INTERIOR, Location::INTERIOR);
621  return isInteriorsIntersects;
622  }
623 
624  bool valueIM() override {
625  return intMatrix.isTouches(dimA, dimB);
626  }
627 };
628 
629 static std::unique_ptr<IMPredicate> touches();
630 
639 static std::unique_ptr<TopologyPredicate> matches(const std::string& imPattern)
640 {
641  return std::unique_ptr<TopologyPredicate>(new IMPatternMatcher(imPattern));
642 }
643 
644 
645 
646 }; // !RelatePredicate
647 
648 
649 } // namespace geos.operation.relateng
650 } // namespace geos.operation
651 } // namespace geos
652 
@ A
Dimension value of a surface (2).
Definition: Dimension.h:46
@ L
Dimension value of a curve (1).
Definition: Dimension.h:43
@ P
Dimension value of a point (0).
Definition: Dimension.h:40
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:59
bool equals(const Envelope *other) const
Returns true if the Envelope other spatially equals this Envelope.
static bool intersects(const CoordinateXY &p1, const CoordinateXY &p2, const CoordinateXY &q)
Test the point q to see whether it intersects the Envelope defined by p1-p2.
bool isNull(void) const
Returns true if this Envelope is a "null" envelope.
Definition: Envelope.h:252
bool disjoint(const Envelope &other) const
Definition: Envelope.h:596
Location
Constants representing the location of a point relative to a geometry.
Definition: Location.h:32
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25