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

M

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 wrote, on 03/09/11 14:44:
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
Click to expand...
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
 
On Mar 14, 4:52 pm, Andrew Beckett <andr...@DcEaLdEeTnEcTe.HcIoSm>
wrote:
Marcel Preda wrote, on 03/09/11 14:44:



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,

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                      *
*           Seehttp://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
Click to expand...
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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top