From: Karel Bruneel <karel.bruneel@gm...>  20121026 22:02:14

Hi Everybody, I'm building a PCB design rule checker. To do this I'm making a polygon for each of the nets on the board and then I calculate the intersection for each pair of nets. If there is an intersection, there is a short between the nets and thus a design rule violation. My problem is that what I have now is working but not really fast and this might be due to my very limited knowledge about jts. I'm actually not using jts but jsts, a javascript port of jts that I found on github (https://github.com/bjornharrtell/jsts) through the jts site. To create the polygon for a net I take the union of each of its segments and pads, which are both polygons. So first I create an empty polygon (geometry) and then in a loop I union it with each of the segments and pads. Maybe there is a way this can be made faster? Unioning all the polygons in one go? Next I calculate the intersection of each pair of netpolygons which gives me a new polygon if the nets are shorted. This new polygon is then used for visualization. So the number of intersection calculations is O(n^2) is there a better way to do this like calculating all the intersections of a collection of polygons at once? Or should I do some filtering before I use the intersection calculation to avoid unnecessary invocations? Should I use some spacial indexing for this? Thanks in advance! Karel 
From: Martin Davis <mtnclimb@gm...>  20121026 22:12:56

I can't speak for the performance of JSTS  AFAIK the algorithms are the same as JTS, but it seems likely that JS engines are less performant than JVMs are. Anyway, the choice of algorithm certainly makes a big different to performance. In the case of unioning a set of polygons, you definitely should be using unary union (Geometry.union()). This uses a spatial index to make the union much faster. Using a spatial index should help with the polygon intersection computation. Load the polygons into a spatial index (STRtree is the most performant), and then for each polygon query the index to find polygons which are candidates for intersecting. There's still more performance gains to be made, but at this point it gets to be substantially more code. One thing you can do easily is to convert the polygons to linestrings, and then intersect those  but I'm not sure that will produce big gains. The fastest way to compute intersections is to create an indexed set of the polygon segments, and then test the other polygons segments against that. The index can be cached and reused for subsequent polygons. That's about as much detail as I can provide in a short note. Pretty cool use case! Do you have any screen shots to share? On Fri, Oct 26, 2012 at 3:02 PM, Karel Bruneel <karel.bruneel@...> wrote: > Hi Everybody, > > I'm building a PCB design rule checker. To do this I'm making a polygon for each of the nets on the board and then I calculate the intersection for each pair of nets. If there is an intersection, there is a short between the nets and thus a design rule violation. My problem is that what I have now is working but not really fast and this might be due to my very limited knowledge about jts. > > I'm actually not using jts but jsts, a javascript port of jts that I found on github (https://github.com/bjornharrtell/jsts) through the jts site. > > To create the polygon for a net I take the union of each of its segments and pads, which are both polygons. So first I create an empty polygon (geometry) and then in a loop I union it with each of the segments and pads. Maybe there is a way this can be made faster? Unioning all the polygons in one go? > > Next I calculate the intersection of each pair of netpolygons which gives me a new polygon if the nets are shorted. This new polygon is then used for visualization. So the number of intersection calculations is O(n^2) is there a better way to do this like calculating all the intersections of a collection of polygons at once? Or should I do some filtering before I use the intersection calculation to avoid unnecessary invocations? Should I use some spacial indexing for this? > > Thanks in advance! > Karel > > > > >  > WINDOWS 8 is here. > Millions of people. Your app in 30 days. > Visit The Windows 8 Center at Sourceforge for all your go to resources. > http://windows8center.sourceforge.net/ > joingenerationappandmakemoneycodingfast/ > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser 
From: Karel Bruneel <karel.bruneel@gm...>  20121026 23:08:55
Attachments:
Screen shot 20121027 at 12.28.00 AM.png
Message as HTML

Hi Martin Thanks for the quick reply! I'm using it to build the DRC checker for circuits.io (www.circuits.io) an online PCB layout tool. I must say the jsts.js is amazing. I build a kind of functioning drc checker in a couple of hours :) I attached a screenshot of what I have now. The yellow blobs indicate where the nets are to close together. So probably I'm already using the unary union, right? Is it the standard union operation or should I do something special? So the intersection operation does not use some kind of bypass mechanism for when the bounding boxes of the two polygons don't overlap? Or am I seeing it wrong? Thanks! Karel 
From: Martin Davis <mtnclimb@gm...>  20121026 23:19:29

Very cool. And good to hear that JSTS is working well. You may be using unary union. You can tell by the fact that the method does not take any argument. There's two "standard" union operations  one binary and one unary. The unary one is faster for bulk unions. Use it by creating a GeometryCollection of the geometries to be unioned. Geometry.intersection() does contain a shortcircuit check for bounding boxes overlapping. If you are checking for intersections between all geometries in a set, the straightforward nested loop algorithm is O(n^2). If the number of geometries is large enough, that will begin to dominate the computation. At that point using a spatial index will improve performance. It's the same reason that databases provide indexes for table joins. On Fri, Oct 26, 2012 at 4:08 PM, Karel Bruneel <karel.bruneel@...> wrote: > Hi Martin > > Thanks for the quick reply! > > I'm using it to build the DRC checker for circuits.io (www.circuits.io) an online PCB layout tool. > > I must say the jsts.js is amazing. I build a kind of functioning drc checker in a couple of hours :) I attached a screenshot of what I have now. The yellow blobs indicate where the nets are to close together. > > So probably I'm already using the unary union, right? Is it the standard union operation or should I do something special? > > So the intersection operation does not use some kind of bypass mechanism for when the bounding boxes of the two polygons don't overlap? Or am I seeing it wrong? > > Thanks! > Karel > > > > > > > On Oct 27, 2012, at 12:12 AM, Martin Davis wrote: > >> I can't speak for the performance of JSTS  AFAIK the algorithms are >> the same as JTS, but it seems likely that JS engines are less >> performant than JVMs are. >> >> Anyway, the choice of algorithm certainly makes a big different to >> performance. In the case of unioning a set of polygons, you >> definitely should be using unary union (Geometry.union()). This uses >> a spatial index to make the union much faster. >> >> Using a spatial index should help with the polygon intersection >> computation. Load the polygons into a spatial index (STRtree is the >> most performant), and then for each polygon query the index to find >> polygons which are candidates for intersecting. >> >> There's still more performance gains to be made, but at this point it >> gets to be substantially more code. One thing you can do easily is to >> convert the polygons to linestrings, and then intersect those  but >> I'm not sure that will produce big gains. The fastest way to compute >> intersections is to create an indexed set of the polygon segments, and >> then test the other polygons segments against that. The index can be >> cached and reused for subsequent polygons. That's about as much >> detail as I can provide in a short note. >> >> Pretty cool use case! Do you have any screen shots to share? >> >> On Fri, Oct 26, 2012 at 3:02 PM, Karel Bruneel <karel.bruneel@...> wrote: >>> Hi Everybody, >>> >>> I'm building a PCB design rule checker. To do this I'm making a polygon for each of the nets on the board and then I calculate the intersection for each pair of nets. If there is an intersection, there is a short between the nets and thus a design rule violation. My problem is that what I have now is working but not really fast and this might be due to my very limited knowledge about jts. >>> >>> I'm actually not using jts but jsts, a javascript port of jts that I found on github (https://github.com/bjornharrtell/jsts) through the jts site. >>> >>> To create the polygon for a net I take the union of each of its segments and pads, which are both polygons. So first I create an empty polygon (geometry) and then in a loop I union it with each of the segments and pads. Maybe there is a way this can be made faster? Unioning all the polygons in one go? >>> >>> Next I calculate the intersection of each pair of netpolygons which gives me a new polygon if the nets are shorted. This new polygon is then used for visualization. So the number of intersection calculations is O(n^2) is there a better way to do this like calculating all the intersections of a collection of polygons at once? Or should I do some filtering before I use the intersection calculation to avoid unnecessary invocations? Should I use some spacial indexing for this? >>> >>> Thanks in advance! >>> Karel >>> >>> >>> >>> >>>  >>> WINDOWS 8 is here. >>> Millions of people. Your app in 30 days. >>> Visit The Windows 8 Center at Sourceforge for all your go to resources. >>> http://windows8center.sourceforge.net/ >>> joingenerationappandmakemoneycodingfast/ >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >>  >> WINDOWS 8 is here. >> Millions of people. Your app in 30 days. >> Visit The Windows 8 Center at Sourceforge for all your go to resources. >> http://windows8center.sourceforge.net/ >> joingenerationappandmakemoneycodingfast/ >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 