skill function to check if a shape s1 is inside shape s2

Discussion in 'Cadence' started by Marcel Preda, Mar 9, 2011.

  1. Marcel Preda

    Marcel Preda Guest

    Hi there,

    I'm looking for a function to check if a shape s1 is entirely inside
    of other shape s2.
    Both shapes are on the top a the current cell view.

    In the past I use to use:
    dbLayerInside(cv someDummyLayer list(s1) list(s2) ),
    but this function has 2 disadvantages:
    - cellview should be open in write/append mode
    - create some shapes (I delete them after checking the result) => slow
    execution especially if I have lots of such calls.


    Any idea ?

    Thank you,
    Marcel
     
    Marcel Preda, Mar 9, 2011
    #1
  2. Marcel Preda wrote, on 03/09/11 14:44:
    Marcel,

    Something like these functions could be used. You'll have to check that all
    points of shape 1 are inside the point list of shape 2. If they're not polygons,
    you'll have to form an equivalent list of points.

    There's also the leIsPointInsideFig() function which could be used (in my case I
    wrote these functions because the list of points which formed the second
    argument didn't correspond to a figure in the database).

    /*************************************************************************
    * *
    * (abPointInPolygon point points) *
    * *
    * Uses a ray casting approach to count if the number of intersections *
    * is even or odd. Even means the point is outside, and odd means inside. *
    * Returns t if inside the polygon. Note that the algorithm will *
    * ensure that for abutting polygons, it is only inside one of them. *
    * So, for a single polygon, needs to be combined with abPointOnBoundary *
    * to know if on boundary or inside. *
    * *
    * Based on Jordan curve theorem *
    * See http://en.wikipedia.org/wiki/Point_in_polygon *
    * *
    *************************************************************************/

    (defun abPointInPolygon (point points)
    (let (inside ptj
    (testX (car point))
    (testY (cadr point)))
    (setq ptj (car (last points)))
    (foreach pti points
    (when
    (and
    (nequal
    (greaterp (yCoord pti) testY)
    (greaterp (yCoord ptj) testY))
    (lessp
    testX
    (plus
    (quotient
    (times
    (difference (xCoord ptj) (xCoord pti))
    (difference testY (yCoord pti))
    )
    (difference (yCoord ptj) (yCoord pti))
    )
    (xCoord pti)
    )
    )
    )
    (setq inside (null inside))
    )
    (setq ptj pti)
    )
    inside
    )
    )

    /*****************************************************************
    * *
    * (abPointOnBoundary point points) *
    * *
    * Determines if a point is on the boundary of the polygon or not *
    * *
    *****************************************************************/

    (defun abPointOnBoundary (point points)
    (let (ptj iX iY jX jY
    (testX (car point))
    (testY (cadr point)))
    (setq ptj (car (last points)))
    (null
    (forall pti points
    (progn
    (setq iX (xCoord pti))
    (setq iY (yCoord pti))
    (setq jX (xCoord ptj))
    (setq jY (yCoord ptj))
    (setq ptj pti)
    (null
    (and
    ;------------------------------------------------------
    ; Next four check point is between the vertices
    ;------------------------------------------------------
    (geqp testX (min iX jX))
    (leqp testX (max iX jX))
    (geqp testY (min iY jY))
    (leqp testY (max iY jY))
    ;----------------------------------------------------------
    ; Colinear test
    ;----------------------------------------------------------
    (or
    ;--------------------------------------------------------
    ; Same X coord as both vertices
    ;--------------------------------------------------------
    (and (equal testX iX) (equal testX jX))
    ;--------------------------------------------------------
    ; Same Y coord as both vertices
    ;--------------------------------------------------------
    (and (equal testY iY) (equal testY jY))
    ;--------------------------------------------------
    ; at vertex
    ;--------------------------------------------------
    (and (equal testX iX) (equal testY iY))
    (and (equal testX jX) (equal testY jY))
    ;--------------------------------------------------------
    ; Gradient to both vertices the same (within tolerance)
    ;--------------------------------------------------------
    (and
    (nequal testX iX)
    (nequal testX jX)
    (nequal testY iY)
    (nequal testY jY)
    (lessp
    (abs
    (difference
    (quotient
    (difference testX iX)
    (difference testY iY))
    (quotient
    (difference testX jX)
    (difference testY jY))
    ))
    1e-6)
    ) ; and - gradient test
    ) ; or - colinear test
    ) ; and - is point on edge
    ) ; null - keep going until get a point on edge
    ) ; progn
    ) ; forall
    ) ; null
    ) ; let
    ) ; defun
     
    Andrew Beckett, Mar 14, 2011
    #2
  3. Marcel Preda

    Marcel Preda Guest

    Hi Andrew,

    Thank you for the reply.
    Funny thing: I've already wrote a function PointInsidePolygon using
    the same algorithm (odd/even intersection points number).
    Now I'm sure that I'm on the right track :)
    Code is almost the same, except that I do not use lisp syntax style.



    BR,
    Marcel
     
    Marcel Preda, Mar 15, 2011
    #3
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.