Find Closest Edge Performance with Many Polylines

[mccalltd]

Hi! Thanks for the great library. I would really like to use it to find nearby edges in road networks, but am having trouble getting scalable performance anywhere close to performance touted here.

I create an index with many Polylines, each containing N>1 edges. As the size of the index scales up, the closest edge query slows down:

BenchmarkS2NearestN/edges:_1-16         	 1406076	       849 ns/op	     584 B/op	      12 allocs/op
BenchmarkS2NearestN/edges:_2-16         	 1000000	      1038 ns/op	     585 B/op	      12 allocs/op
BenchmarkS2NearestN/edges:_4-16         	  914354	      1390 ns/op	     586 B/op	      12 allocs/op
BenchmarkS2NearestN/edges:_8-16         	  603141	      2038 ns/op	     589 B/op	      12 allocs/op
BenchmarkS2NearestN/edges:_16-16        	  308814	      3957 ns/op	     596 B/op	      12 allocs/op
BenchmarkS2NearestN/edges:_32-16        	  153189	      8489 ns/op	    1244 B/op	      35 allocs/op
BenchmarkS2NearestN/edges:_64-16        	  111956	     11280 ns/op	    1242 B/op	      34 allocs/op
BenchmarkS2NearestN/edges:_128-16       	   54687	     21748 ns/op	    1309 B/op	      38 allocs/op
BenchmarkS2NearestN/edges:_256-16       	   25036	     47599 ns/op	    1381 B/op	      42 allocs/op
BenchmarkS2NearestN/edges:_512-16       	   13784	     88142 ns/op	    1455 B/op	      45 allocs/op
BenchmarkS2NearestN/edges:_1024-16      	    5572	    192456 ns/op	    1511 B/op	      47 allocs/op
BenchmarkS2NearestN/edges:_2048-16      	    3582	    338513 ns/op	    1511 B/op	      47 allocs/op
BenchmarkS2NearestN/edges:_4096-16      	    1615	    786304 ns/op	    1591 B/op	      51 allocs/op
BenchmarkS2NearestN/edges:_8192-16      	     493	   2541775 ns/op	    1659 B/op	      54 allocs/op

I checked the benchmarks here and noticed that the test is run against a single shape with N edges, which is different from my naive indexing strategy of N shapes with few edges.

Being relatively new to the problem space, I wonder if you could help advise me about whether this library is a good fit for what I am trying to do? And if so, any tips on how to better model my network in S2?

FWIW, I pulled the source locally and tried to run the benchmark modeling my scenario, but the test times out. I added the following loopShapeIndexGenerator and swapped it out with the one used by the benchmark linked above:

func edgeCloudShapeIndexGenerator(c Cap, numEdges int, index *ShapeIndex) {
	for i := 0; i < numEdges; i++ {
		p1, p2 := samplePointFromCap(c), sampleBoundaryFromCap(c)
		index.Add(&Polyline{p1, p2})
	}
}

Thanks!

[jmr]

@rsned