X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f X-Recipient: geda-user AT delorie DOT com Date: Tue, 21 Nov 2017 08:59:27 +0100 (CET) X-X-Sender: igor2 AT igor2priv To: geda-user AT delorie DOT com X-Debug: to=geda-user AT delorie DOT com from="gedau AT igor2 DOT repo DOT hu" From: gedau AT igor2 DOT repo DOT hu Subject: [geda-user] [dev] rtree rewrite -> minilib Message-ID: User-Agent: Alpine 2.00 (DEB 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII Reply-To: geda-user AT delorie DOT com Hi gEDA developers, I am writing a new rtree minilib. I am writing to the list because this might be interesting to some gEDA projects dealing with 2d geometries. 1. What is an rtree (R-tree) It's a spatial data structure, invented in the '80s. It stores rectangles and makes relatively fast (logarithmic average access time) lookups. The query is "what existing rectangles overlap with my query rectangle?" 2. What rtree can be used for In pcb-rnd (and pcb mainline) all drawing primitives are stored in rtrees, using their bounding box for the rectanlges. When you click the screen, make a selection or find.c needs to know "what objects are connected to this arc", these all start as rtree queries. Rtree rapidly figure which few objects have any chance to be interesting and then a more expensive, per-object-type function is ran for detecting actual overlap knowing the detailed shape. 3. What the new rtree minilib is about? It's very small, it has no dependencies (written in pure C89) and it can accomodate to whatever object model, coordinate types the application has. It can build and maintain multiple rtrees consisting of 2D rectangles. It can do searches, dumps and checks. It can insert and remove objects on the fly. 4. Why writing a new lib? (Read this before you start saying "not invented here") Mainly for long term plans: cschem will need an rtree too. I really like how rtree is used in pcb-rnd. Normally I'd go and cut out the rtree code and make it a lib. I did consider that but there are three problems kept me back from that: - it's very much tied to pcb-rnd's data structures and types, so it would take a lot of work to make it generic - it has no automated tests - we just know it all works because of the lot of hours it's been running under the hood while we were editing boards; but this does not help much if we need to change/extend/generalize the code - it's licensed under the GPL - which is fine for pcb-rnd (and even cschem) but may be a limiting factor in case of a generic library; because he original authors can not even be reached anymore, it's impossible to change the license. So I decided to take some of the ideas from the code, some ideas from other sources and started a full rewrite from scratch, in a separate minilib project. The new code is generic and has a test infrastructure right from the start. It will have a more permissive license (probably LGPL2.1+). The effort took 7 hours so far and I expect it to take another 8..16 hours until it's good enough for production and release. So it's really small and cheap. I plan to use it in cschem and I anticipate it would replace the original rtree code in pcb-rnd some time in 2018. 5. How this could be good for existing projects like pcb-rnd? Moving out custom, local implementation from core into a 3rd party minilib. The advantages of modularization, reuse, proper testing without the disadvantages of having to maintain a local copy or depending on a large, unportable mega-lib that brings its own bool type and keeps on changing for no good reason. 6. If you are interested... in joining the development or just using the lib in your project, please contact me in email or on IRC. Regards, Igor2