Re: gEDA-user: DRC rule structure

[Armin Faltl <armin.faltl@xxxxxx>]

Andrew Poelstra wrote:
> I like this. Since many features on a PCB are traces, which are long
> and thin, I wonder if we could achieve an even-greater speedup by
> using "bounding ellipses" rather than circles. With rounded-up sine
> tables I think we can do the check nearly as fast as we could with
> simple circles (will have to check my calc book), and we'd eliminate
> a -lot- more components in the initial scan.
>   
Bounding spheres and -circles are quite common. As DJ indicated pcb 
already has
r-trees implemented (http://en.wikipedia.org/wiki/R-tree). Sorting 
bounding boxes
by their edges and storing the result in 4 or 6 (3D) B+trees is another 
option.
In that case you don't even have to look at most of the objects (O(log n)).
An other option is quad trees (oct trees in 3D) that devide the space 
into non-overlapping
segments and allow an object to be part of several nodes.
Finding the smallest bounding box that is *not* axis-aligned is a hard 
problem
in general (trivial for a set of 2 circles) with lots of approaches and 
literature.
Finding the smallest ellipse, say with minimum area I think isn't 
trivial, even for 2 circles.

Checking the intersection of circles is fast only, because it can be reduced
to the distance of their centers.
The best way I can immediately write to check ellipses will involve solving
a quadratic equation - requires taking a square root. I'm not quite sure
atm but for circles the distance can be squared and the root avoided.
For just testing whether the solutions are complex, no actual root taking
with quadratic equations is required either. Problem remains to find out
when an ellipse is fully inside the other...

Spheres have no natural easy way to compute the bounding sphere of 
aggregates
from the spheres of components, therefore they are sometimes used with 
one of the
trees above.

This is not to discourage you, just meant as hints.


_______________________________________________
geda-user mailing list
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user