[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: gEDA-user: Locking/unlocking multiple elements

Dave McGuire wrote:
> > Not really, the intersection computation takes more time but computers
> > are so fast  now it simply doesn't matter.
>    Hmm, no offense, but that type of approach is what gave us the
> abyssmal performance of things like Gnome.  Once in a while it's ok,
> but making a habit of it is a very, very bad idea.

The main issue with concave polygons is that there is a higher likelihood of
lines being inside the bounding box, yet not touching the polygon. The worst
case is for a line that doesn't intersect the polygon because all ways in
which it could touch must be tested. One large polygon will have a larger
bounding box and thus probably more lines within that box to check.

However the worst case test is still extremely fast. It's linear in the
number of polygon corners. If you had a 1,000 point polygon with 2,000 lines
inside it's bounding box, none of which touched it, it would require
approximately 8,000,000 comparisons to show it didn't touch. I doubt any
rational pcb layout will need a 1,000 point polygon or that you'd put 2,000
lines inside the bounding box that didn't touch. But if you did, it would
take a fraction of a second (on a modern computer) to find what's connected.

Pcb uses the fastest algorithms I know of for doing this; the issue is
whether the user should also take action in their layout. My answer is no,
they shouldn't. The recent major changes (I made) to pcb to use r-trees for
data searching shows a trend towards improved algorithmic performance so I
think your comment about habit is quite misplaced.