Decompose Constructive Solid Geometry into minimal regions
dl = decsg(gd,sf,ns)
dl = decsg(gd)
[dl,bt] = decsg(gd)
[dl,bt] = decsg(gd,sf,ns)
[dl,bt,dl1,bt1,msb] = decsg(gd)
[dl,bt,dl1,bt1,msb] = decsg(gd,sf,ns)
This function analyzes the Constructive Solid Geometry model (CSG model) that you draw. It analyzes the CSG model, constructs a set of disjoint minimal regions, bounded by boundary segments and border segments, and optionally evaluates a set formula in terms of the objects in the CSG model. We often refer to the set of minimal regions as the decomposed geometry. The decomposed geometry makes it possible for other Partial Differential Equation Toolbox™ functions to "understand" the geometry you specify. For plotting purposes a second set of minimal regions with a connected boundary is constructed.
The PDE app uses
decsg for many purposes.
Each time a new solid object is drawn or changed, the PDE app calls
be able to draw the solid objects and minimal regions correctly. The
Delaunay triangulation algorithm,
uses the output of
decsg to generate an initial
dl = decsg(gd,sf,ns) decomposes
the CSG model
gd into the decomposed geometry
The CSG model is represented by the Geometry Description matrix, and
the decomposed geometry is represented by the Decomposed Geometry
decsg returns the minimal regions that
evaluate to true for the set formula
sf. The Name
ns is a text matrix that relates the
gd to variable names in
dl = decsg(gd) returns all minimal
regions. (The same as letting
sf correspond to
the union of all objects in
[dl,bt] = decsg(gd) and
= decsg(gd,sf,ns) additionally return a Boolean
table that relates the original solid objects to the minimal
regions. A column in
bt corresponds to the column
with the same index in
gd. A row in
to a minimal region index.
[dl,bt,dl1,bt1,msb] = decsg(gd) and
= decsg(gd,sf,ns) return a second set of minimal regions
a corresponding Boolean table
bt1. This second
set of minimal regions all have a connected boundary. These minimal
regions can be plotted by using MATLAB® patch objects. The second
set of minimal regions have borders that may not have been induced
by the original solid objects. This occurs when two or more groups
of solid objects have nonintersecting boundaries.
The calling sequences additionally return a sequence
drawing commands for each second minimal region. The first row contains
the number of edge segment that bounds the minimal region. The additional
rows contain the sequence of edge segments from the Decomposed Geometry
matrix that constitutes the bound. If the index edge segment label
is greater than the total number of edge segments, it indicates that
the total number of edge segments should be subtracted from the contents
to get the edge segment label number and the drawing direction is
opposite to the one given by the Decomposed Geometry matrix.
The Geometry Description matrix
the CSG model that you draw using the PDE app. The current Geometry
Description matrix can be made available to the MATLAB workspace
by selecting the Export Geometry Description, Set Formula,
Labels option from the Draw menu
in the PDE app.
Each column in the Geometry Description matrix corresponds to an object in the CSG model. Four types of solid objects are supported. The object type is specified in row 1:
For the circle solid, row one contains 1, and the second and third row contain the center x- and y-coordinates, respectively. Row four contains the radius of the circle.
For a polygon solid, row one contains 2, and the second row contains the number, n, of line segments in the boundary of the polygon. The following n rows contain the x-coordinates of the starting points of the edges, and the following n rows contain the y-coordinates of the starting points of the edges.
For a rectangle solid, row one contains 3. The format is otherwise identical to the polygon format.
For an ellipse solid, row one contains 4, the second and third row contains the center x- and y-coordinates, respectively. Rows four and five contain the semiaxes of the ellipse. The rotational angle (in radians) of the ellipse is stored in row six.
sf contains a set formula expressed
with the set of variables listed in
ns. The operators
`+', `*', and `-' correspond to the set operations union, intersection,
and set difference, respectively. The precedence of the operators
`+' and `*' is the same. `-' has higher precedence. The precedence
can be controlled with parentheses.
The Name Space matrix
the columns in
gd to variable names in
Each column in
ns contains a sequence of characters,
padded with spaces. Each such character column assigns a name to the
corresponding geometric object in
gd. This way
we can refer to a specific object in
gd in the
The Decomposed Geometry matrix
a representation of the decomposed geometry in terms of disjointed minimal
regions that have been constructed by the
Each edge segment of the minimal regions corresponds to a column in
We refer to edge segments between minimal regions as border
segments and outer boundaries as boundary segments.
In each such column rows two and three contain the starting and ending x-coordinate,
and rows four and five the corresponding y-coordinate.
Rows six and seven contain left and right minimal region labels with
respect to the direction induced by the start and end points (counter
clockwise direction on circle and ellipse segments). There are three
types of possible edge segments in a minimal region:
For circle edge segments row one is 1. Rows eight and nine contain the coordinates of the center of the circle. Row 10 contains the radius.
For line edge segments row one is 2.
For ellipse edge segments row one is 4. Rows eight and nine contain the coordinates of the center of the ellipse. Rows 10 and 11 contain the semiaxes of the ellipse, respectively. The rotational angle of the ellipse is stored in row 12.
The following command sequence starts the PDE app and draws a unit circle and a unit square.
pdecirc(0,0,1) pderect([0 1 0 1])
Insert the set formula
C1-SQ1. Export the
Geometry Description matrix, set formula, and Name Space matrix to
the MATLAB workspace by selecting the Export Geometry
Description option from the Draw menu.
[dl,bt] = decsg(gd,sf,ns); dl = 2.0000 2.0000 1.0000 1.0000 1.0000 0 0 -1.0000 0.0000 0.0000 1.0000 0 0.0000 1.0000 -1.0000 0 1.0000 -0.0000 -1.0000 1.0000 0 0 -1.0000 0 -0.0000 0 0 1.0000 1.0000 1.0000 1.0000 1.0000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.0000 1.0000 1.0000 bt = 1 0
There is one minimal region, with five edge segments, three circle edge segments, and two line edge segments.
NaN is returned if the set formula
The algorithm consists of the following steps:
Determine the intersection points between the borders of the model objects.
For each intersection point, sort the incoming edge segments on angle and curvature.
Determine if the induced graph is connected. If not, add some appropriate edges, and redo algorithm from step 1.
Cycle through edge segments of minimal regions.
For each original region, determine minimal regions inside it.
Organize output and remove the additional edges.
The input CSG model is not checked for correctness. It is assumed
that no circles or ellipses are identical or degenerated and that
no lines have zero length. Polygons must not be self-intersecting.
Use the function