Home

LIRiAP Documentation

LIRiAP (Largest Inscribed Rectangle in Arbitrary Polygon) provides QGIS Processing algorithms for computing largest inscribed rectangles in polygon features.

Problem Statement

Given an input polygon, find a large non-axis-aligned interior rectangle. Four problem variants are implemented:

Family	Primary Objective	Strict Containment	Boundary Expansion
Approximation	Fast area-focused search	No	No
Skeleton	BCRS-free skeleton-guided solver	Yes (unless fallback enabled)	No
BCRS	Certified + fit improvement	Yes (unless fallback enabled)	Yes (CABF - historical)
Axis-Aligned	Exact fixed-axis solve	Exact (vertex-coordinate)	N/A

Algorithm Overview

Algorithm	Problem	Containment	Expansion
Approximation Standard	Fast approximation	Not certified	No
Approximation Fast	Same as Standard, lower overhead	Not certified	No
Skeleton	BCRS-free skeleton-guided	Certified / best-effort	No
BCRS	Full contained + expansion	Certified / best-effort	CABF (historical)
BCRS Fast	Optimized BCRS	Certified / best-effort	CABF (historical)
Axis-Aligned LIR	Exact fixed-axis solve	Exact (vertex-coordinate)	N/A

Quick Start

1. Install LIRiAP in QGIS - Choose script folder or plugin provider
2. Open Processing Toolbox → LIRiAP
3. Select algorithm family:
   • Approximation: quick candidates
   • Skeleton: BCRS-free skeleton-guided solver
   • BCRS: boundary expansion (historical earlier implementation)
   • Axis-Aligned: exact fixed-orientation solution

Performance Notes

• Approximation Fast with multithreading: best throughput for large datasets
• Axis-Aligned LIR: fastest single-threaded for fixed-axis problems (exact solution)
• BCRS (single-threaded): best accuracy for rotated rectangles
• See Performance for detailed benchmarks

---

Navigation

• Home
• Installation
• Algorithms
  • Approximation
  • Skeleton
  • BCRS
  • Axis-Aligned
• Theory
  • Complexity
  • Foundations
  • Performance
• Reference
  • Parameters
  • Folder Layout
  • Usage