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.
- 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.
- Compute points of quarter centres (NOTE border quarters are slightly larger because path is subtracted only from one side; TODO fix that).
- For each unsorted quarter intersect find intersection with the quarter centre and save at the matrix array index. Do the same for corner shapes.
- Now it is possible to walk through matrix and access both quarters and corner shapes (corner quarters).
- Create labelled shape for each quarter
- Remove duplicate and middle-of-edge vertices for each corner shape and set it to appropriate quarter.
- Set indexing.
- Input remains the same
- Selection: list of non-overlapping intervals [a, b]
- Extrusion size
- Process separated
- Linestrings created from selection list and input shape
- Each linestring extruded into a single connected polygon
- Boolean polygon cutting and labelled shape creation
- Substrate shape created by differencing iregion with extruded shapes
- Fixing of polygons
- Indices are set
Given iregion and a selection extractBoundary computes a linestring around the boundary of the iregion.
- 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]]
- (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]].
- Ectually extract LE subedges.
- Get LE, as linestring on the local range [0, 1]
- 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.
- Joing LE subedges into one linestring, removing duplicates at joining points.
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
- Split polyline into individual edges or segments
- Create pairs of inner and outer segments; Outer segment may either lie on the polyline or outside when outer extrusion parameter is positive.
- Extrude polygons or blocks are created. At this point however we cannot join them unless angle between adjacent segments is180 degrees or lower.
- 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.
- 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.