Package org.tinfour.refinement

Class RuppertRefiner

  • All Implemented Interfaces:
    IDelaunayRefiner
    public class RuppertRefiner
extends Object
implements IDelaunayRefiner
    RuppertRefiner implements Ruppert’s Delaunay refinement for improving mesh quality of an IIncrementalTin.

    The refiner iteratively refines poor-quality triangles by inserting Steiner points (Shewchuk-style off-centers with circumcenter fallback) and by splitting encroached constrained subsegments. Several practical safeguards are included to avoid pathological infinite refinement:

    • radius-edge gating (configurable; optionally enforces ρ ≥ √2);
    • concentric-shell segment tagging to enable robust off-center / midpoint handling;
    • identification of seditious edges (midpoints on the same shell about a critical corner) and optional skipping/ignoring of these in split/encroachment decisions to prevent ping-pong cascades;
    • scale-aware tolerances for encroachment, near-vertex and near-edge checks to avoid degenerate insertions.

    Features and guarantees:

    • The refiner is driven by a minimum-angle (or equivalently a circumradius-to-shortest-edge ratio) goal supplied at construction. When configured to enforce the √2 guard, the implementation follows standard termination theory (Ruppert/Shewchuk) and mitigates many non-adversarial inputs.
    • Concentric-shell and seditious-edge logic extend robustness to small corner cases commonly observed in practice.
    • By default the algorithm uses off-center insertion (Shewchuk) and splits constrained segments when required by encroachment rules.
    • Terminated either when no encroached subsegments and no poor triangles remain, or when an iteration cap is reached.

    References:

    • J. Ruppert, "A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation", J. Algorithms (1995).
    • J. R. Shewchuk, "Delaunay Refinement Mesh Generation", 1997.
    Author:
    Michael Carleton

    • Constructor Detail

      • RuppertRefiner

        public RuppertRefiner​(IIncrementalTin tin,
                      double minAngleDeg)
        Constructs a RuppertRefiner with the requested minimum internal triangle angle.

        The refiner will try to remove triangles with angles smaller than minAngleDeg. The implementation uses off-center insertion with circumcenter fallback, encroachment checks for constrained subsegments, and several practical safeguards (concentric-shell tagging and seditious-edge handling) to prevent pathological infinite refinement loops.

        Parameters and preconditions:

        • tin must be non-null and bootstrapped (already built).
        • minAngleDeg must be in (0, 60) degrees; values near the theoretical limits may still fail to terminate.
        Parameters:
        tin - the incremental triangulation to refine (non-null, bootstrapped)
        minAngleDeg - the requested minimum angle in degrees (0 < θ < 60)
        Throws:
        IllegalArgumentException - on invalid inputs

      • RuppertRefiner

        public RuppertRefiner​(IIncrementalTin tin,
                      double minAngleDeg,
                      double minTriangleArea)
        Constructs a RuppertRefiner with the requested minimum internal triangle angle and a user-specified minimum triangle area threshold.

        The minTriangleArea is used as a conservative safeguard to avoid attempting to refine triangles whose area is extremely small (in the coordinate units squared). A value of 0 disables the area-based skipping.

        Parameters:
        tin - the incremental triangulation to refine (non-null, bootstrapped)
        minAngleDeg - the requested minimum angle in degrees (0 < θ < 60)
        minTriangleArea - area threshold for skipping refinement of very small triangles (must be ≥ 0)
        Throws:
        IllegalArgumentException - on invalid inputs

      • RuppertRefiner

        public RuppertRefiner​(IIncrementalTin tin,
                      double minAngleDeg,
                      double minTriangleArea,
                      boolean enforceSqrt2Guard,
                      boolean skipSeditiousTriangles,
                      boolean ignoreSeditiousEncroachments)
        Constructs a RuppertRefiner with explicit runtime policy options.

        This overload exposes three boolean options useful for production tuning:

        • enforceSqrt2Guard — when true, the internal radius-edge gating enforces ρ ≥ √2 (Shewchuk/Ruppert termination guard).
        • skipSeditiousTriangles — when true, triangles whose shortest edges have been marked seditious are not attempted for split.
        • ignoreSeditiousEncroachments — when true, encroachments identified as seditious are ignored (prevents ping-pong splitting).
        Parameters:
        tin - the incremental triangulation to refine (non-null, bootstrapped)
        minAngleDeg - the requested minimum angle in degrees (0 < θ < 60)
        minTriangleArea - area threshold for skipping very small triangles (must be ≥ 0)
        enforceSqrt2Guard - whether to force the ρ ≥ √2 termination guard
        skipSeditiousTriangles - whether to skip splitting triangles whose shortest edges are seditious
        ignoreSeditiousEncroachments - whether to ignore seditious encroachments
        Throws:
        IllegalArgumentException - on invalid inputs

    • Method Detail

      • fromEdgeRatio

        public static RuppertRefiner fromEdgeRatio​(IIncrementalTin tin,
                                           double ratio)
        Creates a RuppertRefiner configured by a target circumradius-to-shortest-edge ratio ratio.

        This factory computes the equivalent minimum angle from ratio (via θ = arcsin(1/(2·ratio))) and delegates to the primary constructor. The created refiner will attempt to eliminate triangles whose circumradius-to-shortest-edge ratio meets or exceeds the implied target.

        Parameters:
        tin - the incremental TIN to refine; must be bootstrapped and non-null
        ratio - the target circumradius-to-shortest-edge ratio (must be > 0)
        Returns:
        a configured RuppertRefiner
        Throws:
        IllegalArgumentException - if tin is null or not bootstrapped, or if ratio <= 0

      • refine

        public boolean refine()
        Perform refinement on the supplied IIncrementalTin.

        This method runs Ruppert’s iterative loop:

        1. collect constrained segments;
        2. split an encroached constrained segment if any;
        3. otherwise find a largest bad triangle and attempt an off-center insert (circumcenter fallback) or split an encroached segment found while testing the candidate;
        4. repeat until no encroached segments and no bad triangles remain or an iteration cap is reached.

        The method is re-entrant in the sense it mutates the supplied tin; it returns true when refinement converges or false if the maximum iteration cap is hit.

        Specified by:
        refine in interface IDelaunayRefiner
        Returns:
        true if the refinement process terminated successfully because the triangulation meets the configured quality criteria; false if the process terminated early due to a hard iteration cap or other imposed stopping condition before the criteria were satisfied.

      • refineOnce

        public Vertex refineOnce()
        Description copied from interface: IDelaunayRefiner
        Performs a single refinement operation on the associated triangulation.

        Implementations should perform one atomic refinement step: identify an element that violates the configured quality criteria (for example a "bad" triangle) and repair it (for example by inserting a Steiner vertex, performing local retriangulation or edge flips). This method mutates the underlying triangulation in-place.

        Implementation Note: Implementations are encouraged to make this method behave predictably when invoked repeatedly: calling it repeatedly on an unchanged triangulation should either return the same inserted vertex until the local repair completes, or return null once no further single-step refinements are required.

        Specified by:
        refineOnce in interface IDelaunayRefiner
        Returns:
        the Vertex that was inserted as part of this refinement step, or null if no refinement was necessary (the triangulation already meets the quality criteria or no applicable operation was available).
        See Also:
        IDelaunayRefiner.refine()