A Python implementation of CGAL 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.

• Segment Regularization: Align line segments to common angles and offsets using quadratic programming optimization
• Contour Regularization: Simplify closed polygons by aligning edges to principal directions
• Flexible Configuration: Control maximum angle and offset tolerances
• Visualization: Built-in plotting utilities for before/after comparisons
• Pure Python: No CGAL dependency required

pip install shreg

uv pip install shreg

git clone https://github.com/nickp/shreg.git
cd shreg
pip install -e .

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

import numpy as np
from shreg import solve_line_segments, seg

# Create some segments (each segment is [x1, y1, x2, y2])
segments = [
    seg(0.0, 0.0, 1.0, 0.02),   # Nearly horizontal
    seg(0.0, 1.0, 1.0, 1.05),   # Nearly horizontal, slightly offset
    seg(1.0, 0.0, 1.02, 1.0),   # Nearly vertical
]

# Regularize: align angles within 25 degrees, offsets within 0.5 units
result = solve_line_segments(
    segments,
    angle=True,
    offset=True,
    maximum_angle=25,
    maximum_offset=0.5
)

Simplify a closed polygon by aligning edges to principal directions:

from shreg import regularize_contour

# Define a noisy polygon (list of [x, y] points)
points = [
    [45, 29], [65, 440], [44, 498], [446, 498], [429, 325],
    [499, 309], [448, 206], [479, 148], [479, 31], [247, 88],
]

# Regularize with axis alignment
result = regularize_contour(
    points,
    principle="axis",     # Align to horizontal/vertical
    max_offset=20,        # Maximum offset for merging
)

print(f"Simplified from {len(points)} to {len(result)} points")

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:

Simplify complex polygons while preserving their essential shape:

Complex shapes are reduced to their essential vertices:

Regularize a list of line segments.

Parameters:

• segments: List of segments, where each segment is a numpy array [x1, y1, x2, y2]
• offset: Whether to regularize offsets (default: True)
• angle: Whether to regularize angles (default: True)
• maximum_offset: Maximum offset tolerance in units (default: 0.5)
• maximum_angle: Maximum angle tolerance in degrees (default: 25)

Returns: List of regularized segments

Helper function to create a segment array.

from shreg import seg
s = seg(0, 0, 1, 1)  # Creates np.array([0, 0, 1, 1])

Regularize a closed contour.

Parameters:

• points: List of [x, y] coordinates forming a closed polygon
• principle: How to determine principal directions:
  • "longest": Use the longest edge as reference
  • "axis": Align to horizontal/vertical axes
  • "cardinal": Use 0, 45, 90, 135 degree directions
• max_offset: Maximum offset for merging parallel segments (default: 20.0)
• visualize: Whether to show intermediate plots (default: False)

Returns: numpy array of regularized points

Load contour points from a polylines file.

Parameters:

• filename: Path to polylines file. If None, loads bundled example data.

The package includes various geometry functions:

from shreg import (
    length,              # Segment length
    midpoint,            # Segment midpoint
    orientation,         # Segment orientation in degrees [0, 180)
    direction,           # Unit direction vector
    normal,              # Unit normal vector
    rotate,              # Rotate segment around midpoint
    translate_by_normal, # Translate along normal
    angle_difference,    # Angle difference modulo 90 degrees
)

from shreg import plotting

# Enable/disable all plotting
plotting.enable()
plotting.disable()

# Before/after comparison
plotting.comparison(before_segments, after_segments, title="My Title")

# Context manager for before/after
with plotting.BeforeAfter("My Title") as plot:
    plot.before(segments)
    segments = regularize(segments)
    plot.after(segments)

# Save plots to file
plotting.comparison(before, after, save_path="output.png")

Run the demo examples:

# Run all examples with visualization
shreg

# Run without visualization (batch mode)
shreg --no-plot

# Run only segment examples
shreg --segments

# Run only contour examples
shreg --contours

Or using Python module syntax:

python -m shreg --help

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:

• Fidelity: Keep segments close to their original positions
• Regularity: Encourage nearby segments to share common angles and offsets

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

minimize    (1/2) x'Px + q'x
subject to  l <= Ax <= u

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.

1. Neighbor Detection: Use Delaunay triangulation on segment midpoints to identify nearby segment pairs efficiently
2. Constraint Graph: Build constraints for angle and offset differences between neighboring segments within tolerance bounds
3. QP Optimization: Solve the quadratic program using OSQP to find optimal corrections
4. Application: Apply computed rotations and translations to each segment

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

1. Angle Alignment: Rotate each edge to align with principal directions (modulo 90 degrees)
2. Parallel Merging: Merge consecutive parallel edges that are close together
3. Link Insertion: Insert connecting segments between remaining parallel edges
4. Intersection: Compute intersection points to form the final regularized polygon

• numpy >= 1.20.0
• scipy >= 1.7.0
• osqp >= 0.6.0 - Quadratic programming solver
• matplotlib >= 3.5.0

Install development dependencies:

pip install -e ".[dev]"

Run tests:

pytest tests/ -v

• Jean-Philippe Bauchet and Florent Lafarge. KIPPI: KInetic Polygonal Partitioning of Images. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3146–3154, Salt Lake City, United States, June 2018. [PDF]
• CGAL Shape Regularization Documentation
• OSQP: Operator Splitting Quadratic Program Solver