Mail Archives: geda-user/2017/11/21/02:49:42
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
- Raw text -