-
-
Notifications
You must be signed in to change notification settings - Fork 78
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Creation of holes and no holes shapes #173
Comments
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)? |
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
|
This works for me, maybe your real use-case is more complex?
|
I need to be able to handle arbitrary shapes, your example seems to behave like the work around if I'm not mistaken. |
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:
maybe this example is more helpful for arbitrary shapes?
|
@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. |
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 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. |
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.
The text was updated successfully, but these errors were encountered: