Incorrect Hierarchy in PolyTree Union Results

[hziya]

I found a hierarchy issue in PolyTree results. I saw this closed issue, but my case is different.
I attached a text file with the contours needed to reproduce the issue. I couldn’t find a simpler example.

clipper_paths.txt

The last line in the text file represents the small red rectangle inside the complex polygon. However, when computing the union using PolyTree64, this small polygon appears at the same hierarchy level as the inner contour of the outer complex polygon (level 1). Since it is inside that inner contour, it should instead be at level 2.

Additionally, if you insert another polygon inside this complex polygon instead of this small one, its hierarchy will also be incorrect, indicating a general issue with the nesting logic.

Below is the code to reproduce the issue:

  std::ifstream file("clipper_paths.txt");
  std::string line;
  Clipper2Lib::Paths64 paths;
  while (std::getline(file, line)) {
      Clipper2Lib::Path64 path;
      std::istringstream iss(line);
      std::string point;
      while (std::getline(iss, point, ']')) {
          std::istringstream pss(point);
          if (point.empty()) {
              continue;
          }
          std::string x, y;
          std::getline(pss, x, ' ');
          x.erase(std::remove_if(x.begin(), x.end(), [](char c) { return c == '[' || c == ']' || c == ','; }),
                  x.end());
          y.erase(std::remove_if(y.begin(), y.end(), [](char c) { return c == '[' || c == ']' || c == ','; }),
                  y.end());
          std::getline(pss, y, ' ');
          path.emplace_back(std::stod(x), std::stod(y));
      }
      paths.push_back(path);
  }
  
  Clipper2Lib::PolyTree64 solution;
  try {
      Clipper2Lib::Clipper64 c;
      c.AddSubject(paths);
      c.Execute(Clipper2Lib::ClipType::Union, Clipper2Lib::FillRule::NonZero, solution);
  } catch (const Clipper2Lib::Clipper2Exception &e) {
      LOGW("An exception occurred while computing union of polygons: %s", e.what());
  }

Could you confirm if this is expected behavior or a bug? Thanks!

[AngusJohnson]

I found a hierarchy issue in PolyTree results. I saw this closed issue, but my case is different. I attached a text file with the contours needed to reproduce the issue. I couldn’t find a simpler example.

👍👍

The last line in the text file represents the small red rectangle inside the complex polygon. However, when computing the union using PolyTree64, this small polygon appears at the same hierarchy level as the inner contour of the outer complex polygon (level 1). Since it is inside that inner contour, it should instead be at level 2.

I'll investigate (and your post is a great example of how I prefer Issues being raised)😁.

Below is the code to reproduce the issue:

👍👍👍

[hziya]

Are there any updates?

[AngusJohnson]

Are there any updates?

Not yet. I'm tired up with other things..I hope to look at this in the next few days.

[AngusJohnson]

Here's the fix ... (and I'll upload a new revision when I've had some sleep 😁💤).

bool ClipperBase::CheckSplitOwner(OutRec* outrec, OutRecList* splits)
{
  for (auto split : *splits)
  {
    //////////////////////////////////////////////////////////
    if (!split->pts && split->splits && 
      CheckSplitOwner(outrec, split->splits)) return true;
    //////////////////////////////////////////////////////////
    split = GetRealOutRec(split);
    if(!split || split == outrec || split->recursive_split == outrec) continue;
    split->recursive_split = outrec; // prevent infinite loops

    if (split->splits && CheckSplitOwner(outrec, split->splits))
        return true;
    else if (CheckBounds(split) &&
      IsValidOwner(outrec, split) &&
      split->bounds.Contains(outrec->bounds) &&
      Path1InsidePath2(outrec->pts, split->pts))
    {
      outrec->owner = split; //found in split
      return true;
    }
  }
  return false;
}

[hziya]

Thanks a lot! I truly appreciate you taking the time to fix this.