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 toNone
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).
Hi Michel,
ReplyDeleteI 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
Hi,
ReplyDeleteI'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.
This comment has been removed by the author.
Deletehttps://github.com/varkenvarken/spacetree/
DeleteGreat thoughts you got there, believe I may possibly try just some of it throughout my daily life.
ReplyDeleterpa 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
Thanks for splitting your comprehension with us. It’s really useful to me & I hope it helps the people who in need of this vital information.
ReplyDeleteData Science training in marathahalli
Data Science training in btm
Data Science training in rajaji nagar
Data Science training in chennai
Data Science training in kalyan nagar
Data Science training in electronic city
Data Science training in USA
Data science training in pune
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.
ReplyDeleteData 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
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!
ReplyDeletejava training in tambaram | java training in velachery
java training in omr | oracle training in chennai
java training in annanagar | java training in chennai
Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.
ReplyDeletepython training in pune
python online training
python training in OMR
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
ReplyDeleteBlueprism training in tambaram
Blueprism training in annanagar
Blueprism training in velachery
Nice blog. Can't be written much better. You’re doing a great job. Keep continuing.
ReplyDeleteEnglish Coaching Classes in Chennai
Best Spoken English Institute in Chennai
Spoken English Course in Chennai
Best IELTS Class in Chennai
IELTS Training Institute in Chennai
IELTS Coaching Classes in Chennai
IELTS Classes near me
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!
ReplyDeletePython Training in Hyderabad | Digital Nest
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.
ReplyDeleteData Science Training in Hyderabad
Great thoughts you got there, believe I may possibly try just some of it throughout my daily life.
ReplyDeletedevops online training
aws online training
data science with python online training
data science online training
rpa online training
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.
ReplyDeleteMicrosoft Azure online training
Selenium online training
Java online training
Python online training
uipath online training
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.
ReplyDeleteSOFTWARE TRAINING IN CHENNAI
POWERBI TRAINING IN CHENNAI
CCNA TRAINING IN CHENNAI
ANDROID TRAINING IN CHENNAI
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
ReplyDeleteThis comment has been removed by the author.
ReplyDeletethanks for sharing this information
ReplyDeletebest python training institute in bangalore
python training institutes in bangalore marathahalli
python training in jayanagar bangalore
python training in btm Layout
Artificial Intelligence training in Bangalore
Artificial Intelligence training in BTM
data science with python training in Bangalore
data science with python training in BTM
Thanks for sharing such a valuable information Advanced Digital Marketing Training Institute In Hyderabad Madhapur
ReplyDeleteHi
ReplyDeleteHow 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
Thanks for sharing such a valuable information
ReplyDeleteYaaron 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
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...
ReplyDeleteData Science Training In Hyderabad
Tableau Trainig In Hyderabad
nice blogs...
ReplyDeletedominican republic web hosting
iran hosting
palestinian territory web hosting
panama web hosting
syria hosting
services hosting
afghanistan shared web hosting
andorra web hosting
belarus web hosting
nice..
ReplyDeletemexico web hosting
moldova web hosting
albania web hosting
andorra hosting
armenia web hosting
australia web hosting
it is excellent blogs...!!
ReplyDeleteinplant training for diploma students
mechanical internship in chennai
civil engineering internship in chennai
internship for b.arch students in chennai
internship for ece students in core companies in chennai
internship in chandigarh for ece
industrial training report for computer science engineering on python
internship for automobile engineering students in chennai
big data training in chennai
ethical hacking internship in chennai
slovakia web hosting
ReplyDeletetimor lestes hosting
egypt hosting
egypt web hosting
ghana hosting
iceland hosting
italy shared web hosting
jamaica web hosting
kenya hosting
kuwait web hosting
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.
ReplyDeleteoracle training in bangalore
ReplyDeleteVery useful post...
python training in chennai
internships in hyderabad for cse 2nd year students
online inplant training
internships for aeronautical engineering students
kaashiv infotech internship review
report of summer internship in c++
cse internships in hyderabad
python internship
internship for civil engineering students in chennai
robotics course in chennai
very good...
ReplyDeleteinternship report on python
free internship in chennai for ece students
free internship for bca
internship for computer science engineering students in india
internships in hyderabad for cse students 2018
electrical companies in hyderabad for internship
internships in chennai for cse students 2019
internships for ece students
inplant training in tcs chennai
internship at chennai
Thanks for this blog are more informative contents in step by step. I here attached my site would you see this blog.
ReplyDelete7 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
Amazing articles useful information.
ReplyDeleteWeb 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
nice blogs....
ReplyDeletecoronavirus update
inplant training in chennai
inplant training
inplant training in chennai for cse
inplant training in chennai for ece
inplant training in chennai for eee
inplant training in chennai for mechanical
internship in chennai
online internship
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:
ReplyDelete-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
Good job in presenting the correct content with the clear explanation. The content looks real with valid information. Good Work
ReplyDeleteDevOps 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
Thanks for providing a useful article containing valuable information. start learning the best online software courses.
ReplyDeleteSailpoint Certification
Oracle Fusion HCM Training
Workday Training
AWS Data Engineering Training
I’m Ravi Varma, a Serial Entrepreneur who enjoys exploring new ideas and business opportunities. I am a fan of technology, design, and entrepreneurship.
ReplyDeleteI enjoy helping companies with strategy, planning and problem-solving.
I aspire to be the best Digital Marketing Trainer in Hyderabad, as I train individuals on digital Marketing Skills and help them make a career out of Digital Marketing.
Class RoomOnline2 Weeks8,000 RsRs. 6000/-
ReplyDeleteVery Informative and unique content. This the best blog post I've read . Thanks for sharing
ReplyDeleteTrading for beginners
Best Web designing company in Hyderabad
Best Web development company in Hyderabad
Best App development company in Hyderabad
Data Science Course in Hyderabad
ReplyDeleteBecome a Data Science Expert with us.We provide Classroom training on IBM Certified Data Science at Hyderabad for the individuals who believe hand-held training. We teach as per the Indian Standard Time (IST) with In-depth practical Knowledge on each topic in classroom training, 80 – 90 Hrs of Real-time practical training classes. There are different slots available on weekends or weekdays according to your choices.
Get trained on data science course in hyderabad by real-time industry experts and excel your career with Data Science training by Technologyforall. #1 online training institute for Data Science
ReplyDeleteAI Patasala Python Course in Hyderabad is sure to be the ideal choice for those looking to gain insight into all the real-world challenges in this field. AI Patasala Python course is the best option for students to begin their career with the latest technology.
ReplyDeletePython Training in Hyderabad
Thank you Sharing your Views on this.
ReplyDeletePlease click the link to get highest returns on your investment.
Open Plots in Hyderabad - Aspirealty
Open Plots for Sale Near Tukkuguda @ Srisailam Highway - Aspirealty Advaith
Open Plots for Sale Near MAK Projects @ Srisailam Highway - Aspirealty Amogh
Open Plots in Tukkuguda - Aspirealty KingsDell
Become a data science expert by joining AI Patasala’s Data Science Training in Hyderabad, where you can learn more advanced data science topics with real-time experience. AI Patasala offers both online and offline classroom training sessions for data science aspirants. After completion of the course, you will receive industry-recognized certification, which will help you get a data science job in top MNCs.
ReplyDeleteData Science Course in Hyderabad
Data Science Course Training Institute in Hyderabad
Hey thank you!!! I was seeking for the particular information for long time. Good Luck ?
ReplyDeleteDigital marketing course in Delhi are an ideal way to further your career. You can get advice from experienced marketing professionals and establish your professional network as soon as you can. In fact, Digital Marketing Institute Digital Marketing course recently introduced a unique certification course for business leaders. It is designed to help improve your knowledge of marketing and boost the confidence to achieve your goals. Whether you are a senior marketer or rising star, this program is ideal for you. The program includes 12 classes and online modules, the program also features interactive Q&As along with support from a community of experts. It will provide all the information you need to make it. Presented by Raja Rajamannar, a senior market leader this program is open to senior marketing professionals, in addition to to professionals across all functions.
ReplyDeleteI like your blog. Grow your career with Python training course in Noida. kd-tree for quick nearest-neighbor lookup. This table provides an index for k-dimensional points that can be used to find the nearest neighbor of each point.
ReplyDeleteVery educational and original information. My favorite blog post to date. Thank you for revealing
ReplyDeleteLearn Python Fullstack Course in Hyderabad