Re: gEDA-user: Locking/unlocking multiple elements

[Karel Kulhavý <clock@twibright.com>]

On Mon, Aug 23, 2004 at 10:05:20AM -0400, harry eaton wrote:
> 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.

And what if I had 1,000 point convex polygon with 2,000 lines inside it's
bounding box, none of which touched it -- how many comparisons would it
roughly take?

> 
> Pcb uses the fastest algorithms I know of for doing this; the issue is

It reminds me those days we were taught convex hulls etc. at the college ;-)

Cl<