0

I am attempting to find the intersections of many polygons_with_holes to check the topology of a map. However, when using the CGAL::intersection() defined here (under 2D Regularized Boolean Set-Operations), the run time for one check exceeds 1 minute, sometimes reaching close to 2 minutes. I have about 60-70 polygons with holes, with a total of 584697 vertices. I check whether their bounding boxes overlap before checking whether they intersect (I isolated the bounding box check, and that did not take long), but that still did not speed it up much. Is there any way I could get the runtime down to a couple seconds? I'm using Epick as my kernel. This is the code I have:

  // Comparing polygons pair-wise and calculating intersections, if any.
  for (size_t i = 0; i < all_pgwhs_in_inset.size(); ++i) {
    const Polygon_with_holes pgnwh1 = all_pgwhs_in_inset[i];
    const Bbox pgnwh1_bb = pgnwh1.bbox();
    for (size_t j = i + 1; j < all_pgwhs_in_inset.size(); ++j) {
      const Polygon_with_holes pgnwh2 = all_pgwhs_in_inset[j];
      const Bbox pgnwh2_bb = pgnwh2.bbox();

      // Calculating intersections only if bounding boxes overlap.
      // For condition, look at:
      // https://stackoverflow.com/questions/306316/determine-if-
      // two-rectangles-overlap-each-other
      if (pgnwh1_bb.xmin() < pgnwh2_bb.xmax()
          && pgnwh1_bb.xmax() > pgnwh2_bb.xmin()
          && pgnwh1_bb.ymin() < pgnwh2_bb.ymax()
          && pgnwh2_bb.ymax() > pgnwh1_bb.ymin()) {
        unsigned int size = intersections.size();
        CGAL::intersection(pgnwh1, pgnwh2, std::back_inserter(intersections));
      }
    }
  }

This is the kind of data I am dealing with: enter image description here

Finally, I noticed that the function recognises and adds the entire polygon with holes as an intersection; when would this be the case and why would it happen? In these cases, I can not find any intersections using tools like https://mapshaper.org. Thus, are these indicating something else? Some of the added 'intersections' seem to be the exact same as the original polygon with holes.

adisidev
  • 162
  • 1
  • 15
  • Another interesting thought I had was that CGAL simplification of polygons with shared boundaries works quite fast. As a side effect, the simplification adds points of intersections to polygons. Thus, implicitly the simplification algorithms seems to calculate intersections quite fast. Instead of polygon areas, I'd also be okay with intersection Points; is there any CGAL algorithm that can help me with this (apart from using Simplification as a stop-gap measure)? – adisidev Jan 07 '22 at 12:17
  • If an entire polygon is the result, then it is completely overlapping with the other polygon. Please verify that this is the case. If this is not the case, then there is an issue and you should report it. When you report, please provide an entire program and data that can be used to used to reproduce. This would also help here, because it will make clear which Kernel you are using, for example. – Efi Fogel Jan 08 '22 at 11:11
  • Does this map show the individual polygons that you are intersecting ? If yes, why do you do that (prefectures do not overlap, usually) ? –  Jan 10 '22 at 10:55
  • 1
    A suggestion to speed everything up - use references more. For example, use `auto const& pgnwh1 = all_pgwhs_in_inset[i]` - this will allow you to avoid calling the copy constructor. – HEKTO Jan 11 '22 at 22:09
  • Indeed @EfiFogel, it is not the case that the polygons overlap. I will report the issue; would the best place to do that be their GitHub repository? – adisidev Jan 12 '22 at 14:37
  • Thank you for the suggestion @HEKTO, I will try that and post updates here – adisidev Jan 12 '22 at 14:37
  • @YvesDaoust this map is the regular map of Japan - it was just to give an example of the kind of polygons I am working with. – adisidev Jan 12 '22 at 14:37
  • So let me conclude that it is a bad example. –  Jan 12 '22 at 14:46
  • Yes, the GitHub repository is the place. – Efi Fogel Jan 15 '22 at 11:00
  • @YvesDaoust, the algorithm I run on the map manipulates the borders such that intersections come up. However, regardless of whether the map has intersections or not, the main issue I have is not the intersections not being displayed; rather, it is the slowness of the algorithm, which is relevant on maps with and without intersections (for instance, for topology checks). – adisidev Jan 15 '22 at 12:24

0 Answers0