Stats

  • Locked Locked
  • Replies 4
  • Subscribers 144
  • Views 9380
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

abeLayerTouch result question

BorisD

Greetings,

 I have a script which takes as input a string expression like this "PC touch CA touch M1 touch (...)"  etc. This expression can have arbitrary length and represents connectivity information. I created a parser based on Advanced Boolean Engine (abe) routines to check if the expression evals to t/nil. For 'touch' operation I use abeLayerTouch which works perfectly fine:

abeLayerTouch( abeLayer1 abeLayer2 abeResult )

The issue I have is that the resulting abeResult contains only the tiles from abeLayer1 that touch abeLayer2. But for my purpose, I need to continue checking using the entire islands from abeLayer1 that touch segments from abeLayer2. 

QUESTIONS:

  1. Is there a way for abeLayerTouch to return the entire island (aka polygon) instead of just the partitioned tile ?
  2. If not, any suggestions for alternative way to get what I want? I was trying to come up with a solution entirely within ABE realm, because of how quick it is. However, I finally resorted to loops and geometry.
  3. Are the islands in geoLayer OR abeIslandIterator sorted by default for number of points?
  4. For checking if a concave polygon is touching a rectangle, I couldn't find anything better than dbPointArrAnd, any ideas here? It felt really slow since for some reason it requires cellView and moreoever, I don't need it to return the overlapping area, I need boolean answer. So I wrote a 2 step algorithm, which profiled and turn out to better:
    1. Check if the sum of radiuses (r1 + r1) of smallest enclosing circle around two polygons is less then the distance between the circle center points L. If L>r1+r2 then polygons don't touch and stop here.
    2. Else check if at least one line N of polygonA is crossing|abutting line K of polygonB. If yes - polygons are abutting or straddle stop here.
      NOTE: This algorithm does not detect when polygonB is entirely inside polygonA without any abutting or crossing lines. However, this is not possible for my scenario with the abeLayerTouch.

 I ended up writing my own abeLayerConnect proc that performs what I need, but it can get slow with large number of polygons/islands and/with many points. I basically perform a standard abeLayerTouch, then for each tile from abeResult I check if it belongs to any islands from abeLayer1, if yes - I put them into a new abeLayer using abeLayerOrPtArray and continue with my expression using this new layer.

abeLayerTouch(abeLayer1 abeLayer2 abeResult)
;# Create array filled with tiles (threat tile as polygon for consistency)
ii=abeIslandIterator(abeResult)
tilesCount = ii->count
declare(aTiles[tilesCount])
for(i 0 tilesCount-1 aTiles[i] = ii->next)
;# Create array filled with polygons/islands
ii=abeIslandIterator(abeLayer1)
polysCount = ii->count
declare(aPolys[polysCount])
for(i 0 polysCount-1 aPolys[i] = ii->next)
;# Iterate over each polygon and check if a tile is touching.
;# If yes - add the polygon points to a new cumulutive abeLayer using abeLayerOrPtArray and 'remove' it from array. Remove the tile as well
;# because one tile can be part of exactly 1 polygon/island. Stop the loop and retry with new reduced number of polygons and tiles.
;# If no - just remove it from array -> none of the tiles were part from this particular polygon.
abePolys = abeNewLayer()
while(!zerop(tilesCount) || !zerop(polysCount)
  prog( (polygon tile)
    for( i 0 length(aPolys)-1
      polygon = aPolys[i]
      when(!eq(polygon 'unbound)
        for(k 0 length(aTiles)-1
          tile  = aTiles[k]
          when(!eq(tile 'unbound) && dbPointArrAnd(cv list(polygon) list(tile)) ; OR my custom made function which is actually faster
            abeLayerOrPtArray(polygon abePolys)
            aPolys[i] = 'unbound
            aTiles[k] = 'unbound
            tilesCount-=1
            polysCount-=1
            return(t)
          ); when
        ); for k
      ); when
      aPolys[i] = 'unbound
      polysCount-=1
    ); for i
  ); prog
); while
abePolys

Any tips and/or ideas are appreciated. Thank you!
Parents

  • Hi Aurel,

     Thank you for your input! I've tested your approach but I hit a hard show stopper with abeLayerOrPtArray() function, which appears to have a limit for maximum size of list of points per polygon (l_points) and throws an error for invalid list. I could not find the exact number, however from experiments it appears to be somewhere between 3K and 6K points. This limitation prevents the code from executing on mesh like (chocolate bar) shapes, because of sheer number of points as it threated as polygon. In some scenarios I have as much as 12K points. 
     I obviously cannot arbitrary slice the list of points to allowed size and process them in turns (or can I ?). So using abeLayerOrPtArray() is a no go and invalidates both yours and mine solutions for for such polygons... 

    On a side note: have you noticed performance improvement when you explicitly use abeRemoveLayer() call when you are done with certain geoLayer?


    Hey Sebastian,

     Thanks for chiming in. This is pretty much exactly what I am also trying to do. I do leverage SKILL++ class system, but I use strings instead of lists because A) this would be main way to supply input to the code and B) I personally think infix notation (A+B) is easier on the eyes for people not familiar with Lisp than prefix notation (+AB)  : )
     I am not familiar in details with the algorithm you are referring to, but I can search around the web for more detailed explanation and try it as alternative for mine.

     From few experiments, I couldn't conclusively conclude whether abeIslandIterator() (or how geoLayer data is presented) doesn't at least follow some logic when you go over the islands. In my test, the polygon with most points was never last in the list. This is just me thinking if I can reap any benefit from choosing reverse order of traversing in case I have to keep with my solution.

Reply

  • Hi Aurel,

     Thank you for your input! I've tested your approach but I hit a hard show stopper with abeLayerOrPtArray() function, which appears to have a limit for maximum size of list of points per polygon (l_points) and throws an error for invalid list. I could not find the exact number, however from experiments it appears to be somewhere between 3K and 6K points. This limitation prevents the code from executing on mesh like (chocolate bar) shapes, because of sheer number of points as it threated as polygon. In some scenarios I have as much as 12K points. 
     I obviously cannot arbitrary slice the list of points to allowed size and process them in turns (or can I ?). So using abeLayerOrPtArray() is a no go and invalidates both yours and mine solutions for for such polygons... 

    On a side note: have you noticed performance improvement when you explicitly use abeRemoveLayer() call when you are done with certain geoLayer?


    Hey Sebastian,

     Thanks for chiming in. This is pretty much exactly what I am also trying to do. I do leverage SKILL++ class system, but I use strings instead of lists because A) this would be main way to supply input to the code and B) I personally think infix notation (A+B) is easier on the eyes for people not familiar with Lisp than prefix notation (+AB)  : )
     I am not familiar in details with the algorithm you are referring to, but I can search around the web for more detailed explanation and try it as alternative for mine.

     From few experiments, I couldn't conclusively conclude whether abeIslandIterator() (or how geoLayer data is presented) doesn't at least follow some logic when you go over the islands. In my test, the polygon with most points was never last in the list. This is just me thinking if I can reap any benefit from choosing reverse order of traversing in case I have to keep with my solution.

Children
  • in reply to BorisD

    About abeRemoveLayer I haven't noticed anything but I haven't try neither...

    I guess you could use the profilers to check if it increases the performances. It might be interesting to do but should require meaningful testcases (your layouts seem complex enough though)

    To me the behaviour I expect is just for Virtuoso to make the generated layers available for the garbage collector to clear them when memory is required

    And from my developer point of view I want my function to act as a black box which just does what is defined in its docstring and does not pollute its environment

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.