Creation of holes and no holes shapes

[nsluhrs]

This is a feature request:

I have a need in several of my projects to generate shapes from holes in polygons and to generate shapes with those holes removed. Currently I am using dbLayerHoles and dbLayerNoHoles respectively in cadence virtuoso, but it seems like the clipper library's simplify polygon method would enable a very similar functionality. This would be advantageous because it would avoid the need for additional processing to be done prior to export from cadence. I can explore setting this up myself but due to my lack of experience with C++ I am concerned this might very difficult for me to do.

I have a few methods in mind. When I use the pyclipper bindings to run simplify polygons, it returns both the outer shape (NoHoles) and the inner shapes (Holes) however it didn't seem to have any promises of the order of appearance. Additionally it has the ability to simplify a list of polygons but then I would need to determine which polygons are outer and which are inner and which inner belong to which outer which i think would likely be at least N^2. Any advice on how to implement this would be helpful. My current work around is to get the bounding box of a shape and subtract the original shape, this sort of gets the holes but also gets some extra bits on the edges which is undesirable. Of course this also fails to get the no holes shape except in the sense that the bounding box doesn't have any holes.

[nmz787-intel]

can you post a picture of what you want to get? simple powerpoint or napkin drawing. When you say "simplify" do you mean reduce the number of points? Would you expect it to be XOR clean with the non-simplified shape, or is some 'resolution loss' acceptable (i.e. approximating a circle with an N-gon)?

[nmz787-intel]

it sounds like you may be looking for filtering a collection of polygons into two sets, one of polygons with holes, one of polygons without holes? I think you may be able to do that by checking if a polygon ever has the same point more than once.

my opinion based on the Cadence docs on dbLayerNoHoles:

Returns a list of new objects from those areas consisting of all the original shapes of the input
list without holes. A hole is an area created when the perimeter of a polygon touches itself,
enclosing an area that is not the polygon

[nsluhrs]

Here is some demo code was testing out. This might actually be a fix, but it would be much nicer if I didn't have to also use the standalone pyclipper library since I found that converting between representations can be very expensive

import gdstk
from IPython.display import display, SVG
import tempfile
import os
import pprint

# some boilerplate funcitons I use for visulising things in jupyter 
def show_cell(cell):
    with tempfile.NamedTemporaryFile(delete=False) as temp:
        name=temp.name
    cell.write_svg(name)
    display(SVG(filename=name))
    os.remove(name)
def show_shape(*shapes):
    cell = lib.new_cell("temp")
    cell.add(*shapes)
    show_cell(cell)

# Create the geometry (a single rectangle) and add it to the cell.
rect = gdstk.rectangle((0, 0), (25, 5))
hole = gdstk.rectangle((2, 2), (6, 4))
hole2 = gdstk.rectangle((10, 2), (12, 4))
hole3 = gdstk.rectangle((16, 2), (18, 4))
hole4 = gdstk.rectangle((17,1),(22,3)
                        )
test_case_1 = gdstk.boolean(rect,[hole,hole2,hole3,hole4],'not')[0]
print('test case 1:')
show_shape(test_case_1)
test_case_2 = gdstk.boolean(test_case_1,[gdstk.rectangle((0,0),(1,2))],'not')[0]
print('test case 2:')
show_shape(test_case_2)

import pyclipper

print('running pyclipper.SimplifyPolygon yeilds a list of new shapes')
print('It seems like the last one may always be the outer shape but I\'m not sure')
print('test case 1:')
demo_cell = gdstk.Cell('demo')
simplified = pyclipper.SimplifyPolygon(test_case_1.points)
holes = simplified[:-1]
pprint.pprint(simplified)
for shape in holes:
    poly = gdstk.Polygon(shape,layer=0)
    demo_cell.add(poly)
poly = gdstk.Polygon(simplified[-1],layer=1)
demo_cell.add(poly)
show_cell(demo_cell)

print('test case 2:')

demo_cell = gdstk.Cell('demo')
simplified = pyclipper.SimplifyPolygon(test_case_2.points)
pprint.pprint(simplified)
holes = simplified[:-1]
for shape in holes:
    poly = gdstk.Polygon(shape,layer=0)
    demo_cell.add(poly)
poly = gdstk.Polygon(simplified[-1],layer=1)
demo_cell.add(poly)
show_cell(demo_cell)
print('the partial solution I am using now')
bbox=gdstk.rectangle(*test_case_2.bounding_box())
holes = gdstk.boolean([bbox],[test_case_2],'not')
show_shape(*holes)

The output of this: Obviously I ran the work around with testcase 2 since it actually works fine for test case 1 Also while the simplify function works nicely on single shapes it ends up unclear which ones are the outsides if you use the multi shape version SimplifyPolygons

[nmz787-intel]

This works for me, maybe your real use-case is more complex?

import gdstk
lib = gdstk.Library()
cell1 = lib.new_cell('cell1')

rect = gdstk.rectangle((0, 0), (25, 5))
hole = gdstk.rectangle((2, 2), (6, 4))
hole2 = gdstk.rectangle((10, 2), (12, 4))
hole3 = gdstk.rectangle((16, 2), (18, 4))
hole4 = gdstk.rectangle((17,1),(22,3))

test_case_1 = gdstk.boolean(rect,[hole,hole2,hole3,hole4],'not')
assert len(test_case_1)==1
test_case_1 = test_case_1[0]

cell1.add(test_case_1)

# get the holes
holes = gdstk.boolean(rect,test_case_1,'not', layer=1)

[cell1.add(h) for h in holes]
lib.write_oas('hole_test.oas')

[nsluhrs]

I need to be able to handle arbitrary shapes, your example seems to behave like the work around if I'm not mistaken. The desired behavior would not return hole 4. Imagine a diamond with a hole in the center, this would result in 5 "holes" by the work around method and 1 hole by the simplification method.

[nmz787-intel]

Hole 4 merged into Hole 3... they're both holes. Didn't you want to obtain ALL the holes? A diamond with a hole seems like there'd only be 1 single hole. Here is the proof of that:

import gdstk
lib = gdstk.Library()#unit=unit_value, precision=precision)
cell1 = lib.new_cell('cell1')

diamond_outer=  gdstk.regular_polygon((0, 0), side_length=10, sides=10)
diamond_inner=  gdstk.regular_polygon((0, 0), side_length=8, sides=10)
diamond_with_hole = gdstk.boolean(diamond_outer, diamond_inner, 'not')

assert len(diamond_with_hole)==1
diamond_with_hole = diamond_with_hole[0]
cell1.add(diamond_with_hole)

holes = gdstk.boolean(diamond_outer, diamond_with_hole,'not', layer=1)
assert len(holes)==1, len(holes)
[cell1.add(h) for h in holes]

lib.write_oas('diamond_hole.oas')   

maybe this example is more helpful for arbitrary shapes?

import gdstk
lib = gdstk.Library()
cell1 = lib.new_cell('cell1')

rect_without_hole = gdstk.rectangle((100, 100), (125, 105))
cell1.add(rect_without_hole)

rect_near_diamond = gdstk.rectangle((12.5, 12.5), (14.5, 14.5))
cell1.add(rect_near_diamond)

diamond_outer=  gdstk.regular_polygon((0, 0), side_length=10, sides=10)
diamond_inner=  gdstk.regular_polygon((0, 0), side_length=8, sides=10)
diamond_with_hole = gdstk.boolean(diamond_outer, diamond_inner, 'not')
assert len(diamond_with_hole)==1
cell1.add(diamond_with_hole[0])

def has_holes(p):
    point_set = set([(pt[0],pt[1]) for pt in p.points])
    return len(point_set)!=len(p.points)

def get_holes(p):
    bb = gdstk.rectangle(*p.bounding_box())
    bb_pts = bb.points
    result = gdstk.boolean(bb, p, 'not', layer=1)
    results_not_touching_bb = []
    for r in result:
        common_points = [tuple(pt)==tuple(other_pt) for pt in r.points for other_pt in bb_pts]
        if not any(common_points):
            results_not_touching_bb.append(r)
    return results_not_touching_bb

polygons_with_holes = [p for p in cell1.polygons if has_holes(p)]
assert len(polygons_with_holes)==1

holes = []
for p in polygons_with_holes:
    holes.extend(get_holes(p))
assert len(holes)==1, len(holes)
[cell1.add(h) for h in holes]

lib.write_oas('hole_finder.oas')

[heitzmann]

@nsluhrs Here's a possible solution:

import gdstk

lib = gdstk.Library()
demo_cell = lib.new_cell("DEMO")

outer = gdstk.boolean(
    gdstk.rectangle((0, 0), (25, 5)), gdstk.rectangle((0, 0), (1, 2)), "not"
)

holes = [
    gdstk.rectangle((2, 2), (6, 4)),
    gdstk.rectangle((10, 2), (12, 4)),
    gdstk.rectangle((16, 2), (18, 4)),
    gdstk.rectangle((17, 1), (22, 3)),
]

# Create shape with holes
original = gdstk.boolean(outer, holes, "not", layer=0)[0]

# Use bounding box method to get holes + extra bits
bb = original.bounding_box()
box = gdstk.rectangle(*bb)
diff = gdstk.boolean(box, original, "not", layer=1)

# Use an outer shell to check which polygons are really holes
shell = gdstk.boolean(
    gdstk.rectangle((bb[0][0] - 0.1, bb[0][1] - 0.1), (bb[1][0] + 0.1, bb[1][1] + 0.1)),
    box, "not", layer=2)[0]

holes = []
clips = []
for polygon in diff:
    # Real hole do not intersect the outer shell
    if gdstk.any_inside(polygon.points, shell):
        clips.append(polygon)
    else:
        holes.append(polygon)

filled_polygon = gdstk.boolean(box, clips, "not", layer=3)[0]

# Original in layer 0, shell in 2, holes in 1, filled original in 3
demo_cell.add(original, shell, *holes, filled_polygon)

lib.write_gds("HOLES.GDS")

The idea is that what differentiates a hole from an external clipping off the bounding box is the adjacency with the bounding box edges. It's not an elegant solution, but I think it should work for any non-degenerate cases.

The ideal solution would be to get the results from the boolean operation before connecting the holes to their outer boundary, but currently there's no way to skip this step. I'll leave this issue open and try to implement this feature if/when I have more time, unless anyone wants to give it a try and start a PR.

[nsluhrs]

So I've been continuing to work on this in my spare time and came up with a bit of a code abomination, I haven't compiled it yet but I think the base logic is fine and my ide doesn't see any obvious errors yet. Wouldn't surprise me if there was a memory leak or some such as I don't actually know c++. I also designed it with the triple nested array so that I could have the holes that correspond to each polygon and handle cases with recursive holes, which while a reasonable thing to forbid, I would if possible like to support.

ErrorCode complete_holes(const Array<Polygon*>& polygons, bool use_union, double scaling,
                         Array<Array<Array<Polygon*>*>*>& result) {
    ErrorCode errorcode = ErrorCode::NoError;
    // this converts the incoming polygon objects to clipperlib paths
    ClipperLib::Paths original_polys = polygons_to_paths(polygons, scaling);
    if (use_union) {
        ClipperLib::Clipper clpr;
        clpr.AddPaths(original_polys, ClipperLib::ptSubject, true);
        ClipperLib::PolyTree solution;
        clpr.Execute(ClipperLib::ctUnion, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
        ClipperLib::PolyNode* node = solution.GetFirst();
        Array<Array<Polygon*>*> shape_res;
        // grabs every non-hole polygon and their corresponding holes
        // First element is the outer shape 2nd and onward is holes
        // Cases with shapes in holes or orther messy things will be
        // separated out into different insnstances
        while (node) {
            if (!node->IsHole()) {
                Array<Polygon*> node_res;
                node_res.append(path_to_polygon(node->Contour, scaling));
                ClipperLib::PolyNode* child;
                for (int child_idx = 0; child_idx < node->ChildCount(); ++child_idx) {
                    child = node->Childs[child_idx];
                    node_res.append(path_to_polygon(child->Contour, scaling));
                    // NOTE If we see polygon that is not a hole here we have
                    // an issue
                    if (!child->IsHole()) errorcode = ErrorCode::BooleanError;
                }
                shape_res.append(&node_res);
            } else {
                node = node->GetNext();
            }
        }
        result.append(&shape_res);
    } else {
        for (ClipperLib::Paths::size_type i = 0; i < original_polys.size(); ++i) {
            ClipperLib::Clipper clpr;
            clpr.AddPath(original_polys[i], ClipperLib::ptSubject, true);
            Array<Array<Polygon*>*> shape_res;
            ClipperLib::PolyTree solution;
            clpr.Execute(ClipperLib::ctUnion, solution, ClipperLib::pftNonZero,
                         ClipperLib::pftNonZero);
            ClipperLib::PolyNode* node = solution.GetFirst();
            // grabs every non-hole polygon and their corresponding holes
            // First element is the outer shape 2nd and onward is holes

            while (node) {
                if (!node->IsHole()) {
                    Array<Polygon*> node_res;
                    node_res.append(path_to_polygon(node->Contour, scaling));
                    ClipperLib::PolyNode* child;
                    for (int child_idx = 0; child_idx < node->ChildCount(); ++child_idx) {
                        child = node->Childs[child_idx];
                        node_res.append(path_to_polygon(child->Contour, scaling));
                        // NOTE If we see polygon that is not a hole here we have
                        // an issue
                        if (!child->IsHole()) errorcode = ErrorCode::BooleanError;
                    }
                    shape_res.append(&node_res);
                } else {
                    node = node->GetNext();
                }
            }
            result.append(&shape_res);
        }
    }
    return errorcode;
}

I have also been thinking about creating a more normal function that just does n holes like the comment in the issue mentioned earlier. We could easily get that no_holes just by getting the children of the first (the empty one) node of the polytree. Getting just the holes might be a bit harder. probably fastest to xor the shape with the no_holes case of itself. Those could also follow the format of the other cases where it returns a single flat array of polygons. On a side note this was an EXTREMELY useful function for testing this.

sizes= np.array([8,6,4,2])
def recursive_holes(sizes):
    yz=np.array([1,0])
    my_square = get_square(sizes[0],len(sizes)%2)
    if len(sizes)==1:
        return my_square
    else:
        mid = recursive_holes(sizes[1:])
        return np.concatenate([my_square[:2],my_square[1:2]*yz,mid[0:1]*yz,mid,mid[-1:]*yz,my_square[-2:-1]*yz,my_square[2:]])
        #return np.concatenate([my_square[:2],mid,my_square[2:]])
shape = recursive_holes(sizes)    

I plan to eventually have this be a PR at least for the basic no_holes and holes cases.