Clipper2 slower than clipper1

[Sachaaaaaa]

Hi there,

I've been using Clipper for generating GDS files, and recently I migrated my code from Clipper 1 to Clipper 2. However, I've noticed a significant decrease in performance for certain operations, especially union.

Interestingly, when I perform random operations, Clipper 2 shows much better performance compared to Clipper 1. However, when I try to generate a "grid cover," which essentially creates a grid with numerous repetitions of a square shape, the performance seems to degrade significantly (Clipper2 two times slower than Clipper1).

grid cover :

I've come across some discussions on this issue, but unfortunately, I haven't found a solution yet, even after trying optimization flags like -O3.

I'm hoping that the problem lies within my code and that there might be some optimizations that could be implemented to improve performance.

Any suggestions or insights would be greatly appreciated.

Clipper2 code :

    Paths64 subj, clip;
    PolyTree64 solution;

    Clipper64 c64;


    subj = makePathsFromFile("clip.txt");
    clip = makePathsFromFile("subj.txt");


    c64.AddSubject(subj);
    c64.AddClip(clip);


    auto start = std::chrono::steady_clock::now();

    c64.Execute(ClipType::Union, FillRule::NonZero, solution);

    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "Temps d'exécution : " << elapsed_seconds.count() << " secondes" << std::endl;
    

Clipper 1 :

    Paths subj, clip;
    PolyTree solution;

    Clipper c64;

    subj = makePathsFromFile("clip.txt");
    clip = makePathsFromFile("subj.txt");

    c64.AddPaths(subj, ptSubject, true);
    c64.AddPaths(clip, ptClip, true);

    auto start = std::chrono::steady_clock::now();

    c64.Execute(ClipType::ctUnion, solution, pftNonZero, pftNonZero);

    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "Temps d'exécution : " << elapsed_seconds.count() << " secondes" << std::endl;

code of makePathsFromFile for Clipper2 :
/!\ I know the following codes are very inefficient but it doesn't matter i just did that for testing purpose

Paths64 makePathsFromFile(const std::string& filename){
  
  Paths64 benchmark; 

  // Open the file
  std::ifstream infile(filename); 
  
  // Check if the file is not already in use
  if (!infile.is_open()) {
      std::cerr << "Erreur lors de l'ouverture du fichier." << std::endl;
  }

  int he=0;
  std::string line;
  std::vector<std::vector<int>> allValues;
  while (std::getline(infile, line)) { // Go across each line
      Paths64 path;
      std::istringstream iss(line);
      int x, y;
      char comma;
      std::vector<int> values;
      while (iss >> x >> comma >> y >> comma) { // Read the int x, y
          values.push_back(x);
          values.push_back(y);
      }

      values.push_back(x);
      values.push_back(y);   

      allValues.push_back(values);
  }


  // Close the file
  infile.close();

  for (const auto& values : allValues) {
      benchmark.push_back(MakePath(values)); 
  }
  

  return benchmark;
}

code of makePathsFromFile for Clipper1 :

Path makePath(const std::vector<int>& points) {
    Path path;
    for (size_t i = 0; i < points.size(); i += 2) {
        path.push_back(IntPoint(points[i], points[i + 1]));
    }
    return path;
}


Paths makePathsFromFile(const std::string& filename){
  
  Paths benchmark; 

  // Open the file
  std::ifstream infile(filename); 
  
  // Check if the file is not already in use
  if (!infile.is_open()) {
      std::cerr << "Erreur lors de l'ouverture du fichier." << std::endl;
  }

  int he=0;
  std::string line;
  std::vector<std::vector<int>> allValues;
  while (std::getline(infile, line)) { // Go across each line
      Paths path;
      std::istringstream iss(line);
      int x, y;
      char comma;
      std::vector<int> values;
      while (iss >> x >> comma >> y >> comma) { // Read the int x, y
          values.push_back(x);
          values.push_back(y);
      }

      values.push_back(x);
      values.push_back(y);   

      allValues.push_back(values);
  }


  // Close the file
  infile.close();

  for (const auto& values : allValues) {
      benchmark.push_back(makePath(values)); 
  }
  

  return benchmark;
}

And the data :
(Note that those Paths are not random it is real case scenario)
archiveCompressed.zip

[AngusJohnson]

Hi Sasha.
Clipper2 is indeed a little slower that Clipper1 given your example above.
However, my measurements make it about 20% slower, not "two times" slower as you seem to be measuring.

Anyhow, I'm not entirely sure why Clipper2 is a little slower in this instance. I was initially presuming it was due to all the extra work Clipper2 does to ensure that "touching" polygons in clipping solutions are properly merged. (This was very incomplete in Clipper1). Unfortunately, disabling all this additional merging code doesn't seem to make much difference in Clipper2's performance.

ComparePerformanceWithClipper1.zip

[niki-sp]

On 17.05.24 г. 12:53 ч., Angus Johnson wrote: ... Anyhow, I'm not entirely sure why Clipper2 is a little slower in this instance. I was initially presuming it was due to all the extra work Clipper2 does to ensure that "touching" polygons are properly merged. (This was very incomplete in Clipper1). Unfortunately, disabling all this additional merging code doesn't seem to make much difference in Clipper2's performance.

Can you post example for disabling the merging? thanks in advance, Niki

[LarsSkiba]

I achieved huge performance gains in a similiar case by subdividing the space and perfoming multiple unions recursively.

[zhangjiangzhao123]

Can you share the code implementation? This is very helpful to me.
Thanks in advance

[LarsSkiba]

No, sorry