Saturday, 13 April 2013

A pure Python kd-tree implementation

kd-trees are an efficient way to store data that is associated with a location in any number of dimensions up to twenty or so. Specifically, kd-trees allow for nearest neighbor searches in O(log n) time, something I desperately needed for my Blender tree generation add-on. In this article I highlight some of the design decisions that that shaped my pure Python implementation of a kd-tree module.

Visiting my own post five years later a lot has changed. We are now quite a few versions of Blender ahead of what was available in 2013 and a kd-tree implementation is now part of Blender's Python API.
I highly recommend using that implementation because is written in C and probably quite a bit faster than my pure Python implementation. There is also a bvh-tree implementation that is suited for problems that not such much involve points but geometry that fills space, like triangles.

kd-trees

There exist quite a few implementations in C or C++ that are part of robust and well tested libraries but for my Blender add-on I needed a platform neutral (= pure python) implementation that I could ship with the add-on. There are a few Python implementations but because I could not determine how well tested they were or because they did not quite meet my requirements I decided to develop an implementation myself.

Requirements

My requirements might not be everybody's requirements so besides supporting adding nodes and providing a nearest neighbor search what were the issues that were important to me?

    Comes with test-suite
    It might seem strange to make this the first requirement but because it's a part that is so essential to my add-on and because the code is quite tricky, I opted for test driven development. Adding unit tests to a python module is quite simple and although I can't claim that the tests cover all edge cases, they are nevertheless quite comprehensive. There is also a small performance test included.
    Works with any iterable as position
    A node in a kd-tree consists besides other things primarily of a position attribute. For use in Blender this typically would be a Vector instance but in other situations you might want to use other vector implementations. This kd-tree implementation assumes very little about its position attributes, just that it is subscriptable and that it supports a .dot() member function that returns the sum of the pairwise multiplication of its items (in other words, the dot product which is equal to the distance squared). Individual items should be floats (or anything that supports substraction, addition and comparisons). Probably any vector implementation will meet these requirements. The test-suite implements its own, based on Python's list class.
    Allows easy deletion
    Deleting nodes from a kd-tree is tricky and costly because of the rebalancing that has to be performed. I therefor opted for a much simpler solution: Instead of deleting a node we set its data attribute to None and add an option to the .nearest() member function to ignore nodes without data. Of course this won't make the tree any smaller but even when we delete a third of the nodes in random fashion (a typical use case for my tree add-on) the performance impact on nearest neighbor searches is minimal.

Availability

The module is licensed as GPL and available on Github as part of the spacetree add-on for Blender. It is contained in a single source file that can be downloaded separately (click Raw to download).

108 comments:

  1. Hi Michel,
    I am sorry about posting the comments related to your book under this article, couldn't find a way to give you my feed back so far, just going through your book Python 3 web development, I am on chapter 3, so far looks very good,but found two things which need your attention:
    1) For some reason your spreadsheet examples (chapter 2 & 3) are not working for me, I can load the spreadsheet but when I enter any number and move to next screen, it removes the data.
    2) Chapter 3 - when I load loagonapp and go to logon screen the images are not showing up and the reason is (I think) you are missing this in logonapp.py config section (to alias images folder) like this:
    '/images':
    { 'tools.staticdir.on':True,
    'tools.staticdir.dir':os.path.join(current_dir,"static","jquery","css","redmond","images")
    },
    When I added the above, Log in button started showing icon.

    Thanks

    Philip

    ReplyDelete
    Replies
    1. I am glad that I saw this post. It is informative blog for us and we need this type of blog thanks for share this blog, Keep posting such instructional blogs and I am looking forward for your future posts. Python Projects for Students Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account. Project Center in Chennai

      Delete
  2. Hi,

    I'm interested in your pure python kdtree implementation, but the link to github is broken. Where can I find it? I'm using brute force right now, and I hope to speed up nearest neighbor search like this.

    Regards,
    Anton.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. https://github.com/varkenvarken/spacetree/

      Delete
  3. Thanks for the informative article. This is one of the best resources I have found in quite some time. Nicely written and great info. I really cannot thank you enough for sharing.

    rpa Training in Chennai

    rpa Training in bangalore

    rpa Training in pune

    blueprism Training in Chennai

    blueprism Training in bangalore

    blueprism Training in pune

    rpa online training

    ReplyDelete
  4. It's interesting that many of the bloggers to helped clarify a few things for me as well as giving.Most of ideas can be nice content.The people to give them a good shake to get your point and across the command

    rpa Training in tambaram

    blueprism Training in tambaram

    automation anywhere training in tambaram

    iot Training in tambaram

    rpa training in sholinganallur

    blue prism training in sholinganallur

    automation anywhere training in sholinganallur

    iot training in sholinganallur

    ReplyDelete
  5. All are saying the same thing repeatedly, but in your blog I had a chance to get some useful and unique information, I love your writing style very much, I would like to suggest your blog in my dude circle, so keep on updates.
    Data Science Training in Chennai
    Data science training in bangalore
    Data science online training
    Data science training in pune
    Data science training in kalyan nagar
    selenium training in chennai


    ReplyDelete
  6. I have picked cheery a lot of useful clothes outdated of this amazing blog. I’d love to return greater than and over again. Thanks! 
    java training in tambaram | java training in velachery

    java training in omr | oracle training in chennai

    java training in annanagar | java training in chennai

    ReplyDelete
  7. Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.
    python training in pune
    python online training
    python training in OMR

    ReplyDelete
  8. Good Post! Thank you so much for sharing this pretty post, it was so good to read and useful to improve my knowledge as updated one, keep blogging.
    Devops training in velachery
    Devops training in annanagar
    Devops training in sholinganallur

    ReplyDelete
  9. Thank you for this post. Thats all I are able to say. You most absolutely have built this blog website into something speciel. You clearly know what you are working on, youve insured so many corners.thanks
    Blueprism training in tambaram

    Blueprism training in annanagar

    Blueprism training in velachery

    ReplyDelete
  10. Howdy, would you mind letting me know which web host you’re utilizing? I’ve loaded your blog in 3 completely different web browsers, and I must say this blog loads a lot quicker than most. Can you suggest a good internet hosting provider at a reasonable price?
    Amazon Web Services Training in OMR , Chennai | Best AWS Training in OMR,Chennai


    Amazon Web Services Training in Tambaram, Chennai|Best AWS Training in Tambaram, Chennai

    ReplyDelete
  11. I’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
    Best AWS Training in Marathahalli | AWS Training in Marathahalli
    Amazon Web Services Training in Anna Nagar, Chennai |Best AWS Training in Anna Nagar, Chennai
    AWS Training in Velachery | Best AWS Course in Velachery,Chennai
    Best AWS Training in Chennai | AWS Training Institutes |Chennai,Velachery

    ReplyDelete
  12. Your article is awesome! How long does it take to complete this article? I have read through other blogs, but they are cumbersome and confusing. I hope you continue to have such quality articles to share with everyone! I believe there will be many people who share my views when they read this article from you!

    Python Training in Hyderabad | Digital Nest

    ReplyDelete
  13. Best Business Analytics Training, Big Data Analytics And Data Scientist Course / Data Science Course Training In Hyderabad, With 100% Placement Assistance.
    https://www.excelr.com/business-analytics-training-in-hyderabad/

    ReplyDelete
  14. Thanks for such a great article here. I was searching for something like this for quite a long time and at last I’ve found it on your blog. It was definitely interesting for me to read about their market situation nowadays. Well written article Thank You for Sharing with Us.
    Data Science Training in Hyderabad

    ReplyDelete
  15. Awesome! Education is the extreme motivation that open the new doors of data and material. So we always need to study around the things and the new part of educations with that we are not mindful.
    Microsoft Azure online training
    Selenium online training
    Java online training
    Python online training
    uipath online training

    ReplyDelete
  16. It is a great post. Keep sharing such kind of useful information.

    Technology
    karnatakapucresult

    ReplyDelete
  17. indeed, I’m just always astounded concerning the remarkable things served by you. Some four facts on this page are undeniably the most effective I’ve had.
    SOFTWARE TRAINING IN CHENNAI
    POWERBI TRAINING IN CHENNAI
    CCNA TRAINING IN CHENNAI
    ANDROID TRAINING IN CHENNAI

    ReplyDelete
  18. Thank you for providing such an awesome article and it is a very useful blog for others to read.

    Oracle ICS Online Training

    ReplyDelete
  19. Thanks for providing a useful article containing valuable information. start learning the best online software courses.

    Workday Online Training

    ReplyDelete
  20. Thanks for sharing such an amazing information its very beneficial for our company. our company name is innomatics research labs we offering data science,big data and many more courses to make student career success full and we are giving online, classroom and corporate training our website is https://www.innomatics.in


    ReplyDelete
  21. An overwhelming web journal I visit this blog, it's unfathomably amazing. Unusually, in this present blog's substance made inspiration driving truth and reasonable. The substance of data is enlightening
    Oracle Fusion Financials Online Training
    Oracle Fusion HCM Online Training
    Oracle Fusion SCM Online Training

    ReplyDelete
  22. This comment has been removed by the author.

    ReplyDelete
  23. Hi
    How I share your post to my social friennds? I found a new topic that have to share my friend immediatly. Because of I am a food lover and lot of my friends are foodie. I am also a new cooker but still do not know how to cook delicious food.I want to save my time to cook thats why I am finding a blender. Which blender you use to blend your cooking? Could you mention me a best small blender for me which you use. I want to make me a good coocker. I hope you will help me reach out a good coocker.
    Thanks

    ReplyDelete
  24. Thanks for sharing such a valuable information
    Yaaron Studios is one of the rapidly growing editing studios in Hyderabad. We are the best Video Editing services in Hyderabad. We provides best graphic works like logo reveals, corporate presentation Etc. And also we gives the best Outdoor/Indoor shoots and Ad Making services.
    Best video editing services in Hyderabad,ameerpet
    Best Graphic Designing services in Hyderabad,ameerpet­
    Best Ad Making services in Hyderabad,ameerpet­

    ReplyDelete
  25. Amazing Write-up! I appriciate this information and how effective it would be. it was very effective thats why i would definitley be intrested to this amazing post and the format was very understandble and knowledgeble...
    Data Science Training In Hyderabad
    Tableau Trainig In Hyderabad

    ReplyDelete
  26. I must appreciate you for providing such a valuable content for us. This is one amazing piece of article. Helped a lot in increasing my knowledge.

    oracle training in bangalore

    ReplyDelete
  27. Thank you so much for sharing this blog, such a nice information u have posted. i'm so thankful for your blog .

    data science training in hyderabad.

    ReplyDelete
  28. Thanks for this blog are more informative contents in step by step. I here attached my site would you see this blog.

    7 tips to start a career in digital marketing

    “Digital marketing is the marketing of product or service using digital technologies, mainly on the Internet, but also including mobile phones, display advertising, and any other digital medium”. This is the definition that you would get when you search for the term “Digital marketing” in google. Let’s give out a simpler explanation by saying, “the form of marketing, using the internet and technologies like phones, computer etc”.

    we have offered to the advanced syllabus course digital marketing for available join now.

    more details click the link.

    https://www.webdschool.com/digital-marketing-course-in-chennai.html

    ReplyDelete
  29. Amazing articles useful information.

    Web designing trends in 2020

    When we look into the trends, everything which is ruling today’s world was once a start up and slowly begun getting into. But Now they have literally transformed our lives on a tremendous note. To name a few, Facebook, Whats App, Twitter can be a promising proof for such a transformation and have a true impact on the digital world.

    we have offered to the advanced syllabus course web design and development for available join now.

    more details click the link.

    https://www.webdschool.com/web-development-course-in-chennai.html

    ReplyDelete
  30. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
    workday studio online training
    best workday studio online training
    top workday studio online training

    ReplyDelete
  31. This professional hacker is absolutely reliable and I strongly recommend him for any type of hack you require. I know this because I have hired him severally for various hacks and he has never disappointed me nor any of my friends who have hired him too, he can help you with any of the following hacks:

    -Phone hacks (remotely)
    -Credit repair
    -Bitcoin recovery (any cryptocurrency)
    -Make money from home (USA only)
    -Social media hacks
    -Website hacks
    -Erase criminal records (USA & Canada only)
    -Grade change
    -funds recovery

    Email: onlineghosthacker247@ gmail .com

    ReplyDelete
  32. My spouse and I love your blog and find almost all of your posts to be just what I’m looking for. Appreciating the persistence you put into your blog and the detailed information you provide. I found another one blog like you Data Analytics .Actually I was looking for the same information on internet for Data Analytics Service and came across your blog. I am impressed by the information that you have on this blog. Thanks once more for all the details.

    ReplyDelete
  33. Good job in presenting the correct content with the clear explanation. The content looks real with valid information. Good Work
    DevOps is currently a popular model currently organizations all over the world moving towards to it. Your post gave a clear idea about knowing the DevOps model and its importance.

    Good to learn about DevOps at this time.
    DevOps Training in Chennai

    DevOps Course in Chennai

    ReplyDelete
  34. Thank you for posting informative insights, I think we have got some more information to share with! Do check out
    oracle training in chennai and let us know your thoughts. Let’s have great learning!

    ReplyDelete
  35. Sharing the same interest, Infycle feels so happy to share our detailed information about all these courses with you all! Python Training In Chennai & get to know everything you want to about software trainings.

    ReplyDelete
  36. If Big Data is a job that you're dreaming of, then we, Infycle are with you to make your dream into reality. Infycle Technologies offers the best Big Data Course Chennai, with various levels of highly demanded software courses such as Java, Python, Hadoop, AWS, etc., in 100% hands-on practical training with specialized tutors in the field. Along with that, the pre-interviews will be given for the candidates, so that, they can face the interviews with complete knowledge. To know more, dial 7502633633 for more.Big Data Training in Chennai

    ReplyDelete
  37. nice blog
    Our Digital Marketing course in Hyderabad focuses on Making you employeable.

    We make sure you have the right skill to get a job in Digital Marketing.
    digital marketing course in hyderabad

    ReplyDelete
  38. Thanks for providing a useful article containing valuable information. start learning the best online software courses.
    Sailpoint Certification
    Oracle Fusion HCM Training
    Workday Training
    AWS‌ ‌Data‌ ‌Engineering‌ Training

    ReplyDelete