Repeated union is slower than with Clipper1

[rburing]

Hi, thanks a lot for this great library! I am working on integrating it into Godot:

• https://github.com/godotengine/godot/pull/90153

Is it possible to change something about the Clipper2 program below (or the Clipper2 source code) to make repeated unions as fast as in Clipper1? Probably a big union should not be done like this, but I am trying to update the implementation of an existing API that only has a union(A, B) operation for two polygons A and B.

Clipper1 program:

#include "test_data.h"
#include <chrono>
#include <clipper.hpp>
#include <iostream>
#include <vector>
using namespace ClipperLib;

#define SCALE_FACTOR 100000.0

int main(int argc, char *argv[]) {
  std::chrono::steady_clock::time_point start =
      std::chrono::steady_clock::now();

  Path polygon;

  for (int i = 0; i < test_data.size(); i++) {
    Path path_b;
    for (int j = 0; j < test_data[i].size(); j++) {
      path_b << IntPoint(test_data[i][j].first * SCALE_FACTOR,
                         test_data[i][j].second * SCALE_FACTOR);
    }

    Clipper clp;

    clp.AddPath(polygon, ptSubject, true);
    clp.AddPath(path_b, ptClip, true);

    Paths paths;
    clp.Execute(ctUnion, paths);

    polygon = paths[0];
  }

  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

  std::cout << "Polygon size: " << polygon.size() << std::endl;

  std::cout << "Time elapsed: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;
}

Clipper2 program:

#include "test_data.h"
#include <chrono>
#include <clipper2/clipper.h>
#include <iostream>
#include <vector>
using namespace Clipper2Lib;

#define PRECISION 5

int main(int argc, char *argv[]) {
  std::chrono::steady_clock::time_point start =
      std::chrono::steady_clock::now();

  PathD polygon;

  for (int i = 0; i < test_data.size(); i++) {
    PathD path_b(test_data[i].size());
    for (int j = 0; j < test_data[i].size(); j++) {
      path_b[j] = {static_cast<double>(test_data[i][j].first),
                   static_cast<double>(test_data[i][j].second)};
    }

    ClipperD clp(PRECISION);
    clp.PreserveCollinear(false);

    clp.AddSubject({polygon});
    clp.AddClip({path_b});

    PathsD paths;
    clp.Execute(ClipType::Union, FillRule::EvenOdd, paths);

    polygon = paths[0];
  }

  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

  std::cout << "Polygon size: " << polygon.size() << std::endl;

  std::cout << "Time elapsed: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;
}

The two source files listed above together with a Makefile and test_data.h and the Clipper sources: clipper-performance.zip

Output:

$ ./clipper1-performance 
Polygon size: 56
Time elapsed: 60 ms
$ ./clipper2-performance 
Polygon size: 56
Time elapsed: 93 ms

[rburing]

When compiling with -O2 the performance difference is gone:

$ ./clipper1-performance 
Polygon size: 56
Time elapsed: 16 ms
$ ./clipper2-performance 
Polygon size: 56
Time elapsed: 16 ms

:+1:

This is perhaps worth documenting.

[AngusJohnson]

I understand that the apparent timing lag in Clipper2 disappears when optimisations are enabled, but nevertheless ISTM that you're comparing apples with oranges. To make a fair comparison you need to use Clipper64 not ClipperD in your Clipper2 test. Using type double will cost you a little extra time because, internally in ClipperD, everything is cast to from double to int64_t then later back to double.