May I enquire about the order of the polygons appear when I map a GDSII file to a txt file?
Are they disordered?
Can I specify it when I do the mapping？
Thanks a lot.
the order of shapes is undefined in the GDS format and the corresponding text file. KLayout writes cell by cell and layer by layer. However the order of the layers only reflects the internal order, not necessarily in ascending order or similar.
I wonder why the order is important. Do you require any geometrical order? What order would make sense?
there is no order by which you can order the polygons in a sequential file that reflects the distance to each other. Sorting by the left border just is the first step. You'll have to track the right border of polygons as well. There is no way to sort in a linear sequence taking both left and right border into account.
A solution for that problem is for example to use a band-scanner implementation which keeps track of objects intersecting with a certain band, objects past the band and in front of the band. The band is then moved while updating the polygon lists with respect to the band. Inside the band you can use the same approach to sort the polygons in the perpendicular direction giving you all objects intersecting with a certain box at each time.
An approach similar to that is used in the boolean operations implementation in KLayout, but using single edges instead of whole polygons.
Another approach is to use a quad tree like it's done in KLayout's database. That allows you to quickly look up all polygons touching a certain rectangular region. That approach is used in KLayout's incremental net tracer implementation.
You can implement both algorithms within your own code, but any order of a linear sequence is only half the truth in the base case. If you want to do a distance check efficiently you have to build a special data structure or use an available implementation like the Boost::Polygon library.
Comments
Hallo,
the order of shapes is undefined in the GDS format and the corresponding text file. KLayout writes cell by cell and layer by layer. However the order of the layers only reflects the internal order, not necessarily in ascending order or similar.
I wonder why the order is important. Do you require any geometrical order? What order would make sense?
Matthias
Because I'm trying to decide whether two polygons are within a given distance.
If they are, there will be a conflict.
If there is no order, I have to check every pair of polygons, which is time consuming.
If it's in the order of left boundry of polygons, it will highly accelerate the process.
Thanks.
Hallo,
there is no order by which you can order the polygons in a sequential file that reflects the distance to each other. Sorting by the left border just is the first step. You'll have to track the right border of polygons as well. There is no way to sort in a linear sequence taking both left and right border into account.
A solution for that problem is for example to use a band-scanner implementation which keeps track of objects intersecting with a certain band, objects past the band and in front of the band. The band is then moved while updating the polygon lists with respect to the band. Inside the band you can use the same approach to sort the polygons in the perpendicular direction giving you all objects intersecting with a certain box at each time.
An approach similar to that is used in the boolean operations implementation in KLayout, but using single edges instead of whole polygons.
Another approach is to use a quad tree like it's done in KLayout's database. That allows you to quickly look up all polygons touching a certain rectangular region. That approach is used in KLayout's incremental net tracer implementation.
You can implement both algorithms within your own code, but any order of a linear sequence is only half the truth in the base case. If you want to do a distance check efficiently you have to build a special data structure or use an available implementation like the Boost::Polygon library.
Best regards,
Matthias