quadtree icon indicating copy to clipboard operation
quadtree copied to clipboard

KNearest return not in dist order?

Open ringsaturn opened this issue 3 years ago • 0 comments

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?

ringsaturn avatar Sep 18 '22 14:09 ringsaturn