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

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

 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 1579 views
Page 1 of 1 (6 items)
Sort Posts:
  • Wed, Oct 17 2012 12:38 AM

    • Alvin Park
    • Not Ranked
    • Joined on Fri, Mar 11 2011
    • Posts 6
    • Points 120
    Determine a point is inside of a polygon or outside... Reply

    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... Reply

    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
    • Not Ranked
    • Joined on Fri, Mar 11 2011
    • Posts 6
    • Points 120
    Re: Determine a point is inside of a polygon or outside... Reply

     Thank you Andew.

     leIsPointInsideFig() works good in my SKILL.

    • Post Points: 20
  • Fri, Oct 26 2012 6:03 AM

    • Slayer
    • Top 500 Contributor
    • Joined on Fri, Jan 14 2011
    • Posts 29
    • Points 310
    Re: Determine a point is inside of a polygon or outside... Reply

     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... Reply

    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
    • Top 500 Contributor
    • Joined on Fri, Jan 14 2011
    • Posts 29
    • Points 310
    Re: Determine a point is inside of a polygon or outside... Reply

     Thx to u Andrew forthe intresting information.

    • Post Points: 5
Page 1 of 1 (6 items)
Sort Posts:
Started by Alvin Park at 17 Oct 2012 12:38 AM. Topic has 5 replies.