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<
