quadtree
quadtree copied to clipboard
KNearest return not in dist order?
Hi, thanks for the quadtree codes and it’s very fast for many points query.
However I wrote a simple program, and found the qtree.KNearest didn’t return in dist order:
package main
import (
"fmt"
"log"
"github.com/asim/quadtree"
)
func main() {
centerPoint := quadtree.NewPoint(0.0, 0.0, nil)
halfPoint := quadtree.NewPoint(90.0, 180.0, nil)
boundingBox := quadtree.NewAABB(centerPoint, halfPoint)
qtree := quadtree.New(boundingBox, 0, nil)
points := []struct {
Lng float64
Lat float64
ID string
}{
{
Lng: 116.2748,
Lat: 39.9989,
ID: "yi-he-yuan",
},
{
Lng: 116.3202,
Lat: 39.9166,
ID: "yu-yuan-tan",
},
{
Lng: 116.3905,
Lat: 39.9285,
ID: "bei-hai",
},
}
for _, point := range points {
if !qtree.Insert(quadtree.NewPoint(point.Lat, point.Lng, point.ID)) {
log.Fatal("Failed to insert the point")
}
}
center := quadtree.NewPoint(39.9289, 116.3883, nil)
distance := 10000.0 /* Distance to the center point in meters */
bounds := quadtree.NewAABB(center, center.HalfPoint(distance))
maxPoints := 3
for _, point := range qtree.KNearest(bounds, maxPoints, nil) {
fmt.Printf("Found point: %s\n", point.Data().(string))
}
}
Output:
Found point: yi-he-yuan
Found point: yu-yuan-tan
Found point: bei-hai
Expect:
Found point: bei-hai
Found point: yu-yuan-tan
Found point: yi-he-yuan
Is that expect? If so how can set return order?