Use k-d tree to speedup nearest-neighbor lookup

[justbuchanan]

http://en.wikipedia.org/wiki/K-d_tree

[justbuchanan]

@joshhting how's this coming along?

[joshhting]

Slowly and steadily, it's mostly me being confused by how C++ works. I'm trying to make the project with flann, the k-d tree submodule that I'm using, and I'm currently sorting through errors in the linking stage because apparently some of the files in the flann submodule are C++ headers with C implementation files.

[justbuchanan]

Ok, well let me know if you want help with anything. If you want to push your code to GitHub, I can take a look at the linker errors.

[joshhting]

Ok I pushed some code to the flann branch on my fork. When I run make, I get an undefined reference error which I'm not sure how to solve.

[justbuchanan]

Ok, I think I've got this working. See commit 5e53662 on the justin/flann-compile-fix branch.

The main issue was that the flann library wasn't getting compiled by CMake. CMake only builds the c++ files that you tell it to in the CMakeLists.txt file. You had an include_directories() call in there, which makes flann's header files accessible to be #include'd, but the C++ files weren't being compiled. I added some cmake in there that compiles flann, then links it to our rrt library, so I think it's good to go.

[joshhting]

I'm still having trouble compiling it, but now it's because it gets stuck at 14% trying to compile flann.cpp.o. Do you know what could cause make to freeze up here?

[justbuchanan]

Do you get a compile error or does it just hang forever?

[justbuchanan]

I just tried compiling again on my computer and it worked, although it took forever for it to compile flann.cpp.

[joshhting]

Hmm, it just hangs forever for me when it's compiling flann.cpp. I guess I'll just leave it on for longer for now.

[jgkamat]

Just a heads up, theres something off about the flann submodule, It dosent seem to be in the history of the submodule on github. I think its a dangling commit?

error: no such remote ref 26fdfcff2e7f66ab7f78c0a6e806ee69f3d2460f
Fetched in submodule path 'flann', but it did not contain 26fdfcff2e7f66ab7f78c0a6e806ee69f3d2460f. Direct fetching of that commit failed.

[justbuchanan]

Yeah I noticed that too, not sure what happened there... I just cd'd into flann and pulled the latest master branch before compiling

[justbuchanan]

I just pushed an updated version of that submodule checkout to my branch. If you pull from justin/flann-compile-fix, it should work.

[joshhting]

Now I get the following error when I run make (I pulled from justin/flann-compile-fix):

mkdir -p build
cd build && cmake .. -DCMAKE_INSTALL_PREFIX:PATH="" -GNinja && ninja
-- The C compiler identification is GNU 4.8.4
-- The CXX compiler identification is GNU 4.8.4
-- Check for working C compiler using: Ninja
-- Check for working C compiler using: Ninja -- broken
CMake Error at /usr/share/cmake-3.0/Modules/CMakeTestCCompiler.cmake:61 (message):
  The C compiler "/usr/bin/cc" is not able to compile a simple test program.

  It fails with the following output:

   Change Dir: /home/joshting/rrt/build/CMakeFiles/CMakeTmp



  Run Build Command:"/usr/sbin/ninja" "cmTryCompileExec4211792669"

  log: reading configuration file: cmTryCompileExec4211792669



  die: error: unable to read configuration file



  CMake will not be able to correctly generate this project.
Call Stack (most recent call first):
  CMakeLists.txt:2 (project)


-- Configuring incomplete, errors occurred!
See also "/home/joshting/rrt/build/CMakeFiles/CMakeOutput.log".
See also "/home/joshting/rrt/build/CMakeFiles/CMakeError.log".
make: *** [all] Error 1