From 478642224bca43ebe2c878159fb5b7989ed2641e Mon Sep 17 00:00:00 2001 From: Arnur Nigmetov Date: Thu, 6 Apr 2017 11:54:54 +0200 Subject: Heuristic for bottleneck: estimate on sampled diagram Sample input diagrams and use the distance between samples as initial guess in binary search. Relevant variables: bottleneck_dist.cpp:10 useSamplingHeur (if false, heuristic is never applied) bottleneck_dist.cpp:11 heurThreshold (heuristic is not applid to diagrams with fewer points) TODO: add command-line parameters instead Sampling strategy: sort points by multiplicity, set cutting value to be the multiplicity where the increase of the next one is maximal and only keep points whose multiplicity is less then the cutting value --- geom_bottleneck/example/bottleneck_dist.cpp | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'geom_bottleneck/example/bottleneck_dist.cpp') diff --git a/geom_bottleneck/example/bottleneck_dist.cpp b/geom_bottleneck/example/bottleneck_dist.cpp index 655de44..b27bdbb 100644 --- a/geom_bottleneck/example/bottleneck_dist.cpp +++ b/geom_bottleneck/example/bottleneck_dist.cpp @@ -6,6 +6,11 @@ typedef std::vector> PairVector; +// estimate initial guess on sampled diagram? +constexpr bool useSamplingHeur = false; +// if diagrams contain fewer points, don't use heuristic +constexpr int heurThreshold = 30000; + int main(int argc, char* argv[]) { if (argc < 3 ) { @@ -29,7 +34,11 @@ int main(int argc, char* argv[]) // return approximate distance (faster) double approxEpsilon = atof(argv[3]); if (approxEpsilon > 0.0) { - res = geom_bt::bottleneckDistApprox(diagramA, diagramB, approxEpsilon); + if (useSamplingHeur && diagramA.size() > heurThreshold && diagramB.size() > heurThreshold) { + res = geom_bt::bottleneckDistApproxHeur(diagramA, diagramB, approxEpsilon); + } else { + res = geom_bt::bottleneckDistApprox(diagramA, diagramB, approxEpsilon); + } } else if (approxEpsilon == 0.0) { res = geom_bt::bottleneckDistExact(diagramA, diagramB, decPrecision); } else { -- cgit v1.2.3