delorie.com/archives/browse.cgi   search  
Mail Archives: geda-user/2017/11/21/02:49:42

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: <alpine.DEB.2.00.1711210829310.27212@igor2priv>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
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






- Raw text -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019