Open ycrichard opened 5 years ago
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.
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.
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');
@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.
Can you send it to me?
Ulf
-- Ulf GRIESMANN \ +1 301 339 4962 Somewhere on Earth...
On Sun, Dec 18, 2022, 08:48 ycrichard @.***> wrote:
@houxianfei https://github.com/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.
— Reply to this email directly, view it on GitHub https://github.com/ulfgri/gdsii-toolbox/issues/3#issuecomment-1356802423, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACEGLNFLZRIIXRU7VTMIDYTWN4I4BANCNFSM4ISAOAPA . You are receiving this because you commented.Message ID: @.***>
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:
很抱歉,代码具有局限性,没考虑到这种情况,后续有机会我再想想更好的解决方案。
不过这个问题可以换一种写法
% 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');
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');
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');
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');
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
@houxianfei hello, 您修改后的代码对于一个结构中只有一个hole的话很好用,但如果有两个或以上的hole的话就开始有问题了,如下例:这里一个方形结构中理论上有两个方孔,但实际画出来的版图只有一个孔,请问下有没有解决办法呢?
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');
Unfortunately, there isn't an easy solution. The root problem is that the Clipper library used for polygon algebra has a broader definition of polygons than the GDSII standard. In GDSII all polygons must be strictly simple. The toolbox doesn't have a way to convert (cut up) complex polygons into simple ones. I have looked "all over the Internet" in vain to find the missing pieces, and I never had the time to write them myself.
Ulf
-- Ulf GRIESMANN \ +1 301 339 4962 Somewhere on Earth...
On Thu, Aug 29, 2019, 06:13 ycrichard @.***> wrote:
Hello,
I would like know if there 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 exists 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?
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ulfgri/gdsii-toolbox/issues/3?email_source=notifications&email_token=ACEGLNHCROVLBROS2OA2YFTQG6OM7A5CNFSM4ISAOAPKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HIFAKDQ, or mute the thread https://github.com/notifications/unsubscribe-auth/ACEGLND2MSKPMGLWQODYEGDQG6OM7ANCNFSM4ISAOAPA .
@Billy6998 关于你的问题,目前算法上不够完善。如果只是为了实现功能,我的建议是改成下图版本。在写法上需要做约束:1、首先被减元素们不重叠;2、要减的元素需覆盖所有被减元素;3、写法上要求先把所有被减元素相加,最后统一给最大的元素减去; 例如上述的例子就应该写成 ge4 = ge1-(ge0+ge2);
关于被减元素重合,建议写成 ge4 = ge1 - poly_bool( ge0, ge2, 'or'); 参考这次回答
Hello,
I would like know if there is any easy solution to properly write boundary shape with holes. Here is a simple example case:
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?