Show HN：多種形狀正規化演算法

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

To see all available qualifiers, see our documentation.

Various shape regularization algorithms

Uh oh!

There was an error while loading. Please reload this page.

nickponline/shreg

Folders and files

Latest commit

History

Repository files navigation

shreg - Shape Regularization

A Python implementation of various shape regularization algorithms for regularizing line segments and closed contours.

Shape regularization is a technique used in computational geometry to clean up noisy or imprecise geometric data by aligning segments to common orientations and adjusting their positions to create cleaner, more regular shapes.

Features

Installation

Using pip

Using uv

From source

Quick Start

Segment Regularization

Regularize a set of line segments by aligning their angles and offsets:

Contour Regularization

Simplify a closed polygon by aligning edges to principal directions:

Snap Regularization

Close gaps between nearby endpoints to create watertight polygons:

Metric Regularization

Constrain segment dimensions - force equal lengths, quantize to grid units, or equalize spacing:

Examples

Segment Regularization

The algorithm optimizes segment orientations and positions to create cleaner line arrangements:

Angle regularization aligns crossing lines to common orientations:

Combined angle and offset regularization on a hexagon:

This example from the CGAL documentation demonstrates sequential angle and offset regularization on 15 segments organized into three groups: outer boundary, top rhombus, and bottom rhombus.

Contour Regularization

Simplify complex polygons while preserving their essential shape:

Complex shapes are reduced to their essential vertices:

Snap Regularization

Snap regularization connects nearby endpoints to create watertight geometry. This is essential for creating closed polygons suitable for 3D extrusion, mesh generation, or CAD operations.

The cluster method groups nearby endpoints and moves them to their centroid. This is the fastest approach and guarantees watertight results:

Hard constraints use quadratic programming to find the optimal positions that exactly satisfy all snap constraints while minimizing total endpoint movement:

Soft constraints add "spring" forces between endpoints that should connect. This is useful when data is noisy and you're not certain endpoints should be exactly coincident:

T-junctions occur when an endpoint should snap onto another segment's interior (not its endpoints). Enable T-junction detection for proper connectivity:

Snap regularization works on polygons of any complexity:

Metric & Pattern Regularization

Metric regularization constrains the relative measurements of segments. This is useful for architectural drawings, CAD cleanup, and any domain where dimensions should follow regular patterns.

Forces segments with similar lengths to be exactly equal. Useful when objects (like windows or columns) should have identical dimensions:

Snaps segment lengths to integer multiples of a base unit. Essential for architectural plans where walls must be multiples of a grid unit:

Forces equal gaps between parallel lines. Perfect for regularizing staircases, window arrays, or any repeated elements:

API Reference

See API.md for the complete API documentation.

Command Line Interface

Run the demo examples:

Or using Python module syntax:

Algorithm

Energy Minimization via Quadratic Programming

The regularization problem is formulated as an energy minimization problem. Given a set of segments, we seek small adjustments (rotations and translations) that minimize an energy function while respecting constraints on maximum deviations.

The energy function balances two objectives:

This leads to a quadratic program (QP) of the form:

where x contains the rotation and translation corrections for each segment, P encodes the fidelity cost, and the constraints enforce that angle/offset differences between nearby segments are minimized.

Segment Regularization Pipeline

Snap (Connectivity) Regularization

Snap regularization is formulated as a Constrained Quadratic Programming problem that minimizes endpoint movement while enforcing connectivity constraints.

Variables: For N segments, the state vector contains all 4N endpoint coordinates:

Objective (Fidelity): Minimize squared distance from original positions:

Methods:

Pipeline:

Metric & Pattern Regularization

Metric regularization constrains segment dimensions (length, distance). The challenge is that length calculation √(Δx² + Δy²) is non-linear, but QP solvers require linear constraints.

Linearization: We approximate length using the segment's unit direction vector d = (dₓ, dᵧ):

This is linear in the endpoint coordinates and can be directly inserted into the constraint matrix.

Constraint Formulations:

Iterative Refinement (SQP): Because the unit vectors are computed from the current geometry, results are approximate if segments rotate significantly. The algorithm uses Sequential Quadratic Programming:

Pipeline:

Contour Regularization

The contour regularization algorithm follows CGAL's approach for closed polygons:

Dependencies

Development

Install development dependencies:

Run tests:

Run tests with coverage:

References

About

Various shape regularization algorithms

Topics

Resources

Uh oh!

There was an error while loading. Please reload this page.

Stars

Watchers

Forks

Releases

Packages

  0

Languages

Footer

Footer navigation