How to find cell instances that intersect with a box

Hi, I'm becoming fairly familiar with the python API and my question is about a strategy within the API calls to achieve a goal.

I want to know the leaf cell instances that intersect with a given box. I'm getting there right now by selecting the shapes that intersect with that box and creating a RecursiveShapeIterator (called shape_iterator below).

instance_path = shape_iterator.path()
last_cell_inst = instance_path[-1].cell_inst()

This runs once per shape instead of once per cell instance, so I'm wondering if I could improve the performance by navigating the hierarchy tree instead of the shapes themselves.

I originally tried to start with the top cell and select cells that intersected with the box, but it only returns cells in the top cell itself which doesn't give me my leaf cell information. Is there a strategy that would allow me to find the cell instances without processing every shape?

Many Thanks for any guidance you can provide.
-jpk

Comments

  • Hi jpk,

    you can create a RecursiveShapeIterator from a cell with a search box. This will then return only the shapes within this box (seen from the initial cell) and only traverse the subcell instances inside this box.

    Is this what you are looking for?

    Matthias

  • The RecursiveShapeIterator solution is what I'm doing currently. Since it runs at the "shape" level, I'm guessing that it might run faster if I could traverse just the instance hierarchy information without having to query for every shape that exists inside the search box.

    I guess I'm looking for something like RecursiveShapeIterator but more like "RecursiveInstanceIterator" that will return a stream of cell instances that are inside the search box instead of shapes.

  • Hi jpk,

    I see your point.

    Internally there is such a thing, but not on the script level. It's a method called "skip_instance" which you can call to jump to the next instance. I have not considered yet to expose it to Python because I could not imagine a use case.

    Without this, you can emulate the whole procedure in Python, but I guess it will awfully slow.

    As a workaround it might be possible to define a dummy layer and place a rectangle with the dimension of the cell's bounding box for each cell. Then there is a single shape per cell and iterating over this layer will give you each instance once.

    Regards,

    Matthias

  • I ended up using a LayoutQuery, like this:

    select_string = "select cell.name, cell.cell_index, path_trans.disp.x, path_trans.disp.y from instances of ...* \
    where path_trans.disp.x >= {0} \
    && path_trans.disp.x <= {1} \
    && path_trans.disp.y >= {2} \
    && path_trans.disp.y <= {3}".format(marker_box.left,marker_box.right,marker_box.bottom,marker_box.top)

    results = [item.data() for item in pya.LayoutQuery(select_string).each(active_layout)]

  • Cool :-)

    I just saw another post where someone complained about the performance of queries (not specifically in this context). If you're happy with that I think that is fine. The query is not smart enough to do a region search and shortcut evaluation. Essentially it will walk through all instances in a brute-force approach. The RecursiveShapeIterator is better in this respect. But the above approach is good if you have many shapes and few instances.

    BTW: another way to write the query is this:

    select cell.name, cell.cell_index, path_trans.disp.x, path_trans.disp.y from instances of ...* 
    where (path_trans * cell.bbox).overlaps(Box.new({0}, {1}, {2}, {2}))
    

    Matthias

  • jpkjpk
    edited July 2019
    Thanks for the pointer on the rewritten select statement. That’s elegant.

    BTW, I found it challenging to get started with the usage of LayoutQuery because the syntax for the select statements is not documented in the API docs (or I couldn’t find it, anyway...) I eventually found it in the search/replace feature within klayout but I didn’t initially know to look there. It might help others if there was a link to the select syntax directly in the LayoutQuery api docs.
  • You're right. Thanks for that suggestion.

    BTW: I have added variables recently so you can basically pass the box into the query without the string substitution. That's a bit faster and avoids string-to-double conversion issues (accuracy limits, special values like "inf" or "nan" ...).

    Matthias

Sign In or Register to comment.