[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: gEDA-user: Locking/unlocking multiple elements
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
> 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 ;-)