Partial Differential Equation Toolbox |

decsg

Decompose Constructive Solid Geometry into minimal regions

Syntax

-     dl=decsg(gd)
      dl=decsg(gd,sf,ns)
      [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)

Description

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 toolbox functions to "understand" the geometry you specify. For plotting purposes a second set of minimal regions with a connected boundary is constructed.

The graphical user interface `pdetool` uses `decsg` for many purposes. Each time a new solid object is drawn or changed, `pdetool` calls `decsg` in order to be able to draw the solid objects and minimal regions correctly. The Delaunay triangulation algorithm, `initmesh`, also uses the output of `decsg` to generate an initial mesh.

`dl=decsg(gd,sf,ns)` decomposes the CSG model `gd` into the decomposed geometry `dl`. The CSG model is represented by the Geometry Description matrix, and the decomposed geometry is represented by the Decomposed Geometry matrix. `decsg` returns the minimal regions that evaluate to true for the set formula `sf`. The Name Space matrix `ns` is a text matrix that relates the columns in `gd` to variable names in `sf`.

`dl=decsg(gd)` returns all minimal regions. (The same as letting `sf` correspond to the union of all objects in `gd`.)

`[dl,bt]=decsg(gd) and [dl,bt]=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 `bt` corresponds to a minimal region index.

`[dl,bt,dl1,bt1,msb]=decsg(gd) and [dl,bt,dl1,bt1,msb]=decsg(gd,sf,ns)` return a second set of minimal regions `dl1` with 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 `msb` of 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.

Geometry Description Matrix

The Geometry Description matrix `gd` describes the CSG model that you draw using `pdetool`. 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 `pdetool`.

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 of the ellipse is stored in row six.

Set Formula

`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.

Name Space Matrix

The Name Space matrix `ns` relates the columns in `gd` to variable names in `sf`. 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 set formula `sf`.

Decomposed Geometry Matrix

The Decomposed Geometry matrix `dl` contains a representation of the decomposed geometry in terms of disjointed minimal regions that have been constructed by the `decsg` algorithm. Each edge segment of the minimal regions corresponds to a column in `dl`. 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.

Examples

The command sequence below starts `pdetool` 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. Then type

-     [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

Note that there is one minimal region, with five edge segments, three circle edge segments, and two line edge segments.

Algorithm

The algorithm consists of the following steps:

1. Determine the intersection points between the borders of the model objects.
2. For each intersection point, sort the incoming edge segments on angle and curvature.
3. Determine if the induced graph is connected. If not, add some appropriate edges, and redo algorithm from step 1.
4. Cycle through edge segments of minimal regions.
5. For each original region, determine minimal regions inside it.
6. Organize output and remove the additional edges.

Note 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 selfintersecting. Use the function `csgchk` to check the CSG model.

Diagnostics

`NaN` is returned if the set formula `sf` cannot be evaluated.

See Also

`pdetool`, `pdegeom`, `pdebound`, `wgeom`, `wbound`, `pdecirc``,` `pderect`, `pdepoly`, `pdeellip`, `csgchk`, `csgdel`

| csgdel |  | dst, idst |