Home > Community > Forums > Custom IC SKILL > Is there a way to get outer points of selected polygons?

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: *

 Is there a way to get outer points of selected polygons? 

Last post Tue, Nov 2 2010 2:58 AM by Andrew Beckett. 14 replies.
Started by kbhow 21 Oct 2010 11:42 PM. Topic has 14 replies and 4714 views
Page 1 of 1 (15 items)
Sort Posts:
  • Thu, Oct 21 2010 11:42 PM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Is there a way to get outer points of selected polygons? Reply

    Hi,

    Is there any SKILL codes which able to get the outer points of selected objects?

    I was trying to create a new function which may required to get the outer points of selected objects (polygon/rectangle/instances and etc). I want to get a list of points where i can use it to create a polygon which cover all selected objects.

    Example, let say i have selected 10 polygons, and i want a function to return me a list of outer points of my selected object. Can someone help?

    Thanks

    How

    • Post Points: 35
  • Sun, Oct 24 2010 4:45 AM

    • babji
    • Top 500 Contributor
    • Joined on Thu, Apr 23 2009
    • hyderabad, Andhra Pradesh
    • Posts 24
    • Points 360
    Re: Is there a way to get outer points of selected polygons? Reply

     You can do a union of all the selected objects bboxes. trBBoxUnion( geGetSelSet()~>bBox )

     

     procedure( trBBoxUnion( bBoxList )
    let( ( llxList llyList
    urxList uryList
    minllx minlly
    maxurx maxury
    )
    llxList = foreach( mapcar bBox bBoxList
    xCoord( lowerLeft( bBox )))
    llyList = foreach( mapcar bBox bBoxList
    yCoord( lowerLeft( bBox )))
    urxList = foreach( mapcar bBox bBoxList
    xCoord( upperRight( bBox )))
    uryList = foreach( mapcar bBox bBoxList
    yCoord( upperRight( bBox )))
    minllx = apply( 'min llxList )
    minlly = apply( 'min llyList )
    maxurx = apply( 'max urxList )
    maxury = apply( 'max uryList )
    list( minllx:minlly maxurx:maxury )
    ) ; let
    ) ; procedure
    trBBoxUnion( list( list(0:0 100:100) list(50:50 150:150)))

     

     

    • Post Points: 20
  • Mon, Oct 25 2010 1:30 PM

    • skillUser
    • Top 10 Contributor
    • Joined on Fri, Sep 19 2008
    • Austin, TX
    • Posts 2,571
    • Points 15,610
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi How,

    I presume that you are asking for the actual points of the resultant combined shape, rather than the overall bounding box?  I think that the easiest way to get this would be to use something like dbLayerAnd on the input shapes to create a temporary shape, get the points from this shape and then delete it when you're done with it. It may be a little clunky, but it would be simpler than other methods that I can think of. 

    Hope this helps,

    Lawrence.

    • Post Points: 20
  • Mon, Oct 25 2010 5:57 PM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi Pradesh,

    Thanks for your propose solution but this function only able to get the bounding box( bBox) of the selected objects. Thanks a lot.

    I was looking for a function which able to get the outer shape (polygon) for a selected object. It works similar like mark net, when you mark a net, it will highlight only the outer shape of the net, looks like big highlighted polygon. My intention to get the this big highlighted polygon's points and proceed for next step.

    Thanks :)

    • Post Points: 5
  • Mon, Oct 25 2010 6:01 PM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi Lawrewnce,

    Thanks for your propose solution. I did try several approach including dbLayerAnd but it doesn't work when selected shapes is not overlapping each other. As a result, this function only creates individual shapes.

    Any idea? I can't figure out any way in getting this done. Hoping there are ideas from anyone in this forum. Thanks a bunch.

    • Post Points: 20
  • Tue, Oct 26 2010 1:06 AM

    • StefanSL
    • Top 150 Contributor
    • Joined on Mon, Nov 2 2009
    • Reutlingen, Baden-Wurttemberg
    • Posts 47
    • Points 860
    Re: Is there a way to get outer points of selected polygons? Reply
    Hi kbhow,

    regarding the boolean operation, i assume dbLayerOR should be more useful than ANDcause you want to combine all your selected objects; of course, just ORing the shapes will result in a shape covering all your shapes but you might get more than one shape and your shape might have holes in it.

    If i understand your needs correctly, the keyword "convex hull" might be what you are looking for:  the minimum convex polygon including all your shapes.

    Starting point would be a list of all points of all your selected shapes; searching for "convex hull", "computational geometry" should lead to an algorithm to get the convex hull from this set of points; possibly you should export the problem to a perl-script for better performance and access to trigonometric functions.

    If the convex hull is too large, the problem will become much more complicated cause you'd have to define how concave, how "deep" concave the polygon may be.

    Kind regards

    Stefan
    • Post Points: 20
  • Tue, Oct 26 2010 2:01 AM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi Stefan,

    Sorry that i can't really get what you means. Any where thanks.

    I was trying to get outer shape of selected objects as below.

                        ___                                                             _ _ _

                       |_ _|                                                           |       |

             ____        ___                                                ___ |       |___

     ___|        |     |      |____                            _ __|                         |____

    |__  ___  |      |_______|           =>           |______________________|

     

    Hoping this help to make my question clear. Thanks

    • Post Points: 20
  • Tue, Oct 26 2010 2:34 AM

    • StefanSL
    • Top 150 Contributor
    • Joined on Mon, Nov 2 2009
    • Reutlingen, Baden-Wurttemberg
    • Posts 47
    • Points 860
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi kbhow,

    the "convex hull" would look like this:

                        ___                                                        _ _ _
                      
    |_ _|                                                    /         \

             ____        ___                                               /             \

     ___|        |     |      |____                                  /                   \

    |__  ___  |      |_______|           =>                 |_ ________  |

     

    just the outer points are connected in a way that all points are inside the new
    polygon; an interesting geometrical problem, there are some algorithms available.

    Possibly you could achieve a result similar to your drawing by upsizing all shapes
    to an intermediate layer by an amount that's sufficient to close all gaps, the shapes will merge,
    then downsizing by the same amount, the outlines should look like your drawing but
    the gaps will stay closed.

    Size resp. leHiSize() will not merge the shapes,
    dbLayerSize() or "Tools - Layer generation ... GROW" should do the job.

     kind regards

    Stefan

     

     

    • Post Points: 20
  • Mon, Nov 1 2010 9:02 AM

    Re: Is there a way to get outer points of selected polygons? Reply

    How,

    A good place to start would be with http://en.wikipedia.org/wiki/Convex_hull and  http://en.wikipedia.org/wiki/Convex_hull_algorithms

    That said, I'm not sure it's quite a convex hull you want, because I suspect you want it to follow the outer edges rather than being like an elastic band around all the outermost points.

    Regards,

    Andrew.

    • Post Points: 20
  • Mon, Nov 1 2010 7:01 PM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Re: Is there a way to get outer points of selected polygons? Reply

     Hi Andrew,

    Thanks for the sharing.

    Ya, you're right.I actually want the outer edge rather than convex. Do you have any idea? At the same time, i'll go through the link the you share, hoping can get some hint or inspiration from that.

    Regards,

    How

    • Post Points: 35
  • Tue, Nov 2 2010 1:55 AM

    • StefanSL
    • Top 150 Contributor
    • Joined on Mon, Nov 2 2009
    • Reutlingen, Baden-Wurttemberg
    • Posts 47
    • Points 860
    Re: Is there a way to get outer points of selected polygons? Reply

    Hello How,

    besides of the convex hull approach, my second proposal was to apply a
    upsizing-/downsizing-cycle to your shapes, did you already try if this fulfills your needs?

    si=geGetSelectedSet()
    cvid = geGetEditCellView()
    stmp=dbLayerSize(cvid "TMPLAYER" si 3.5)
    so=dbLayerSize(cvid "TGTLAYER" stmp -3.5)

    applying a suitable sizing instead of 3.5um will merge your
    shapes, even from more than one layer, into one shape;
    downsizing this shape by the same amount will result in
    a shape that should do what you want...

    kind regards

    Stefan

     

    • Post Points: 20
  • Tue, Nov 2 2010 2:33 AM

    • kbhow
    • Top 75 Contributor
    • Joined on Thu, May 7 2009
    • Penang, Pulau Pinang
    • Posts 120
    • Points 2,045
    Re: Is there a way to get outer points of selected polygons? Reply

    Hi Stefan,

    Cool. This way never get into my mind, but i believe this will solve my problem. I'll play around with this approach.

    Thanks a lot.

    • Post Points: 20
  • Tue, Nov 2 2010 2:39 AM

    Re: Is there a way to get outer points of selected polygons? Reply
    Hi How,

    If all the shapes have orthogonal edges (i.e. only 90 degree angles), then all you'd have to do is create an additional vertex between each pair of adjacent points on the convex hull (assuming they do not already share the same X or Y coordinate) representing an "L" shape (the L would have to be towards the inside of the resulting polygon). Not _too_ difficult to do that.

    Otherwise you'd probably need to do this:

    1. Merge all the shapes (do an Or of them all)
    2. Collect all the points and a reference to the merged shape it came from.
    3. Compute the convex hull of all the points
    4. For each point in the convex hull, find the original vertex on the merged shapes and then take the line from that vertex to the adjacent point on merged shape, and do this again for the adjacent point on the convex hull, and find the intersection of the two lines to create the additional point.

    The last step needs to be done carefully to ensure you get the intersection of the right pair of lines, but it shouldn't be too hard.

    So fundamentally it's a refinement of the convex hull, rather than a completely different algorithm.

    Regards,

    Andrew
    • Post Points: 5
  • Tue, Nov 2 2010 2:41 AM

    • StefanSL
    • Top 150 Contributor
    • Joined on Mon, Nov 2 2009
    • Reutlingen, Baden-Wurttemberg
    • Posts 47
    • Points 860
    Re: Is there a way to get outer points of selected polygons? Reply

     Hi How,

    if one of the initial shapes is located far off, you may run into a problem,
    using the same value for upsizing and downsizing can result in
    more than one shape, cause the downsize step could remove the interconnect
    again. You should check the result of your operation if
    it's really just one shape.

    regards

    Stefan

     

    • Post Points: 20
  • Tue, Nov 2 2010 2:58 AM

    Re: Is there a way to get outer points of selected polygons? Reply

    To be slightly pedantic, even if it is effectively one shape, it's possible that the dbLayer functions may return more than one shape if there are too many points.

    There's an optional argument to dbLayer* functions which specifies the maximum number of vertices - and the default is (I think, if my memory is correct) 200. Beyond that it automatically splits into pieces. This was done because some formats historically have limits on the number of vertices (e.g. stream format had a historical limit of 200 points per polygon).

    So counting the number of shapes produced may not be sufficient to detect gaps if there are lots of vertices in the resulting shape (if it has an outline like the coast of Norway ;-> ). That said, I believe that the upper limit is enormous (not even sure there is an upper limit) in OA versions is very high; in CDB the upper limit of number of vertices per polygon is 4000 (I think). So you may be able to use Stefan's approach still if you have a relatively small set of data to find the "hull" for.

    Regards,

    Andrew.

     

    • Post Points: 5
Page 1 of 1 (15 items)
Sort Posts:
Started by kbhow at 21 Oct 2010 11:42 PM. Topic has 14 replies.