Skip to content

fastjet/internal/delaunay: implement hierarchical removal

Sebastien Binet requested to merge Bastiantheone:hierarchical_removal into master

Created by: Bastiantheone

This PR implements the removal of points using the hierarchical Delaunay method.

BenchmarkHierarchicalDelaunayInsertionAndRemoval50-4                 100
  14990644 ns/op          251160 B/op       9868 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemovall00-4                 50
  31802214 ns/op          519887 B/op      20575 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval150-4                 30
  48335503 ns/op          789009 B/op      31358 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval200-4                 20
  64054045 ns/op         1036826 B/op      41151 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval250-4                 20
  85055830 ns/op         1363603 B/op      53742 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval300-4                 20
 104305825 ns/op         1675167 B/op      65500 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval350-4                 10
 120606840 ns/op         1938459 B/op      76320 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval400-4                 10
 135409980 ns/op         2193260 B/op      85809 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval450-4                 10
 154408850 ns/op         2469645 B/op      96895 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval500-4                 10
 176309790 ns/op         2826494 B/op     109912 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval550-4                 10
 194312990 ns/op         3118071 B/op     121538 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval600-4                  5
 211415760 ns/op         3376384 B/op     131168 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval650-4                  5
 227013440 ns/op         3677582 B/op     143303 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval700-4                  5
 244409480 ns/op         3881249 B/op     151959 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval750-4                  5
 267215280 ns/op         4234763 B/op     165574 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval800-4                  5
 291017040 ns/op         4478049 B/op     175412 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval850-4                  5
 299621220 ns/op         4771755 B/op     185219 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval900-4                  5
 322218840 ns/op         5064040 B/op     197023 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval950-4                  3
 337693266 ns/op         5316234 B/op     207380 allocs/op
BenchmarkHierarchicalDelaunayInsertionAndRemoval1000-4                 3
 362354366 ns/op         5685093 B/op     221822 allocs/op

image

I had to change the root point coordinates because the predicates were giving wrong results for certain constellations.

Merge request reports