8000 Repair GEO_INTERSECTS (#14492) · arangodb/arangodb@4f05769 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4f05769

Browse files
neunhoefmaierlarsgnusi
authored
Repair GEO_INTERSECTS (#14492)
* Add bad tests. * Fix intersection bug with LngLatRect and Polygon. * Deduplicated code with intersectRectPolygon function. * Deduplicated code using intersectMultiPointsRegion. * Add more implementations, fix tests. * Add more tests with latlngrect and polygon. * Finishing touches. Make point/line and friends throw exceptions. * Avoid some memory allocations. * CHANGELOG. * Suggestions by gnusi. Co-authored-by: maierlars <lars@arangodb.com> Co-authored-by: gnusi <gnusi@arangodb.com>
1 parent 06a1544 commit 4f05769

File tree

4 files changed

+337
-56
lines changed

4 files changed

+337
-56
lines changed

‎CHANGELOG

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
devel
22
-----
33

4+
* Fixed various problems in GEO_INTERSECTS: wrong results, not implemented
5+
cases and numerically unstable behaviour. In particular, the case of
6+
the intersection of two polygons in which one is an S2LngLatRect
7+
is fixed (BTS-475).
8+
49
* Fixed ES-867 and ES-922: removed eslint from NPM packages descriptions and
510
updated netmask package to non-vulnerable version.
611

‎arangod/Aql/Functions.cpp

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1200,8 +1200,15 @@ AqlValue geoContainsIntersect(ExpressionContext* expressionContext,
12001200
return AqlValue(AqlValueHintNull());
12011201
}
12021202

1203-
bool result = contains ? outer.contains(&inner) : outer.intersects(&inner);
1204-
return AqlValue(AqlValueHintBool(result));
1203+
bool result;
1204+
try {
1205+
result = contains ? outer.contains(&inner) : outer.intersects(&inner);
1206+
return AqlValue(AqlValueHintBool(result));
1207+
} catch (arangodb::basics::Exception const& ex) {
1208+
res.reset(ex.code(), ex.what());
1209+
registerWarning(expressionContext, func, res);
1210+
return AqlValue(AqlValueHintBool(false));
1211+
}
12051212
}
12061213

12071214
static Result parseGeoPolygon(VPackSlice polygon, VPackBuilder& b) {

‎lib/Geo/ShapeContainer.cpp

Lines changed: 82 additions & 52 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,24 @@
5555
using namespace arangodb;
5656
using namespace arangodb::geo;
5757

58+
namespace {
59+
60+
S2Polygon latLngRectToPolygon(S2LatLngRect const* rect) {
61+
// Construct polygon from rect:
62+
std::vector<S2Point> v;
63+
v.reserve(5);
64+
v.emplace_back(rect->GetVertex(0).ToPoint());
65+
v.emplace_back(rect->GetVertex(1).ToPoint());
66+
v.emplace_back(rect->GetVertex(2).ToPoint());
67+
v.emplace_back(rect->GetVertex(3).ToPoint());
68+
v.emplace_back(rect->GetVertex(0).ToPoint());
69+
std::unique_ptr<S2Loop> loop;
70+
loop = std::make_unique<S2Loop>(std::move(v), S2Debug::DISABLE);
71+
return S2Polygon{std::move(loop), S2Debug::DISABLE};
72+
}
73+
74+
}
75+
5876
Result ShapeContainer::parseCoordinates(VPackSlice const& json, bool geoJson) {
5977
if (!json.isArray() || json.length() < 2) {
6078
return Result(TRI_ERROR_BAD_PARAMETER, "Invalid coordinate pair");
@@ -557,41 +575,57 @@ bool ShapeContainer::equals(ShapeContainer const* cc) const {
557575
bool ShapeContainer::intersects(S2Polyline const* other) const {
558576
switch (_type) {
559577
case ShapeContainer::Type::S2_POINT: {
560-
S2Point const& p = static_cast<S2PointRegion*>(_data)->point();
561-
// containment is only numerically defined on the endpoints
562-
for (int k = 0; k < other->num_vertices(); k++) {
563-
if (other->vertex(k) == p) {
564-
return true;
565-
}
566-
}
567-
return false;
578+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
579+
"The case GEO_INTERSECTS(<point>, <polyline>) is numerically instable and thus not supported.");
568580
}
569581
case ShapeContainer::Type::S2_POLYLINE: {
570582
S2Polyline const* ll = static_cast<S2Polyline const*>(_data);
571583
return ll->Intersects(other);
572584
}
573585
case ShapeContainer::Type::S2_LATLNGRECT: {
574-
S2LatLngRect const* rect = static_cast<S2LatLngRect const*>(_data);
575-
for (int k = 0; k < other->num_vertices(); k++) {
576-
if (rect->Contains(other->vertex(k))) {
577-
return true;
578-
}
579-
}
580-
return false;
586+
auto rectPoly = ::latLngRectToPolygon(static_cast<S2LatLngRect const*>(_data));
587+
auto cuts = rectPoly.IntersectWithPolyline(*other);
588+
return !cuts.empty();
581589
}
582590
case ShapeContainer::Type::S2_POLYGON: {
583591
S2Polygon const* poly = static_cast<S2Polygon const*>(_data);
584592
auto cuts = poly->IntersectWithPolyline(*other);
585593
return !cuts.empty();
586594
}
587595
case ShapeContainer::Type::S2_MULTIPOINT:
588-
case ShapeContainer::Type::S2_MULTIPOLYLINE:
596+
case ShapeContainer::Type::S2_MULTIPOLYLINE: {
597+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
598+
"The case GEO_INTERSECTS(<multipoint or multipolyline>, <polyline>) is not yet implemented.");
599+
}
589600
case ShapeContainer::Type::EMPTY:
590601
TRI_ASSERT(false);
591602
}
592603
return false;
593604
}
594605

606+
namespace {
607+
bool intersectRectPolygon(S2LatLngRect const* rect, S2Polygon const* poly) {
608+
if (rect->is_full()) {
609+
return true; // rectangle spans entire sphere
610+
} else if (rect->is_point()) {
611+
return poly->Contains(rect->lo().ToPoint()); // easy case
612+
} else if (!rect->Intersects(poly->GetRectBound())) {
613+
return false; // cheap rejection
614+
}
615+
auto rectPoly = ::latLngRectToPolygon(rect);
616+
return poly->Intersects(&rectPoly);
617+
}
618+
619+
bool insersectMultiPointsRegion(S2MultiPointRegion const* points, S2Region const* region) {
620+
for (int i = 0; i < points->num_points(); ++i) {
621+
if (region->Contains(points->point(i))) {
622+
return true;
623+
}
624+
}
625+
return false;
626+
}
627+
}
628+
595629
bool ShapeContainer::intersects(S2LatLngRect const* other) const {
596630
switch (_type) {
597631
case ShapeContainer::Type::S2_POINT: {
@@ -600,7 +634,10 @@ bool ShapeContainer::intersects(S2LatLngRect const* other) const {
600634
}
601635

602636
case ShapeContainer::Type::S2_POLYLINE: {
603-
return contains(other);
637+
auto rectPoly = ::latLngRectToPolygon(static_cast<S2LatLngRect const*>(other));
638+
S2Polyline const* self = static_cast<S2Polyline const*>(_data);
639+
auto cuts = rectPoly.IntersectWithPolyline(*self);
640+
return !cuts.empty();
604641
}
605642

606643
case ShapeContainer::Type::S2_LATLNGRECT: {
@@ -610,22 +647,17 @@ bool ShapeContainer::intersects(S2LatLngRect const* other) const {
610647

611648
case ShapeContainer::Type::S2_POLYGON: {
612649
S2Polygon const* self = static_cast<S2Polygon const*>(_data);
613-
if (other->is_full()) {
614-
return true; // rectangle spans entire sphere
615-
} else if (other->is_point()) {
616-
return self->Contains(other->lo().ToPoint()); // easy case
617-
} else if (!other->Intersects(self->GetRectBound())) {
618-
return false; // cheap rejection
619-
}
620-
// construct bounding polyline of rect
621-
S2Polyline rectBound({other->GetVertex(0), other->GetVertex(1),
622-
other->GetVertex(2), other->GetVertex(3)});
623-
return self->Intersects(rectBound);
650+
return intersectRectPolygon(other, self);
651+
}
652+
653+
case ShapeContainer::Type::S2_MULTIPOINT: {
654+
S2MultiPointRegion* self = static_cast<S2MultiPointRegion*>(_data);
655+
return insersectMultiPointsRegion(self, other);
624656
}
625657

626-
case ShapeContainer::Type::S2_MULTIPOINT:
627658
case ShapeContainer::Type::S2_MULTIPOLYLINE: {
628-
return contains(other); // same
659+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
660+
"The case GEO_INTERSECTS(<multiline>, <latlngrect>) is not yet implemented.");
629661
}
630662

631663
case ShapeContainer::Type::EMPTY:
@@ -641,31 +673,24 @@ bool ShapeContainer::intersects(S2Polygon const* other) const {
641673
return other->Contains(p);
642674
}
643675
case ShapeContainer::Type::S2_POLYLINE: {
644-
LOG_TOPIC("2cb3c", ERR, Logger::FIXME)
645-
<< "intersection with polyline is not well defined";
646-
return false; // numerically not well defined
676+
S2Polyline* line = static_cast<S2Polyline*>(_data);
677+
auto cuts = other->IntersectWithPolyline(*line);
678+
return !cuts.empty();
647679
}
648680
case ShapeContainer::Type::S2_LATLNGRECT: {
649681
S2LatLngRect const* self = static_cast<S2LatLngRect const*>(_data);
650-
if (self->is_full()) {
651-
return true; // rectangle spans entire sphere
652-
} else if (self->is_point()) {
653-
return other->Contains(self->lo().ToPoint()); // easy case
654-
} else if (!self->Intersects(other->GetRectBound())) {
655-
return false; // cheap rejection
656-
}
657-
// construct bounding polyline of rect
658-
S2Polyline rectBound({self->GetVertex(0), self->GetVertex(1),
659-
self->GetVertex(2), self->GetVertex(3)});
660-
return other->Intersects(rectBound);
682+
return intersectRectPolygon(self, other);
661683
}
662684
case ShapeContainer::Type::S2_POLYGON: {
663685
S2Polygon const* self = static_cast<S2Polygon const*>(_data);
664686
return self->Intersects(other);
665687
}
666-
case ShapeContainer::Type::EMPTY:
667688
case ShapeContainer::Type::S2_MULTIPOINT:
668-
case ShapeContainer::Type::S2_MULTIPOLYLINE:
689+
case ShapeContainer::Type::S2_MULTIPOLYLINE: {
690+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
691+
"The case GEO_INTERSECTS(<multipoint or multipolyline>, <polygon>) is not yet implemented.");
692+
}
693+
case ShapeContainer::Type::EMPTY:
669694
TRI_ASSERT(false);
670695
}
671696
return false;
@@ -674,6 +699,11 @@ bool ShapeContainer::intersects(S2Polygon const* other) const {
674699
bool ShapeContainer::intersects(ShapeContainer const* cc) const {
675700
switch (cc->_type) {
676701
case ShapeContainer::Type::S2_POINT: {
702+
if (_type == ShapeContainer::Type::S2_POLYLINE ||
703+
_type == ShapeContainer::Type::S2_MULTIPOLYLINE) {
704+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
705+
"The case GEO_INTERSECTS(<polyline>, <point>) is numerically instable and thus not supported.");
706+
}
677707
S2Point const& p = static_cast<S2PointRegion*>(cc->_data)->point();
678708
return _data->Contains(p); // same
679709
}
@@ -687,13 +717,13 @@ bool ShapeContainer::intersects(ShapeContainer const* cc) const {
687717
return intersects(static_cast<S2LatLngRect const*>(cc->_data));
688718
}
689719
case ShapeContainer::Type::S2_MULTIPOINT: {
690-
auto pts = static_cast<S2MultiPointRegion const*>(cc->_data);
691-
for (int k = 0; k < pts->num_points(); k++) {
692-
if (_data->Contains(pts->point(k))) {
693-
return true;
694-
}
720+
if (_type == ShapeContainer::Type::S2_POLYLINE ||
721+
_type == ShapeContainer::Type::S2_MULTIPOLYLINE) {
722+
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_NOT_IMPLEMENTED,
723+
"The case GEO_INTERSECTS(<polyline>, <multipoint>) is numerically instable and thus not supported.");
695724
}
696-
return false;
725+
auto pts = static_cast<S2MultiPointRegion const*>(cc->_data);
726+
return insersectMultiPointsRegion(pts, _data);
697727
}
698728
case ShapeContainer::Type::S2_MULTIPOLYLINE: {
699729
auto lines = static_cast<S2MultiPolyline const*>(cc->_data);

0 commit comments

Comments
 (0)
0