polygons that contain coincident internal edges not flagged as odd_polygons

[d-m-bailey]

Other tools flag polygons that contain zero width portions as invalid, but klayout odd_polygons check does not flag these shapes.

Version 0.30.7

1. First create a loop shape path.

2. Then add a path.

3. merge. Notice that the lower-left rectangle has an internal upper edge.

4. Use partial to move the top edge of the hole. This shows the zero width portion hidden in 3 above.
   Merging the data eliminates any drc errors, but other tools flag the shape in step 3 as a bad polygon.

5. Using partial move again shows the two internal edges that constituted the zero width portion.

Is there a way to detect this (or better yet, prevent this from occuring during merge) in klayout?

CC: @H-Ojiro @jun1okamura

[Kazzz-S]

Hello,

To better understand this issue, I checked the polygon's vertex sequence.

As far as I can see, KLayout handles this geometry without problems; for example, both positive and negative sizing work as expected.

A polygon with a hole also requires coincident edges when represented as a single vertex sequence, in order to connect the outer contour to the hole.
From this point of view, I am not sure what makes the zero-width branch in this example problematic.

Does this particular coincident edge pair cause any actual problem during trapezoidal decomposition or mask-data fracturing?

I am asking purely out of technical interest.

Best regards,
Kazzz-S

[d-m-bailey]

@Kazzz-S thanks for the detailed analysis!

You are correct in that klayout has no problems processing this shape.

The problem is that other tools do! Namely, Assura flags this in its data audit as an invalid shape.

From your diagram, this shape has 3 overlapping edges, 1-2(→), 5-6(←), and 11-12(←).

Although GDS does not prohibit invalid polygons, different tools may handle them in different ways.

ChatGPT's guidelines on safe polygons are

For a BOUNDARY, I would define a safe/simple GDS polygon as one that:

1. Has at least 3 distinct vertices.
2. Is explicitly closed (P[n] == P[0]).
3. Has nonzero area.
4. Has no zero-length edges (P[i] != P[i+1]).
5. Has no edge crossing another nonadjacent edge.
6. Has no edge overlapping another nonadjacent edge.
7. Does not retrace an edge in the opposite direction.
8. Ideally has no redundant collinear vertices.
9. Has no hole encoded directly inside the polygon.
10. Stays within the accepted vertex-count limit of your destination tool/foundry.

The shape in question violates number 7.

[Kazzz-S]

Hello @d-m-bailey,

Thank you for the explanation. I now understand the background of the issue.

Perhaps we can wait for Matthias's comments on this.

Best regards,
Kazzz-S

[klayoutmatthias]

Hi @Kazzz-S and @d-m-bailey,

Thanks for bringing up this topic. The way, holes are inserted in these kind of polygons is a little strange in KLayout, but the polygon is not wrong. This is a known problem and I think there has been a ticket for this case already.

Technically we have a cutline - formed by the hole (1->2 and 5->6) being coincident with the outline edge 11->12. The polygon is still orientable - i.e. not self-intersecting - as you can see if you imagine the 11->12 edge shifted somewhat lower. That is the most important property.

It's not easy to fix without an implied performance penalty for polygons with a very large number of holes. At least I have not found an acceptable solution the last time I looked at this problem. Maybe I should try again.

Matthias

[d-m-bailey]

@klayoutmatthias Thanks for looking into this. I checked for an outstanding issue, but couldn't find one.

Postponing an actual fix until later, would it be possible to add the detection of these shapes to the odd_polygons routine?
The users could then manually create non-merged shapes that only have at most 2 coincident edges (in the opposite direction).

One (as yet untested) implementation might be:

• For each edge

  • Calculate the nominal angle (for orthogonal shapes, 0 for 0 and 180 or 90 for 90 and -90).
  • Transform the points by rotating from the origin based on the nominal angle
  • The nominal angle and common coordinate are dictionary keys to a list of edges sorted on the lowest non-common coordinate
  • The edge list contains the minimum and maximum non-common coordinate and a flag to indicate if the points were reversed

• For each nominal angle

  • Run a scan line check on the associated list, keeping track of whether a forward or reversed edge is active.
  • Flag the shape if multiple forward or multiple reversed edges are active

There might be a simpler implementation, but I think the above would handle non-orthogonal shapes too.

Specs and working code available if needed (not tested on non-orthogonal shapes).