Query intersection of an edge for loops within loops

[dm356]

Hello. I am trying to set up a Contains-like query for an S2ShapeIndex containing loops that intersect one another. I'm encountering an issue when I query an edge that matches a loop edge that is fully contained within another loop. If I run the following:

  auto p1_1 = S2Point(0, 0, 1e5).Normalize();
  auto p1_2 = S2Point(100, 0, 1e5).Normalize();
  auto p1_3 = S2Point(100, 100, 1e5).Normalize();
  auto p1_4 = S2Point(0, 100, 1e5).Normalize();

  auto loop1 = std::make_unique<S2Loop>(std::vector<S2Point>{p1_1, p1_2, p1_3, p1_4});
  loop1->Normalize();

  auto p2_1 = S2Point(25, 25, 1e5).Normalize();
  auto p2_2 = S2Point(75, 25, 1e5).Normalize();
  auto p2_3 = S2Point(75, 200, 1e5).Normalize();
  auto p2_4 = S2Point(25, 200, 1e5).Normalize();

  auto loop2 = std::make_unique<S2Loop>(std::vector<S2Point>{p2_1, p2_2, p2_3, p2_4});
  loop2->Normalize();

  MutableS2ShapeIndex index;
  index.Add(std::make_unique<S2Loop::OwningShape>(std::move(loop1)));
  index.Add(std::make_unique<S2Loop::OwningShape>(std::move(loop2)));

  S2BooleanOperation::Options options;
  options.set_polygon_model(S2BooleanOperation::PolygonModel::OPEN);
  options.set_polyline_model(S2BooleanOperation::PolylineModel::CLOSED);

  S2Polyline line({p2_1, p2_2});
  MutableS2ShapeIndex line_index;
  line_index.Add(std::make_unique<S2Polyline::Shape>(&line));

  S2BooleanOperation::IsEmpty(S2BooleanOperation::OpType::INTERSECTION, line_index, index, options);

I get the following trace:

WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
F0000 00:00:1719550241.292658  321744 s2boolean_operation.cc:1613] Check failed: MakeS2ContainsPointQuery(&it->b_index()).Contains(a.v1) == inside_ ^ invert_b_ (1 vs. 0) 
*** Check failure stack trace: ***
    @     0x7c4111a0b50d  absl::lts_20230802::log_internal::LogMessage::PrepareToDie()
    @     0x7c4111a0b585  absl::lts_20230802::log_internal::LogMessage::SendToLog()
    @     0x7c4111a0afb9  absl::lts_20230802::log_internal::LogMessage::Flush()
    @     0x7c4111a0b890  absl::lts_20230802::log_internal::LogMessageFatal::~LogMessageFatal()
    @     0x7c4111870bbd  S2BooleanOperation::Impl::CrossingProcessor::ProcessEdge1()
    @     0x7c411187034c  S2BooleanOperation::Impl::CrossingProcessor::ProcessEdge()
    @     0x7c4111872c66  S2BooleanOperation::Impl::AddBoundary()
    @     0x7c4111873d80  S2BooleanOperation::Impl::AddBoundaryPair()
    @     0x7c4111874032  S2BooleanOperation::Impl::BuildOpType()
    @     0x7c411187511c  S2BooleanOperation::Impl::DoBuild()
    @     0x7c411187543d  S2BooleanOperation::Impl::Build()
    @     0x7c4111875e73  S2BooleanOperation::Build()
    @     0x7c4111875f55  S2BooleanOperation::IsEmpty()

Is there another way I should be doing this check, or is there an issue with assumptions in the algorithm?

[smcallis]

This is reproducible internally too, I'm investigating.

…

On Thu, Jun 27, 2024 at 11:03 PM dm356 ***@***.***> wrote: Hello. I am trying to set up a Contains-like query for an S2ShapeIndex containing loops that intersect one another. I'm encountering an issue when I query an edge that matches a loop edge that is fully contained within another loop. If I run the following: auto p1_1 = S2Point(0, 0, 1e5).Normalize(); auto p1_2 = S2Point(100, 0, 1e5).Normalize(); auto p1_3 = S2Point(100, 100, 1e5).Normalize(); auto p1_4 = S2Point(0, 100, 1e5).Normalize(); auto loop1 = std::make_unique<S2Loop>(std::vector<S2Point>{p1_1, p1_2, p1_3, p1_4}); loop1->Normalize(); auto p2_1 = S2Point(25, 25, 1e5).Normalize(); auto p2_2 = S2Point(75, 25, 1e5).Normalize(); auto p2_3 = S2Point(75, 200, 1e5).Normalize(); auto p2_4 = S2Point(25, 200, 1e5).Normalize(); auto loop2 = std::make_unique<S2Loop>(std::vector<S2Point>{p2_1, p2_2, p2_3, p2_4}); loop2->Normalize(); MutableS2ShapeIndex index; index.Add(std::make_unique<S2Loop::OwningShape>(std::move(loop1))); index.Add(std::make_unique<S2Loop::OwningShape>(std::move(loop2))); S2BooleanOperation::Options options; options.set_polygon_model(S2BooleanOperation::PolygonModel::OPEN); options.set_polyline_model(S2BooleanOperation::PolylineModel::CLOSED); S2Polyline line({p2_1, p2_2}); MutableS2ShapeIndex line_index; line_index.Add(std::make_unique<S2Polyline::Shape>(&line)); S2BooleanOperation::IsEmpty(S2BooleanOperation::OpType::INTERSECTION, line_index, index, options); I get the following trace: WARNING: All log messages before absl::InitializeLog() is called are written to STDERR F0000 00:00:1719550241.292658 321744 s2boolean_operation.cc:1613] Check failed: MakeS2ContainsPointQuery(&it->b_index()).Contains(a.v1) == inside_ ^ invert_b_ (1 vs. 0) *** Check failure stack trace: *** @ 0x7c4111a0b50d absl::lts_20230802::log_internal::LogMessage::PrepareToDie() @ 0x7c4111a0b585 absl::lts_20230802::log_internal::LogMessage::SendToLog() @ 0x7c4111a0afb9 absl::lts_20230802::log_internal::LogMessage::Flush() @ 0x7c4111a0b890 absl::lts_20230802::log_internal::LogMessageFatal::~LogMessageFatal() @ 0x7c4111870bbd S2BooleanOperation::Impl::CrossingProcessor::ProcessEdge1() @ 0x7c411187034c S2BooleanOperation::Impl::CrossingProcessor::ProcessEdge() @ 0x7c4111872c66 S2BooleanOperation::Impl::AddBoundary() @ 0x7c4111873d80 S2BooleanOperation::Impl::AddBoundaryPair() @ 0x7c4111874032 S2BooleanOperation::Impl::BuildOpType() @ 0x7c411187511c S2BooleanOperation::Impl::DoBuild() @ 0x7c411187543d S2BooleanOperation::Impl::Build() @ 0x7c4111875e73 S2BooleanOperation::Build() @ 0x7c4111875f55 S2BooleanOperation::IsEmpty() Is there another way I should be doing this check, or is there an issue with assumptions in the algorithm? — Reply to this email directly, view it on GitHub <#368>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGEMKUYY3AZV5WKW5T3GHLZJTVDTAVCNFSM6AAAAABKBESRA2VHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZWHA3TEMBZHE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[smcallis]

The geometry is very close to the pole, but it looks fine otherwise:

[smcallis]

My mistake, this geometry actually isn't valid for S2BooleanOperation. It requires the index to represent a single valid S2Shape. You can see the requirements here. If I move the second rectangle so it doesn't overlap the first then it works fine.

[dm356]

Ok, so I need to do the union first. That's what I thought to do anyway. Thanks for confirming.