Home > Community > Forums > Custom IC SKILL > Determine a point is inside of a polygon or outside...

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# Determine a point is inside of a polygon or outside...

Last post Sun, Oct 28 2012 10:09 PM by Slayer. 5 replies.
 Started by Alvin Park 17 Oct 2012 12:38 AM. Topic has 5 replies and 1586 views
• #### Wed, Oct 17 2012 12:38 AM

• Alvin Park
• Joined on Thu, Mar 10 2011
• Posts 6
• Points 120
Determine a point is inside of a polygon or outside...
 Hi.... This is KT PARK in Korea. Do you have any SKILL Command or code to determine a point is inside of a polygon or outside at Virtuoso Layout Suit?  dbLayerInside or dbLayerOutside does not help.... T_T
• Post Points: 20
• #### Wed, Oct 17 2012 1:29 AM

Re: Determine a point is inside of a polygon or outside...
 You could use the leIsPointInsideFig() - this will determine whether a specified point is inside the figure represented by a database object (so a polygon, rectangle, path etc). Or another approach would be to use the CCSpointInPolygon() function defined in my solution 11024326 (note that the full solution is a bit superflous now because it's a built-in feature in IC615, but it's useful as an exercise in seeing how it was done before it became available).This function is useful if you have a polygon represented by a list of points rather than an actual database object.Regards,Andrew.
• Post Points: 20
• #### Wed, Oct 17 2012 6:51 PM

• Alvin Park
• Joined on Thu, Mar 10 2011
• Posts 6
• Points 120
Re: Determine a point is inside of a polygon or outside...
 Thank you Andew. leIsPointInsideFig() works good in my SKILL.
• Post Points: 20
• #### Fri, Oct 26 2012 6:03 AM

• Slayer
• Joined on Thu, Jan 13 2011
• Posts 29
• Points 310
Re: Determine a point is inside of a polygon or outside...
 There is my small function, instead leIsPointInsideFig()u can use my function in no graph mode and modify: ;-; Arguments:   n_x    - x coord for cheking point;-;         n_y    - y coord for cheking point;-;         l_points - points of shape;-;  ;-; Return value: list of points;-;  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;procedure(IsPointInPolygon(n_x n_y l_points)    let( (n b1 b2 b_flag xpi ypi i)               n = length(l_points);    xpi = declare(xpi[n+1]);    ypi = declare(ypi[n+1]);    ;create array with x and y points    for(i 1 n-1           xpi[i] = car(nthelem(i l_points));       ypi[i] = cadr(nthelem(i l_points));    );end for        xpi[0] = car(nthelem(n l_points));    ypi[0] = cadr(nthelem(n l_points));          i = 0;    b_flag = nil;    while(i <= n-2         b1 = (n_y > ypi[i]);         b2 = (n_y <= ypi[i+1]);          if( !((b1 && !b2) || (b2 && !b1)) then           if( n_x-xpi[i] < (n_y-ypi[i])*(xpi[i+1]-xpi[i])/(ypi[i+1]-ypi[i]) then         ;dprint("a vot her znaet");             b_flag = !b_flag;           )         )     i++;    )        b_flag;           );end let);procedure.
• Post Points: 20
• #### Fri, Oct 26 2012 7:47 AM

Re: Determine a point is inside of a polygon or outside...
 The fundamental algorithm looks very similar to my CCSpointInPolygon implementation in the solution I reference above - here's the same function with an "ab" prefix (I tend to convert the code to use a Cadence Customer Support prefix when publishing solutions). It's in a LISP-style, but you get the picture: /************************************************************************* * * * (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 ) ) The one thing that's unnecessary in the code above is the conversion of the list into arrays - and in fact the populating of the arrays is inefficient as it uses a for loop together with nth. Most of the time that's probably not a big deal because the number of points in a polygon will often be small, but for large polygons the for loops will be O(N**2) rather than O(N) as it would have been if a foreach had been used.Kind Regards,Andrew.
• Post Points: 20
• #### Sun, Oct 28 2012 10:09 PM

• Slayer
• Joined on Thu, Jan 13 2011
• Posts 29
• Points 310
Re: Determine a point is inside of a polygon or outside...
 Thx to u Andrew forthe intresting information.
• Post Points: 5