Indexing and Selecting using Logical Edges

Logical Edges Implementation

As mentioned already, logical edges (or LEs) contain multiple physical (or geometrical) edges. A selection unit is now a logical edge instead of a physical vertex as it was previous to this moment. Indices and directions are still used but relate to LEs instead of vertices. LEs are implemented as integer values of a start vertex and the length of the path to the next corner vertex.

When length is zero selection is no longer contains edges could represent a single vertex.

Autoindexing Input Region

A polygon with |v| > 4 but that roughly looks like a quad is treated as a ‘quad’ by partitioning all edges using (currently only) angle thresholding into 4 LEs

Vertices of the detected LEs or corners are also used as a corner shape for the Grid rule, because for path partitioning Grid rules requires a quad as input.

Grid Changes

• adapted LEs to be used as input
• Subregions (may be non-quads) and Corner Shapes (quads) are spacially indexed the same way
• Matrix indexing
• Corner Shapes may contain vertices that do not add new geometric information. Such vertices are removed. Thresholds were increased to deal with increasingly large Epsilon values.
  • Almost identical vertices, that is with an Epsilon distance between them are removed.
  • Vertices that span an angle of close to 180 degrees with the adjacent edges are classified as middle of the edge vertices and are removed.

Matrix Indexing

1. Compute points of quarter centres (NOTE border quarters are slightly larger because path is subtracted only from one side; TODO fix that).
2. For each unsorted quarter intersect find intersection with the quarter centre and save at the matrix array index. Do the same for corner shapes.
3. Now it is possible to walk through matrix and access both quarters and corner shapes (corner quarters).
   1. Create labelled shape for each quarter
   2. Remove duplicate and middle-of-edge vertices for each corner shape and set it to appropriate quarter.
   3. Set indexing.

Peel Changes

• Input remains the same
  • Iregion
  • Selection: list of non-overlapping intervals [a, b]
  • Extrusion size
• Process separated
  1. Linestrings created from selection list and input shape
  2. Each linestring extruded into a single connected polygon
  3. Boolean polygon cutting and labelled shape creation
     1. Substrate shape created by differencing iregion with extruded shapes
     2. Fixing of polygons
  4. Indices are set

Linestring Creation

Given iregion and a selection extractBoundary computes a linestring around the boundary of the iregion.

1. Split one selection range into selection for reach LE and pair with index of that LE. Whole LEs of course will have range [0, 1]. For instance selection [0.6, 2.3] will result in the list:
   [0:[0.6, 1], 1:[0, 1], 2:[0, 0.3]]
2. (optional) Ranges are reversed if selection direction is negative. Also each LE selection ranges are reversed [a, b] -> [1 – b, 1 – a]. Note that LE indexing is not changed, only the order of evaluation to closely match physical representation. For example the range above converted to:
   [2:[0.7, 1], 1:[0, 1], 0:[0, 0.4]].
   [TODO picture]
3. Ectually extract LE subedges.
   1. Get LE, as linestring on the local range [0, 1]
   2. Extract ‘substring’ or [0, 1] converted to [a, b] which could be[0.7, 1]. The algorithm also rather large in code is quite trivial nevertheless, important only to mention is that the edges are parametrised by length.
4. Joing LE subedges into one linestring, removing duplicates at joining points.

Extrusion

Initially only inner extrusion has been used. However as a result of floating point errors using Boolean operations – part of the boundary was not clipped appropriately. In the second iteration outer extrusion has been enabled and which amount controlled by an additional argument.

Extrusion algorithm as follows

1. Split polyline into individual edges or segments
2. Create pairs of inner and outer segments; Outer segment may either lie on the polyline or outside when outer extrusion parameter is positive.
3.  Extrude polygons or blocks are created. At this point however we cannot join them unless angle between adjacent segments is180 degrees or lower.
   
4. Joining polygons are created connect adjacent blocks. To accommodate both inner and outer extrusion joining polygons are applied to the whatever side of the polyline that has a greater angle. For zero outer extrusion empty polygons are added.
5. Inner product algorithm joins sets of blocks and joining polygons where both * and + operation overloaded as a joining operation. Because number of joining polygons is one less, an extra one is added to match the number of blocks.