Loading...
Searching...
No Matches
mesh::pslg Namespace Reference

Preparation of planar straight-line graphs (PSLG) for meshing: Ramer–Douglas–Peucker simplification, straightness trimming, densification and resampling of paths and rings, hole-ring preparation, and point-in-rings tests. More...

Classes

class  PointInRingsIndex
 y-banded odd-even point-in-rings index. More...
 
struct  PreparedRing
 One hole ring after preparation for the PSLG. More...
 

Functions

QVector< QPointF > simplifyPolyline (const QVector< QPointF > &pts, double epsilon)
 Return an endpoint-preserving Ramer-Douglas-Peucker subsequence of an open path.
 
QVector< QPointF > simplifyRing (const QVector< QPointF > &ring, double epsilon)
 Simplify a ring's open vertex sequence and restore its existing closure convention.
 
QVector< QPointF > trimByStraightness (const QVector< QPointF > &pts, double maxTurnDeg, double maxDeviation, const QVector< bool > &protectedFlags={}, bool closed=false, int *removedOut=nullptr)
 Remove flattest eligible vertices while preserving original-span chord deviation limits.
 
QVector< QPointF > resampleAtSize (const QVector< QPointF > &path, const std::function< double(double, double)> &hAt, bool canonicalSegments=false)
 Insert collinear samples according to a numerically integrated local target-size callback.
 
QVector< bool > flagsForCoincidentVertices (const QVector< QPointF > &pts, const QVector< QVector< QPointF > > &others, double tol)
 Flag query vertices within an inclusive tolerance of any vertex in other paths.
 
QVector< QPointF > densifyRing (const QVector< QPointF > &ring, double maxLen)
 Insert equal-length subdivisions along every explicitly present consecutive path edge.
 
double polylineLength (const QVector< QPointF > &pts)
 Sum Euclidean lengths of consecutive explicitly stored path edges.
 
QVector< QPointF > unfoldPolyline (const QVector< QPointF > &pts, double maxTurnDeg=150.0, bool *changedOut=nullptr)
 Heuristically reorder reversed interior alignments and drop excessive backtracking turns.
 
QVector< QPointF > resampleMinLength (const QVector< QPointF > &pts, double minLen, double maxDeviation, int *flaggedOut=nullptr)
 Remove intermediate path vertices while respecting an original-point chord-deviation cap.
 
QVector< QPointF > resampleRingMinLength (const QVector< QPointF > &ring, double minLen, double maxDeviation, int *flaggedOut=nullptr)
 Apply minimum-length decimation to a ring while preserving at least three corners.
 
double ringSignedArea (const QVector< QPointF > &ring)
 Compute the ordinary double-precision shoelace area of an implicitly closed ring.
 
double distSqToSegment (const QPointF &p, const QPointF &a, const QPointF &b)
 Compute squared point-to-closed-segment distance using clamped projection.
 
void snapAndDedupe (QVector< mesh::SteinerPoint > &pts, double snapEps)
 Drop duplicate untagged Steiner points by rounded spatial-grid key without moving coordinates.
 
QVector< bool > greedyMinSeparation (const QVector< QPointF > &pts, double minSep)
 Keep points in priority order when no previously kept point is strictly closer than minSep.
 
PreparedRing prepareHoleRing (const QVector< QPointF > &raw, double simplifyEps, double maxEdgeLen, double trimTurnDeg=0.0, double trimDeviation=0.0)
 Trim, simplify, validate, densify and seed one borrowed hole boundary.
 
bool prepareHoleRings (const QVector< QVector< QPointF > > &raw, double simplifyEps, double maxEdgeLen, QVector< PreparedRing > *out, const std::function< bool()> &isCancelled={}, const std::function< void(int, int)> &onChunk={}, int *skippedOut=nullptr, double trimTurnDeg=0.0, double trimDeviation=0.0)
 Prepare hole rings in order-preserving synchronous parallel chunks of at most 4096.
 

Detailed Description

Preparation of planar straight-line graphs (PSLG) for meshing: Ramer–Douglas–Peucker simplification, straightness trimming, densification and resampling of paths and rings, hole-ring preparation, and point-in-rings tests.

Function Documentation

◆ densifyRing()

QVector< QPointF > mesh::pslg::densifyRing ( const QVector< QPointF > & ring,
double maxLen )
nodiscard

Insert equal-length subdivisions along every explicitly present consecutive path edge.

Parameters
[in]ringBorrowed finite planar path, unchanged. To subdivide closing edge, supply a repeated first point; no implicit last-to-first edge is processed for an open sequence.
[in]maxLenFinite positive maximum segment length in coordinate units; <=0 disables insertion. Every ceil(edgeLength/maxLen), output size and coordinate interpolation must be representable/feasible.
Returns
Owned densified sequence preserving originals/order/existing closure, unchanged for <2 points or disabled threshold. No vertex removal, topology repair, bounds checking or source mutation.

Split every ring edge longer than maxLen into equal parts — pure vertex insertion, geometry unchanged. No-op when maxLen <= 0.

Here is the caller graph for this function:

◆ distSqToSegment()

double mesh::pslg::distSqToSegment ( const QPointF & p,
const QPointF & a,
const QPointF & b )
nodiscard

Compute squared point-to-closed-segment distance using clamped projection.

Parameters
[in]pBorrowed finite planar query, unchanged.
[in]aBorrowed first segment endpoint in the same units, unchanged.
[in]bBorrowed second endpoint, unchanged; squared length below 1e-20 is treated as point a.
Returns
Squared coordinate-unit distance, assuming representable products/differences. No bounds, finite/CRS checks, allocation, source mutation or ownership retention.

Squared distance from p to the CLOSED segment ab.

Here is the caller graph for this function:

◆ flagsForCoincidentVertices()

QVector< bool > mesh::pslg::flagsForCoincidentVertices ( const QVector< QPointF > & pts,
const QVector< QVector< QPointF > > & others,
double tol )
nodiscard

Flag query vertices within an inclusive tolerance of any vertex in other paths.

Parameters
[in]ptsBorrowed finite query points in common planar units, unchanged.
[in]othersBorrowed other point paths, unchanged; no segment-interior matching is performed.
[in]tolFinite distance in planar units; negative yields all false, zero uses exact coordinate comparison with 1e-9 hash bins. Positive uses tol-sized bins. Floor coordinate/bin and neighbor offsets must fit qint64, and squared differences/tolerance must be representable.
Returns
Owned flags parallel to pts, true for any point-distance squared<=tol squared. Empty query returns empty. Allocates hash/flags, retains no input references and modifies no geometry.

One flag per vertex of pts: true when the vertex lies within tol of any vertex of any path in others (a T-junction or shared endpoint that trimming must keep).

◆ greedyMinSeparation()

QVector< bool > mesh::pslg::greedyMinSeparation ( const QVector< QPointF > & pts,
double minSep )
nodiscard

Keep points in priority order when no previously kept point is strictly closer than minSep.

Parameters
[in]ptsBorrowed finite planar points, unchanged; earlier indices have priority.
[in]minSepFinite positive separation in coordinate units; <=0 returns all true. Floor coordinate/ minSep and +/-1 neighbor-bin offsets must fit qint32; squared distance arithmetic must be representable.
Returns
Owned parallel keep flags, equality at minSep is retained. Rejected points do not reject later points; this is order-dependent greedy thinning, not a maximal quality/optimal distribution certificate. Allocates flags/spatial hash, no coordinate movement, input mutation or ownership retention.

Greedy minimum-separation thinning in input order.

pts[i] is kept iff no already-kept point lies strictly within minSep of it — so input order IS the priority order (earlier points win their neighbourhood). Spatial hash with cell size = minSep and a 3×3 scan, the same idiom as the terrain Poisson-disk filter. Returns one keep flag per point; minSep <= 0 keeps everything.

◆ polylineLength()

double mesh::pslg::polylineLength ( const QVector< QPointF > & pts)
nodiscard

Sum Euclidean lengths of consecutive explicitly stored path edges.

Parameters
[in]ptsBorrowed finite planar points in common units, unchanged; sums must be representable.
Returns
Length in coordinate units, zero for fewer than two points. No implicit closing edge unless first point is repeated at end; no finite validation, allocation, coordinate conversion or mutation.

Total length of the open polyline pts (0 for fewer than 2 points).

Here is the caller graph for this function:

◆ prepareHoleRing()

PreparedRing mesh::pslg::prepareHoleRing ( const QVector< QPointF > & raw,
double simplifyEps,
double maxEdgeLen,
double trimTurnDeg = 0.0,
double trimDeviation = 0.0 )
nodiscard

Trim, simplify, validate, densify and seed one borrowed hole boundary.

Parameters
[in]rawBorrowed finite planar ring, unchanged; closure/numeric/count preconditions of the respective helpers apply. Raw size<3 returns unchanged boundary and invalid result.
[in]simplifyEpsRDP tolerance in coordinate units, <=0 disables that stage.
[in]maxEdgeLenDensification maximum edge length in coordinate units, <=0 disables insertion.
[in]trimTurnDegStraightness turn threshold in degrees, <=0 disables trimming, circular treatment forced.
[in]trimDeviationStraightness chord-deviation cap in coordinate units, <=0 disables that cap.
Returns
Owned PreparedRing containing densified simplified geometry even when validation fails; valid/seed are set only when EditGeometry validates the smaller simplified ring. Seed comes from interiorPoint(simplified), not a separate post-densification topology check. Allocates helper/output storage, no source mutation, callback retention or engine edit; concurrent independent rings supported.

Prepare a single hole ring: simplify → validate → densify → seed.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ prepareHoleRings()

bool mesh::pslg::prepareHoleRings ( const QVector< QVector< QPointF > > & raw,
double simplifyEps,
double maxEdgeLen,
QVector< PreparedRing > * out,
const std::function< bool()> & isCancelled = {},
const std::function< void(int, int)> & onChunk = {},
int * skippedOut = nullptr,
double trimTurnDeg = 0.0,
double trimDeviation = 0.0 )

Prepare hole rings in order-preserving synchronous parallel chunks of at most 4096.

Parameters
[in]rawBorrowed stable ring array, unchanged; per-ring preconditions match prepareHoleRing().
[in]simplifyEpsRDP tolerance in planar units, <=0 disables.
[in]maxEdgeLenDensification limit in planar units, <=0 disables.
[out]outRequired nonnull borrowed vector, cleared/reserved at entry and appended chunk by chunk; contains completed input-prefix entries on cancellation, all entries on success. Must not alias raw storage.
[in]isCancelledOptional synchronous predicate polled before each chunk, true cancels. No poll occurs for empty input or within a running chunk; callback must not mutate inputs or output.
[in]onChunkOptional synchronous completed-count/total callback after each appended chunk; exceptions propagate and side effects/output already completed are not rolled back.
[out]skippedOutOptional borrowed invalid-ring count, overwritten on success or checked cancellation.
[in]trimTurnDegStraightness threshold in degrees, <=0 disables.
[in]trimDeviationStraightness deviation cap in planar units, <=0 disables.
Returns
False only for polled cancellation, true after all chunks (including empty input). Invalid rings remain in output and are counted, not global failure. QtConcurrent workers allocate per-ring results; callbacks/inputs are not retained after return and no project/engine state is modified.

Prepare many hole rings in parallel (order-preserving).

Rings are processed in chunks via QtConcurrent::blockingMapped; between chunks isCancelled is polled and onChunk(done, total) reports progress. out receives one entry per input ring, in input order. Invalid rings are counted into skippedOut. Returns false only when cancelled (out then holds the chunks finished so far).

Here is the call graph for this function:

◆ resampleAtSize()

QVector< QPointF > mesh::pslg::resampleAtSize ( const QVector< QPointF > & path,
const std::function< double(double, double)> & hAt,
bool canonicalSegments = false )
nodiscard

Insert collinear samples according to a numerically integrated local target-size callback.

Parameters
[in]pathBorrowed finite planar path, unchanged; original vertices/endpoints remain in order.
[in]hAtOptional synchronous callable of absolute x/y returning size in matching planar units; empty callback is a no-op. Nonpositive/NaN samples contribute no reciprocal limit; positive finite sizes and cumulative part counts must permit int conversion and feasible output allocation. Callback must remain deterministic, not mutate the path and not retain temporary evaluation state; exceptions propagate, no callback reference is retained.
[in]canonicalSegmentsWhen true, each segment is resampled from its lower endpoint (smaller x, then smaller y) and the inserted points are put back in path order, so a segment shared by two paths that run in opposite directions receives identical inserted points. False (default) resamples in path direction.
Returns
Owned resampled path, unchanged for <2 points/no callback or segments with no finite initial size source. Midpoint integration uses up to 65536 samples per pass, one optional finer resampling, then ceil(integral-1e-9) parts. This sampled rule can miss a narrow size source and does not prove every final segment <= every local h. Output count is not capped by the integration-sample cap. No source mutation, geometry projection or transactional handling of callback side effects.

Insert vertices so that no edge is longer than the local target size (Stage 1 resampling at h(x)). Pure insertion, geometry unchanged. An edge is split into n = ceil(∫ ds / h(s)) parts, the parts spaced by the local h, so a long edge crossing a size gradient gets short pieces where h is small and long ones where it is large. hAt returns the size at a point; a non-positive sample means "no limit" there. No-op when hAt is null.

◆ resampleMinLength()

QVector< QPointF > mesh::pslg::resampleMinLength ( const QVector< QPointF > & pts,
double minLen,
double maxDeviation,
int * flaggedOut = nullptr )
nodiscard

Remove intermediate path vertices while respecting an original-point chord-deviation cap.

Parameters
[in]ptsBorrowed finite planar path, unchanged; sizes/products/differences must be representable.
[in]minLenFinite target minimum chord length in planar units; <=0 or <=2 points returns input.
[in]maxDeviationFinite maximum original-point distance to each replacement segment in planar units, clamped to >=0. Unlike straightness trimming, zero here enforces zero allowed deviation.
[in,out]flaggedOutOptional borrowed initialized tally, incremented by retained short/deviation exceptions, not reset; unchanged on no-op. The diagnostic is heuristic and does not certify every chord.
Returns
Owned retained subsequence with both endpoints, original order/coordinates preserved. Mandatory endpoints/deviation constraints can leave segments shorter than minLen; tail pullback is rechecked against original points. Allocates retained-index/output storage, no source/engine mutation.

Length-based decimation — the inverse of densifyRing().

Drops intermediate vertices so that every retained chord is at least minLen long, but never moves the polyline further than maxDeviation from its original path: when dropping a run would exceed that, the offending vertex is retained instead and a short segment survives. RDP (simplifyPolyline) cannot do this — it is keyed on perpendicular deviation, so a tight zig-zag keeps every vertex however short the segments.

First and last points are always retained; for a conduit alignment they carry the coupling identity. No-op when minLen <= 0 or size <= 2.

Here is the caller graph for this function:

◆ resampleRingMinLength()

QVector< QPointF > mesh::pslg::resampleRingMinLength ( const QVector< QPointF > & ring,
double minLen,
double maxDeviation,
int * flaggedOut = nullptr )
nodiscard

Apply minimum-length decimation to a ring while preserving at least three corners.

Parameters
[in]ringBorrowed finite planar ring, unchanged; exact repeated closing vertex is recognized.
[in]minLenFinite target minimum chord length in coordinate units; <=0 or <4 points is a no-op.
[in]maxDeviationFinite original-point chord-deviation policy, clamped nonnegative.
[in,out]flaggedOutOptional borrowed initialized tally, incremented only for accepted nondegenerate result; unchanged when reverting to input. Not reset and not a strict minimum-length certificate.
Returns
Owned subsequence with existing closure/orientation convention retained, or original if fewer than three corners remain. Open-sequence endpoints anchor most processing; seam may drop the last corner if its immediate replacement stays within deviation, but no full ring-topology repair or exact all-edge minimum guarantee is added. Allocates scratch/output, no vertex movement or source mutation.

Closed-ring variant of resampleMinLength(). A closed ring (first == last) stays closed and keeps its orientation — vertices are only ever removed, never reordered. A result degenerating below 3 distinct vertices returns the input unchanged, matching simplifyRing().

Here is the call graph for this function:

◆ ringSignedArea()

double mesh::pslg::ringSignedArea ( const QVector< QPointF > & ring)
nodiscard

Compute the ordinary double-precision shoelace area of an implicitly closed ring.

Parameters
[in]ringBorrowed finite planar corners, unchanged; repeated closing duplicate optional.
Returns
Signed squared coordinate units, positive CCW/negative CW, zero for fewer than three distinct sequence entries after closure removal. No local-origin shift, compensated/exact predicate, self-crossing or overflow validation; folded rings can cancel. Allocation-free read-only arithmetic.

Signed area of ring (shoelace / 2). Positive = counter-clockwise. Handles both closed (first == last) and open vertex sequences.

◆ simplifyPolyline()

QVector< QPointF > mesh::pslg::simplifyPolyline ( const QVector< QPointF > & pts,
double epsilon )
nodiscard

Return an endpoint-preserving Ramer-Douglas-Peucker subsequence of an open path.

Parameters
[in]ptsBorrowed finite planar points, unchanged; indices/coordinate products must be representable.
[in]epsilonFinite perpendicular-deviation tolerance in coordinate units; <=0 disables simplification.
Returns
Owned/implicitly shared unchanged input for <=2 points or disabled tolerance, otherwise a retained subsequence with both endpoints. Recursive tests use supporting chord-line distance (not clamped segment projection), with squared chord <1e-20 treated as a point. Does not guarantee polygon validity or prevent deep recursion on adversarial paths; allocates flags/output, no coordinate movement or source mutation.

Simplify an open polyline with RDP. First and last points are always kept. Returns pts unchanged when epsilon <= 0 or pts.size() <= 2.

◆ simplifyRing()

QVector< QPointF > mesh::pslg::simplifyRing ( const QVector< QPointF > & ring,
double epsilon )
nodiscard

Simplify a ring's open vertex sequence and restore its existing closure convention.

Parameters
[in]ringBorrowed finite planar polygon sequence, unchanged; arithmetic/index bounds as simplifyPolyline().
[in]epsilonFinite deviation tolerance in coordinate units; <=0 or fewer than four input points is a no-op.
Returns
Owned retained subsequence, or original if fewer than three retained corners would remain. Exact first==last closure is removed/reappended, and both ends of the open sequence remain anchors; this is not a start-index-invariant cyclic simplifier. No self-intersection/orientation validation, coordinate relocation or source mutation; allocates flags/output and uses recursive RDP.

Simplify a closed polygon ring with RDP. A closed ring (first == last) stays closed; a result degenerating below 3 vertices returns the input.

Here is the caller graph for this function:

◆ snapAndDedupe()

void mesh::pslg::snapAndDedupe ( QVector< mesh::SteinerPoint > & pts,
double snapEps )

Drop duplicate untagged Steiner points by rounded spatial-grid key without moving coordinates.

Parameters
[in,out]ptsBorrowed mutable point records, compacted in place preserving survivor order and all attributes. Tagged marker!=0 records always survive and do not occupy keys for untagged deduplication.
[in]snapEpsFinite positive key-cell size in planar units; <=0 or empty input is a no-op. Rounded coordinate/snapEps must fit qint64, with finite representable reciprocal/arithmetic.
Note
First untagged point per rounded key survives, even if two nearby points fall in adjacent bins. Does not snap survivor xy to bin centers or enforce a Euclidean separation tolerance. Allocates key/flag scratch, invalidates removed-element references, retains no external ownership and emits no layer signals.

Snap near-coincident Steiner points to a grid of cell size snapEps and drop duplicates. Only untagged points (marker == 0) merge; tagged points always survive. Survivor order is preserved.

◆ trimByStraightness()

QVector< QPointF > mesh::pslg::trimByStraightness ( const QVector< QPointF > & pts,
double maxTurnDeg,
double maxDeviation,
const QVector< bool > & protectedFlags = {},
bool closed = false,
int * removedOut = nullptr )
nodiscard

Remove flattest eligible vertices while preserving original-span chord deviation limits.

Parameters
[in]ptsBorrowed finite planar path, unchanged; size/coordinate products must be representable.
[in]maxTurnDegFinite turn threshold in degrees, normally (0,180]; <=0 disables trimming. Actual comparison includes equality and treats zero-length adjacent edges as straight.
[in]maxDeviationFinite chord-distance cap in planar units; <=0 disables this cap. Every original vertex spanned by a proposed removal is checked against the closed replacement segment.
[in]protectedFlagsBorrowed protection flags; may be empty/short, missing entries mean unprotected. Open endpoints are always protected; repeated closing duplicate uses its first corner's flag.
[in]closedTrue forces circular treatment; exact first==last also selects ring behavior.
[out]removedOutOptional borrowed count, reset to zero first and set to removed open vertices.
Returns
Owned retained subsequence, unchanged for no-op/no removals. Preserves explicit closing duplicate, keeps at least three ring vertices, never moves coordinates. Deviation-rejected candidates become permanently protected; no global self-intersection/topology guarantee. Allocates linked-index/heap/output storage, retains no inputs and does not modify geometry or engine state.

Straightness trimming (MESH_OVERHAUL_PLAN_2026-09-29.md Stage 1).

Drops a vertex when the polyline turns by less than maxTurnDeg there, provided the chord that replaces it stays within maxDeviation of every ORIGINAL vertex it spans (so error never accumulates across removals). Vertices are taken flattest-first from a heap; a vertex whose removal would breach the deviation cap is kept for good. Protected vertices (protectedFlags, one per input point; may be empty) are never removed; the endpoints of an open polyline are always protected.

Closed rings (first == last, or closed) are treated circularly, keep their closing duplicate if they had one, and never drop below 3 distinct vertices. No-op when maxTurnDeg <=

  1. maxDeviation <= 0 = no cap.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ unfoldPolyline()

QVector< QPointF > mesh::pslg::unfoldPolyline ( const QVector< QPointF > & pts,
double maxTurnDeg = 150.0,
bool * changedOut = nullptr )
nodiscard

Heuristically reorder reversed interior alignments and drop excessive backtracking turns.

Parameters
[in]ptsBorrowed finite planar path, unchanged; coordinate/length/angle arithmetic must be representable.
[in]maxTurnDegFinite maximum allowed interior turn in degrees, normally [0,180], default 150. No clamp/no-op sentinel is applied; negative values can remove all interior points, while interior reversal can occur even at 180 degrees.
[out]changedOutOptional borrowed flag, initialized false and set true on any reversal/removal.
Returns
Owned path retaining original endpoints. With >=4 points reverses all interior points only if total length decreases; repeatedly removes the largest turn strictly above threshold. Zero-length adjacent edges count as zero turn. Heuristic can change route topology and has no deviation/shape preservation guarantee; allocates copies, no source mutation or engine update.

Undo two digitising faults in a link alignment that fold it back on itself (MESH_TRIANGLE_ENGINE_PLAN_2026-09-30.md, Bellinge).

A vertex list stored from the to-node to the from-node runs the path out to the far end and back; when the interior vertices in reverse order give a shorter path, they are reversed. Then any interior vertex where the path turns back by more than maxTurnDeg (a stray or out-of-order vertex) is dropped, sharpest first, until none is left. A pipe never doubles back, and a folded line leaves a sliver band the mesh cannot fill with good cells. The end points are always kept.

Here is the call graph for this function: