cannot find back original values

[aplusm]

First of all, thank you for your work. I love the design and simplicity of your KDTree

I might i have found an issue with your code, triggered by working on a regular grid of 2D points. Basically, i’m not able to found back the points i’ve inserted in the KDTree. Code below shows it pretty well (where CGSlot is a basic 2-fields struct that conforms to KDTreePoint and used index field for equality)

  func kdTreeError() {

    var points = [CGSlot]()
    for x in 0..<10 {
      for y in 0..<10 {
        points.append(CGSlot(index: 10*x + y, pt: CGPoint(x: x, y:y)))
      }
    }
    print("\(points.count) added")

    let tree = KDTree(values: points)
    var numErrors = 0
    for pt in points {
      if !tree.contains(pt) {
        print("Missing slot num : \(pt.index)")
        numErrors = numErrors + 1
      }
    }
    print("numErrors : \(numErrors)")
  }

Executing this method returns :

numErrors : 37

[Bersaelor]

Thank you for reporting this @aplusm , I added some extra tests to cover your use-case in this branch.

Will try to get to solve the problem as soon as possible.

I'm guessing there are places where a < should be swapped for a <=.

[Bersaelor]

@aplusm Since you're the reporter feel free to approve the PR I made for your problem :)

[Bersaelor]

PS: @aplusm if your data is actually grid-like, there are better ways of finding nearest points then KDTree. KDTree is helpful when you don't know any structures of your data, as it sort of molds itself to the form of your data. If the data is very regular, you can create a custom, regular dataset to perform contains, nearest etc which might be even faster. (In your case a twodimensional array for example, i.e. let grid = [[CGSlot]]() and then calculate the i and j varbiables of a point manually for let somePoint = grid[i][j])

This is sort of similar to neural networks algorithms in data analysis, if you don't have any structure in your data that you know about, NN are great since they adjust themselves to your data. If you know a lot about your data, more heuristic optimization algorithms can be used.

[aplusm]

Thank you for your reactivity @Bersaelor !

My data can range from grid-like data to complete random data. I encountered this bug in various dataset but it seems easier to identify this bug by considering grid-like dataset only.

[Bersaelor]

Understood, that makes sense. I'm actually really happy people use the framework, since I started it more as an academic exercise ;)

[aplusm]

Good job...Really.. Writing a spatial good spatial data structure is hard (eg: Apple's GamePlayKit Quatree/Octree are completely broken)

I'm using cocoapods, do you plan to release an updated pod anytime soon ?

[Bersaelor]

I was waiting till the CI build jobs on travis run through.. it seems nothing happened for a while so I cancelled and restarted the unit tests. ( https://travis-ci.org/Bersaelor/KDTree/builds/267563645 )

[Bersaelor]

@aplusm version 0.5.1 is now live ( https://cocoapods.org/pods/KDTree ) pod repo update on your machine should see it now

[aplusm]

Hi @Bersaelor,

Thanks for the quick deploy of 0.5.1. However, I found another issue, with the same dataset, this time while removing a value in the tree. (value is not found and the same KDTree is returned from the removing method.

Do you want me to open a new Issue ?