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
Contained	Certified contained rectangle	Yes (unless fallback enabled)	No
BCRS	Certified + fit improvement	Yes (unless fallback enabled)	Yes (CABF)
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
Contained Standard	Certified search	Certified / best-effort	No
Contained Fast	Optimized Contained	Certified / best-effort	No
BCRS	Full contained + expansion	Certified / best-effort	CABF
BCRS Fast	Optimized BCRS	Certified / best-effort	CABF
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
   • Contained: guaranteed containment
   • BCRS: best accuracy with boundary fitting
   • Axis-Aligned: exact fixed-orientation solution

Documentation Sections

Getting Started

• Installation — Install as script folder or plugin provider

Algorithms

• Algorithms — Family comparison table
• Approximation — Approx Standard/Fast with flowchart
• Contained — Contained Standard/Fast with flowchart
• BCRS — BCRS/CABF Standard/Fast with flowchart
• Axis-Aligned — Exact solvers for fixed-axis

Theory

• Complexity — Formal complexity analysis
• Foundations — Geometric background and academic references

Reference

• Parameters — Complete parameter reference
• Folder Layout — Code structure
• Usage — Programmatic API usage

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 Complexity for detailed performance characteristics