Skip to content
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.

Sign up for GitHub

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

Jump to bottom

boundary with holes #3

Open
ycrichard opened this issue Aug 29, 2019 · 11 comments
Open

boundary with holes #3

ycrichard opened this issue Aug 29, 2019 · 11 comments

Comments

@ycrichard
Copy link

ycrichard commented Aug 29, 2019 •
edited
Loading

Hello,

I would like know if there is any easy solution to properly write boundary shape with holes.
Here is a simple example case:

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 =  [-1,-1; -1,1; 1,1; 1,-1; -1,-1]; 
xy2 = xy1/2;
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge3 = ge1-ge2;
gs(end+1) = ge3;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, 'basic.gds');

The resulting GDS does not have a hole, probably it is a known limitation in the current version.
I know that we can do a pre-triangulation, but in the cases with more complex holes, the triangulation is really not optimal.
Could you suggest any general method to split it into simple boundary elements?
@ulfgri
Copy link
Owner

ulfgri commented Aug 29, 2019

This is really caused by one piece of still missing functionality in the underlying Clipper library that is used implement the polygon algebra. What's missing in Clipper is a way to convert complex polygons (e.g. polygons with holes) into simple ones. Clipper has the beginnings of polygon simplification, but it currently can't simplify polygons with holes. If I knew a general way to do the simplification, it would already be part of the toolbox. Right now it's best to avoid any holes, e.g. by dividing the outer polygon before subtracting the hole, or similar strategies.

@euzada
Copy link

euzada commented Sep 17, 2020

I believe Holes are not allowed in GDSII, but "self touching" is legal, because the lines will not "self crossing" as explained in this website: https://www.artwork.com/gdsii/gdsii/page3.htm

Maybe the solution is to try to create an extra points to combine the edge of holes to the outside edge and have a close polygon. I am not good at programming to edit Clipper library. But I tested in Klayout. I added to boxes as describe in ycrichard example and I made a subtraction and finally I have a polygon with a hole with the "self touching" idea.

Polygon_With_hole

@houxianfei
Copy link

houxianfei commented Dec 18, 2022 •
edited
Loading

hello

1、在作者原有重载的gdsii-Toolbox\Basic@gds_element\minus.m函数中，还不支持hole的创建。针对这个问题，在minus.m中增加了一段代码，用于解决该问题。

function [gelm] = minus(gelm1, gelm2)
%function [gelm] = minus(gelm1, gelm2)
%
% Defines the '-' operator for the gds_element class, which 
% performs a Boolean 'notb' (set difference) operation with the polygons
% of boundary elements. All properties are inherited from gelm1.
%
% gelm1 :  input boundary element 1
% gelm2 :  input boundary element 2
% gelm  :  boundary element on the same layer as gelm1.

% Ulf Griesmann, NIST, April 2014

   % global variables
   global gdsii_uunit;

   % units must be defined
   if isempty(gdsii_uunit) 
       warning('undefined GDSII units');
       fprintf('\n  +-------------------- WARNING -----------------------+\n');
       fprintf('  | Units are not defined; setting uunit/dbunit = 1000.|\n'); 
       fprintf('  | Define units by creating the library object or     |\n'); 
       fprintf('  | by calling gdsii_units.                            |\n'); 
       fprintf('  +----------------------------------------------------+\n');
       udf = 1000;
   else
       udf = gdsii_uunit;      % conversion factor to db units
   end

   % check arguments
   if ~strcmp(get_etype(gelm1.data.internal), 'boundary') || ...
      ~strcmp(get_etype(gelm2.data.internal), 'boundary')
      error('gds_element.minus :  arguments of - must be boundary elements.');
   end

   % create output element
   gelm = gelm1;

   % apply boolean set operation
   [gelm.data.xy, hf] = poly_boolmex(gelm1.data.xy, gelm2.data.xy, ...
                                     'notb', udf);
   if any(hf)
      % warning('gds_element.minus :  a polygon with a hole was created.');
      gelm.data.xy = {};
      gelm.data.xy{1,1} = disAB(gelm1, gelm2);
   end
   
end


function pointA = disAB(gelm1, gelm2)

gelm1 = poly_cw(gelm1, 1);
gelm2 = poly_cw(gelm2, 0);

if length(gelm1.data.xy) ~= 1
        error('gds_element1 just one polygons');
end

num = length(gelm2.data.xy);
pointA = gelm1.data.xy{1,1};

for i = 1:num
    pointB = gelm2.data.xy{1,i};
    
    xA = pointA(:,1);
    yA = pointA(:,2);
    xB = pointB(:,1);
    yB = pointB(:,2);
    
    xAr = repmat( xA, size(1, numel(xB)) );
    yAr = repmat( yA, size(1, numel(yB)) );
    xBr = repmat( xB', size(1, numel(xA)) );
    yBr = repmat( yB', size(1, numel(yB)) );
    
    dis = sqrt( (xAr-xBr).^2 + (yAr-yBr).^2 );
    [~, ind] = min( dis(:) );
    [a, b] = ind2sub( size(dis), ind);
    
    pointA = [pointA(a:end, :); pointA(1:a, :); pointB(b:end, :); pointB(1:b, :)];
end
end

2、other：另外需要将 gdsii-Toolbox\Basic@gds_element\poly_cw.m中的笔误进行修正

% find the polygons to change
if makecw
    pch = find(cw==0); % find all CCW polygons
else
    pch = find(cl~=0); % find all CW polygons      **cl -> cw**
end

3、使用一楼提供的测试代码，最终结果如图

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2;
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge3 = ge1-ge2;
gs(end+1) = ge3;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, 'basic.gds');

image

@ycrichard
Copy link
Author

@houxianfei Thanks for the nice fix. I tested it, and it works even when two polygons have partial overlap. It would be great if you can make a pull request to the official repo.
Or maybe the owner can implement the idea here.

@ulfgri
Copy link
Owner

ulfgri commented Dec 18, 2022 via email

@ycrichard
Copy link
Author

Be aware there is still some limitation. With the solution from houxianfei, it only works for minus operation between 2 simple polygon. If I make another minus operation on top of the hole shape, it seems to do a XOR operation.

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];
xy3 = xy1/4+[0.5,0.5];
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge0 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge3 = ge1-ge2;     % 1st minus
ge4 = ge3-ge0;      % 2nd minus
gs(end+1) = ge4;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, 'basic.gds');

The result is as following:
image

@houxianfei
Copy link

很抱歉，代码具有局限性，没考虑到这种情况，后续有机会我再想想更好的解决方案。

不过这个问题可以换一种写法

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];
xy3 = xy1/4+[0.5,0.5];
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge0 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge3 = ge1 - poly_bool( ge0, ge2, 'or');
gs(end+1) = ge3;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, '!basic.gds');

image

@houxianfei
Copy link

try again

test1:

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];
xy3 = xy1/4+[0.5,0.5];
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge0 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge3 = ge1-ge2;     % 1st minus
ge4 = ge3-ge0;      % 2nd minus
gs(end+1) = ge4;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, '!basic.gds');

屏幕截图 2022-12-19 214110

test2: hole - hole

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];

xy3 = xy1/2+[0.5,0.5];
xy4 = xy1/4+[0.5,0.5];

% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge3 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge4 = gds_element('boundary', 'xy',xy4, 'layer',1);

ge5 = ge1-ge2;     % 1st minus
ge6 = ge3-ge4;      % 2nd minus

gs(end+1) = ge5 - ge6;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, '!basic.gds');

屏幕截图 2022-12-19 214401

test3: hole - hole

% create a structure to hold elements
gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];

xy3 = xy1/2+[0.4,0.4];
xy4 = xy1/4+[0.4,0.4];

% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge3 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge4 = gds_element('boundary', 'xy',xy4, 'layer',1);

ge5 = ge1-ge2;     % 1st minus
ge6 = ge3-ge4;      % 2nd minus

gs(end+1) = ge5 - ge6;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, '!basic.gds');

image

code update

gdsii-Toolbox\Basic@gds_element\minus.m

function [gelm] = minus(gelm1, gelm2)
%function [gelm] = minus(gelm1, gelm2)
%
% Defines the '-' operator for the gds_element class, which 
% performs a Boolean 'notb' (set difference) operation with the polygons
% of boundary elements. All properties are inherited from gelm1.
%
% gelm1 :  input boundary element 1
% gelm2 :  input boundary element 2
% gelm  :  boundary element on the same layer as gelm1.

% Ulf Griesmann, NIST, April 2014

   % global variables
   global gdsii_uunit;

   % units must be defined
   if isempty(gdsii_uunit) 
       warning('undefined GDSII units');
       fprintf('\n  +-------------------- WARNING -----------------------+\n');
       fprintf('  | Units are not defined; setting uunit/dbunit = 1000.|\n'); 
       fprintf('  | Define units by creating the library object or     |\n'); 
       fprintf('  | by calling gdsii_units.                            |\n'); 
       fprintf('  +----------------------------------------------------+\n');
       udf = 1000;
   else
       udf = gdsii_uunit;      % conversion factor to db units
   end

   % check arguments
   if ~strcmp(get_etype(gelm1.data.internal), 'boundary') || ...
      ~strcmp(get_etype(gelm2.data.internal), 'boundary')
      error('gds_element.minus :  arguments of - must be boundary elements.');
   end

   % create output element
   gelm = gelm1;

   % apply boolean set operation
   [gelm.data.xy, hf] = poly_boolmex(gelm1.data.xy, gelm2.data.xy, ...
                                     'notb', udf);
   if any(hf)
      gelm.data.xy = {};
      gelm.data.xy = disAB(gelm1, gelm2);
   end
   
end


function point = disAB(gelm1, gelm2)
    point = {}; % out point (cell)
    
    if length(gelm1.data.xy) ~= 1
            error('gds_element1 just one polygons');
    end
    
    gelm1 = poly_cw(gelm1, 1); % cw
    
    pointA = gelm1.data.xy{1,1};
    if pointA(1,:) == pointA(end); pointA(end, :) = []; end
    
    % create new gelm
    gelm3 = gelm1;
    gelm3.data.xy{1,1} = {};
    
    if poly_ishole(pointA)
        [pointA, gelm3.data.xy{1,1}] = findhole(pointA);
        gelm2 = poly_bool(gelm2, gelm3, 'or');
    end
    
    gelm2 = poly_cw(gelm2, 0); % ccw
    
    num = length(gelm2.data.xy);
    
    for i = 1:num
        
        pointB = gelm2.data.xy{1,i};
        if pointB(1,:) == pointB(end); pointB(end, :) = []; end
        
        xy = [];
        if poly_ishole(pointB)
            [xy, pointB] = findhole(pointB);
        end

        xA = pointA(:,1);
        yA = pointA(:,2);
        xB = pointB(:,1);
        yB = pointB(:,2);

        xAr = repmat( xA, size(1, numel(xB)) );
        yAr = repmat( yA, size(1, numel(yB)) );
        xBr = repmat( xB', size(1, numel(xA)) );
        yBr = repmat( yB', size(1, numel(yB)) );

        dis = sqrt( (xAr-xBr).^2 + (yAr-yBr).^2 );
        [~, ind] = min( dis(:) );
        [a, b] = ind2sub( size(dis), ind);
        pointA = [pointA(a:end, :); pointA(1:a, :); pointB(b:end, :); pointB(1:b, :)];
        
        if isempty(xy)
            point{end + 1} = pointA;
        else
            point{end + 1} = pointA;
            point{end + 1} = xy;
        end
        
    end
end

function  [pointA, pointB] = findhole(point)
    ind = find( point(2:end,1)==point(1,1) & point(2:end,2) == point(1,2));
    pointA = point(1:ind, :);
    pointB = point(ind+2:end, :);
end

function res = poly_ishole(point)
    ind = find( point(2:end,1)==point(1,1) & point(2:end,2) == point(1,2), 1);
    if isempty(ind)
        res = false;
    else
        res = true;
    end
end

gdsii-Toolbox\Basic@gds_element\poly_bool.m

function [bo] = poly_bool(ba, bb, op, varargin);
%function [bo] = poly_bool(ba, bb, op, varargin);
%
% poly_bool - method for boolean set algebra on 
%             boundary elements.
%
%             bo = poly_bool(ba, bb, op)
%          
%             IMPORTANT: user and database units must be defined
%             before calls to 'poly_bool' either by creating the 
%             library object or with a call to 'gdsii_units'.
%             This is necessary because the boolean operations
%             are performed on the database grid.
%
% ba :    input boundary element. If ba is a compound element
%         (i.e. contains more than one polygon) the boolean set
%         operation is applied to all polygons in sequence.
% bb :    2nd input boundary element (may be a compound element)
% op :    operation applied to the inputs:
%           'and'  -  intersection of both sets; points are in ba
%                     and also in bb
%           'or'   -  union of both sets; points are either in ba
%                     or bb. 
%           'xor'  -  points that are either in ba or in bb, but
%                     not in both sets.
%           'notb' -  set difference; points that are in ba and 
%                     not in bb.
% varargin :  property - value pairs that modify the properties of
%             the output boundary element. 
% bo :    output boundary element, the result of the boolean set
%         operation. Can contain more than one polygon. By default,
%         the output polygon is on the same layer as ba and has the 
%         same data type.
%
% Example:
%          out = poly_bool(square, circle, 'or', 'layer',10);
%       
%          returns a boundary element describing the set union of
%          two elements 'square' and 'circle'. The output element
%          is on layer 10.
%
% NOTES: 
% 1) Some operations can result in complex polygons containing holes.
% Since these are difficult to convert into simple polygons the
% function currently exits with an error when the output polygons are
% not all simple.
%
% 2) This function can use either the polygon clipper library by 
% Angus Johnson (www.angusj.com), or the General Polygon 
% Clipper library by Alan Murta (www.cs.man.ac.uk/~toby/gpc/).

% Initial version, Ulf Griesman, August 2012

% global variables
global gdsii_uunit;

% check arguments
if nargin < 3
   error('gds_element.poly_bool :  expecting at least 3 input arguments');
end

% only works with boundary elements
if ~strcmp(get_etype(ba.data.internal), 'boundary') || ...
   ~strcmp(get_etype(bb.data.internal), 'boundary')
   error('gds_element.poly_bool :  input elements must be boundary elements');
end

% units must be defined
if isempty(gdsii_uunit) 
   fprintf('%s', '\n  +-------------------- WARNING -----------------------+\n');
   fprintf('%s', '  | Units are not defined; setting uunit/dbunit = 1.   |\n'); 
   fprintf('%s', '  | Define units by creating the library object or     |\n'); 
   fprintf('%s', '  | by calling gdsii_units.                            |\n'); 
   fprintf('%s', '  +----------------------------------------------------+\n\n');
   duf = 1;
else
   duf = gdsii_uunit;      % conversion factor to db units
end

% apply boolean set operation
[xyo, hf] = poly_boolmex(ba.data.xy, bb.data.xy, op, duf);
if any(hf)
   ele1 = gds_element('boundary',  'xy', xyo{1,1});
   ele2 = gds_element('boundary',  'xy', xyo{1,2});
   ele = ele1 - ele2;
   xyo = ele.data.xy(1,1);
end

% create a boundary element for the output polygons
bo = ba;
bo.data.xy = xyo;

% add any property arguments
if ~isempty(varargin)
   bo.data.internal = set_element_data(bo.data.internal, varargin);
end
return

@Billy6998
Copy link

@houxianfei hello, 您修改后的代码对于一个结构中只有一个hole的话很好用，但如果有两个或以上的hole的话就开始有问题了，如下例：这里一个方形结构中理论上有两个方孔，但实际画出来的版图只有一个孔，请问下有没有解决办法呢？
Two_holes

gs = gds_structure('BASIC');
% create two closed polygons
xy1 = [-1,-1; -1,1; 1,1; 1,-1; -1,-1];
xy2 = xy1/2+[0,0];
xy3 = xy1/6+[0.7,0.7];
% create boundary elements and substract the second one
ge1 = gds_element('boundary', 'xy',xy1, 'layer',1);
ge2 = gds_element('boundary', 'xy',xy2, 'layer',1);
ge0 = gds_element('boundary', 'xy',xy3, 'layer',1);
ge3 = ge1-ge2;     % 1st minus
ge4 = ge3-ge0;      % 2nd minus
gs(end+1) = ge4;
% create a library to hold the structure
glib = gds_library('standard', 'uunit',1e-6, 'dbunit',1e-9, gs);
% finally write the library to a file
write_gds_library(glib, '!basic.gds');

@ulfgri
Copy link
Owner

ulfgri commented Oct 12, 2023 via email

@houxianfei
Copy link

@Billy6998 关于你的问题，目前算法上不够完善。如果只是为了实现功能，我的建议是改成下图版本。在写法上需要做约束：1、首先被减元素们不重叠；2、要减的元素需覆盖所有被减元素；3、写法上要求先把所有被减元素相加，最后统一给最大的元素减去； 例如上述的例子就应该写成 ge4 = ge1-(ge0+ge2);
image

关于被减元素重合，建议写成 ge4 = ge1 - poly_bool( ge0, ge2, 'or'); 参考这次回答
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@ycrichard @ulfgri @euzada @houxianfei @Billy6998