| Name | quadfit JSON |
| Version |
1.1.0
JSON |
| download |
| home_page | None |
| Summary | Fork of QuadrilateralFitter rewritten in C. QuadrilateralFitter is an efficient and easy-to-use Python library for fitting irregular quadrilaterals from irregular polygons or any noisy data. |
| upload_time | 2025-09-13 00:22:26 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3.9 |
| license | None |
| keywords |
quadrilateral
fitter
polygon
shape analysis
geometry
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
numpy
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# QuadrilateralFitter
This project is a fork of the original [QuadrilateralFitter](https://github.com/Eric-Canas/quadrilateral-fitter) project.
Modifications by Krzysztof Mizgała (2025). Licensed under the MIT License.
The original Python code has been rewritten in C to boost performance.
<img alt="QuadrilateralFitter Logo" title="QuadrilateralFitter" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/logo.png" width="20%" align="left"> **QuadrilateralFitter** is an efficient and easy-to-use library for fitting irregular quadrilaterals from polygons or point clouds.
**QuadrilateralFitter** helps you find that four corners polygon that **best approximates** your noisy data or detection, so you can apply further processing steps like: _perspective correction_ or _pattern matching_, without worrying about noise or non-expected vertex.
Optimal **Fitted Quadrilateral** is the smallest area quadrilateral that contains all the points inside a given polygon.
## Installation
You can install **QuadrilateralFitter** with pip:
```bash
pip install quadfit
```
## Usage
The simplest way to use **QuadrilateralFitter** is just one line:
```python
from quadfit import QuadrilateralFitter
# Fit an input polygon of N sides and get the final quadrilateral directly
quad = QuadrilateralFitter(polygon=your_noisy_polygon).fit()
```
Optionally, you can trade a bit of accuracy for speed and determinism using the additional arguments of `fit`:
```python
# Limit the number of initial combinations and fix RNG seed; choose stage with 'until'
quad = QuadrilateralFitter(your_noisy_polygon).fit(
simplify_polygons_larger_than=30,
start_simplification_epsilon=0.1,
max_simplification_epsilon=0.5,
simplification_epsilon_increment=0.02,
max_initial_combinations=1000,
random_seed=123,
until="final", # or "initial" / "refined"
)
```
<div align="center">
<img alt="Fitting Example 1" title="Fitting Example 1" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/basic_example_1.png" height="250px">
<img alt="Fitting Example 2" title="Fitting Example 2" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/basic_example_2.png" height="250px">
</div>
If your application can accept a quadrilateral that does not strictly include all input points, use the tighter initial guess with early stop:
```python
initial = QuadrilateralFitter(polygon=your_noisy_polygon).fit(until="initial")
```
## API Reference
### QuadrilateralFitter(polygon)
Initialize the **QuadrilateralFitter** instance.
- `polygon`: **np.ndarray | tuple | list | object**. Coordinates of the input geometry. Preferred: `np.ndarray` of shape (N, 2) or list/tuple of `(x, y)`. Also accepts objects exposing `.exterior.coords` or `.coords` (e.g., Shapely geometries) via duck‑typing. Shapely is NOT required at runtime.
### QuadrilateralFitter.fit → tuple of 4 (x, y)
Signature:
```python
QuadrilateralFitter.fit(
simplify_polygons_larger_than: int | None = 10,
start_simplification_epsilon: float = 0.1,
max_simplification_epsilon: float = 0.5,
simplification_epsilon_increment: float = 0.02,
max_initial_combinations: int = 300,
random_seed: int | None = None,
until: Literal["initial", "refined", "final"] = "final",
auto_scale_simplification: bool = True,
max_points_for_refinement: int | None = None,
) -> tuple[tuple[float, float], tuple[float, float], tuple[float, float], tuple[float, float]]
```
- `simplify_polygons_larger_than`: If specified, performs a preliminary Douglas–Peucker simplification of the convex hull when it has more than this many vertices. This speeds up the process but may lead to a slightly sub‑optimal quadrilateral. Default: 10.
- `start_simplification_epsilon`, `max_simplification_epsilon`, `simplification_epsilon_increment`: Epsilon schedule for the Douglas–Peucker simplification.
- `max_initial_combinations`: Limits the number of candidate quadrilaterals tested when searching the initial guess. If 0 or larger than the total number of combinations C(N,4), a full search is performed. Otherwise, up to this many unique combinations are sampled randomly. Default: 300.
- `random_seed`: RNG seed for deterministic sampling when `max_initial_combinations` is used. Default: None.
- `until`: Choose how far the pipeline should run for performance. `"initial"` returns only the initial guess, skipping finetune/expansion. `"refined"` runs TLS finetuning but skips final expansion. `"final"` runs the full pipeline. Default: `"final"`.
- `auto_scale_simplification`: If `True`, scales Douglas–Peucker epsilon parameters by the input size (bounding box diagonal) when epsilons look relative (<= 1). Helps keep simplification consistent across scales. Default: `True`.
- `max_points_for_refinement`: Optional cap for the number of points used in the TLS finetuning stage. If the input has more points, a deterministic subsample is used (or RNG with `random_seed`). This can dramatically reduce runtime on very large point clouds with minimal accuracy loss. Default: `None` (use all points).
**Returns**: A 4-vertex quadrilateral (counter-clockwise) for the requested stage:
- `until="initial"`: best IoU vs convex hull (may not contain all points)
- `until="refined"`: after TLS finetuning
- `until="final"`: expanded to strictly contain the convex hull (default)
## Real Case Example
Let's simulate a real case scenario where we detect a noisy polygon from a form that we know should be a perfect rectangle (only deformed by perspective).
```python
import numpy as np
import cv2
image = cv2.cvtColor(cv2.imread('./resources/input_sample.jpg'), cv2.COLOR_BGR2RGB)
# Save the Ground Truth corners
true_corners = np.array([[50., 100.], [370., 0.], [421., 550.], [0., 614.], [50., 100.]], dtype=np.float32)
# Generate a simulated noisy detection
sides = [np.linspace([x1, y1], [x2, y2], 20) + np.random.normal(scale=10, size=(20, 2))
for (x1, y1), (x2, y2) in zip(true_corners[:-1], true_corners[1:])]
noisy_corners = np.concatenate(sides, axis=0)
# To simplify, we will clip the corners to be within the image
noisy_corners[:, 0] = np.clip(noisy_corners[:, 0], a_min=0., a_max=image.shape[1])
noisy_corners[:, 1] = np.clip(noisy_corners[:, 1], a_min=0., a_max=image.shape[0])
```
<div align="center">
<img alt="Input Sample" title="Input Sample" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/input_noisy_detection.png" height="300px" align="center">
</div>
And now, let's run **QuadrilateralFitter** to find the quadrilateral that best approximates our noisy detection (without leaving points outside).
```python
from quadfit import QuadrilateralFitter
# Define the fitter and compute desired stages
fitter = QuadrilateralFitter(polygon=noisy_corners)
fitted_quadrilateral = np.array(fitter.fit(until="final"), dtype=np.float32)
# Tighter quadrilateral (may exclude some points):
tight_quadrilateral = np.array(fitter.fit(until="initial"), dtype=np.float32)
```
<div align="center">
<img alt="Fitting Process" title="Fitting Process" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/fitting_process.png" height="300px">
<img alt="Fitted Quadrilateral" title="Fitted Quadrilateral" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/fitted_quadrilateral.png" height="300px">
</div>
Finally, for use cases like this, we could use fitted quadrilaterals to apply a perspective correction to the image, so we can get a visual insight of the results.
```python
# Generate the destination points for the perspective correction by adjusting it to a perfect rectangle
h, w = image.shape[:2]
for quadrilateral in (fitted_quadrilateral, tight_quadrilateral):
# Cast it to a numpy for agile manipulation
quadrilateral = np.array(quadrilateral, dtype=np.float32)
# Get the bounding box of the fitted quadrilateral
min_x, min_y = np.min(quadrilateral, axis=0)
max_x, max_y = np.max(quadrilateral, axis=0)
# Define the destination points for the perspective correction
destination_points = np.array(((min_x, min_y), (max_x, min_y),
(max_x, max_y), (min_x, max_y)), dtype=np.float32)
# Calculate the homography matrix from the quadrilateral to the rectangle
homography_matrix, _ = cv2.findHomography(srcPoints=quadrilateral, dstPoints=destination_points)
# Warp the image using the homography matrix
warped_image = cv2.warpPerspective(src=image, M=homography_matrix, dsize=(w, h))
```
<div align="center">
<img alt="Input Segmentation" title="Input Segmentation" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/input_segmentation.png" height="230px">
<img alt="Corrected Perspective Fitted" title="Corrected Perspective Fitted" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/corrected_perspective_fitted.png" height="230px">
<img alt="Corrected Perspective Tight" title="Corrected Perspective Tight" src="https://raw.githubusercontent.com/KMChris/quadfit/main/resources/corrected_perspective_tight.png" height="230px">
</div>
Raw data
{
"_id": null,
"home_page": null,
"name": "quadfit",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "quadrilateral, fitter, polygon, shape analysis, geometry",
"author": null,
"author_email": "Krzysztof Mizga\u0142a <krzysztof@mizgala.pl>",
"download_url": "https://files.pythonhosted.org/packages/87/3a/b749dc5bb6ffda33780f9778d898e0c460272137fd59a64efb9632ff8e80/quadfit-1.1.0.tar.gz",
"platform": null,
"description": "# QuadrilateralFitter\r\nThis project is a fork of the original [QuadrilateralFitter](https://github.com/Eric-Canas/quadrilateral-fitter) project.\r\nModifications by Krzysztof Mizga\u0142a (2025). Licensed under the MIT License.\r\nThe original Python code has been rewritten in C to boost performance.\r\n\r\n<img alt=\"QuadrilateralFitter Logo\" title=\"QuadrilateralFitter\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/logo.png\" width=\"20%\" align=\"left\"> **QuadrilateralFitter** is an efficient and easy-to-use library for fitting irregular quadrilaterals from polygons or point clouds.\r\n\r\n**QuadrilateralFitter** helps you find that four corners polygon that **best approximates** your noisy data or detection, so you can apply further processing steps like: _perspective correction_ or _pattern matching_, without worrying about noise or non-expected vertex.\r\n\r\nOptimal **Fitted Quadrilateral** is the smallest area quadrilateral that contains all the points inside a given polygon.\r\n\r\n## Installation\r\n\r\nYou can install **QuadrilateralFitter** with pip:\r\n\r\n```bash\r\npip install quadfit\r\n```\r\n\r\n## Usage\r\n\r\nThe simplest way to use **QuadrilateralFitter** is just one line:\r\n\r\n```python\r\nfrom quadfit import QuadrilateralFitter\r\n\r\n# Fit an input polygon of N sides and get the final quadrilateral directly\r\nquad = QuadrilateralFitter(polygon=your_noisy_polygon).fit()\r\n```\r\n\r\nOptionally, you can trade a bit of accuracy for speed and determinism using the additional arguments of `fit`:\r\n\r\n```python\r\n# Limit the number of initial combinations and fix RNG seed; choose stage with 'until'\r\nquad = QuadrilateralFitter(your_noisy_polygon).fit(\r\n simplify_polygons_larger_than=30,\r\n start_simplification_epsilon=0.1,\r\n max_simplification_epsilon=0.5,\r\n simplification_epsilon_increment=0.02,\r\n max_initial_combinations=1000,\r\n random_seed=123,\r\n until=\"final\", # or \"initial\" / \"refined\"\r\n)\r\n```\r\n\r\n<div align=\"center\">\r\n <img alt=\"Fitting Example 1\" title=\"Fitting Example 1\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/basic_example_1.png\" height=\"250px\">\r\n \r\n <img alt=\"Fitting Example 2\" title=\"Fitting Example 2\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/basic_example_2.png\" height=\"250px\"> \r\n</div>\r\n\r\nIf your application can accept a quadrilateral that does not strictly include all input points, use the tighter initial guess with early stop:\r\n\r\n```python\r\ninitial = QuadrilateralFitter(polygon=your_noisy_polygon).fit(until=\"initial\")\r\n```\r\n\r\n## API Reference\r\n\r\n### QuadrilateralFitter(polygon)\r\n\r\nInitialize the **QuadrilateralFitter** instance.\r\n\r\n- `polygon`: **np.ndarray | tuple | list | object**. Coordinates of the input geometry. Preferred: `np.ndarray` of shape (N, 2) or list/tuple of `(x, y)`. Also accepts objects exposing `.exterior.coords` or `.coords` (e.g., Shapely geometries) via duck\u2011typing. Shapely is NOT required at runtime.\r\n\r\n### QuadrilateralFitter.fit \u2192 tuple of 4 (x, y)\r\n\r\nSignature:\r\n\r\n```python\r\nQuadrilateralFitter.fit(\r\n simplify_polygons_larger_than: int | None = 10,\r\n start_simplification_epsilon: float = 0.1,\r\n max_simplification_epsilon: float = 0.5,\r\n simplification_epsilon_increment: float = 0.02,\r\n max_initial_combinations: int = 300,\r\n random_seed: int | None = None,\r\n until: Literal[\"initial\", \"refined\", \"final\"] = \"final\",\r\n auto_scale_simplification: bool = True,\r\n max_points_for_refinement: int | None = None,\r\n) -> tuple[tuple[float, float], tuple[float, float], tuple[float, float], tuple[float, float]]\r\n```\r\n\r\n- `simplify_polygons_larger_than`: If specified, performs a preliminary Douglas\u2013Peucker simplification of the convex hull when it has more than this many vertices. This speeds up the process but may lead to a slightly sub\u2011optimal quadrilateral. Default: 10.\r\n- `start_simplification_epsilon`, `max_simplification_epsilon`, `simplification_epsilon_increment`: Epsilon schedule for the Douglas\u2013Peucker simplification.\r\n- `max_initial_combinations`: Limits the number of candidate quadrilaterals tested when searching the initial guess. If 0 or larger than the total number of combinations C(N,4), a full search is performed. Otherwise, up to this many unique combinations are sampled randomly. Default: 300.\r\n- `random_seed`: RNG seed for deterministic sampling when `max_initial_combinations` is used. Default: None.\r\n- `until`: Choose how far the pipeline should run for performance. `\"initial\"` returns only the initial guess, skipping finetune/expansion. `\"refined\"` runs TLS finetuning but skips final expansion. `\"final\"` runs the full pipeline. Default: `\"final\"`.\r\n- `auto_scale_simplification`: If `True`, scales Douglas\u2013Peucker epsilon parameters by the input size (bounding box diagonal) when epsilons look relative (<= 1). Helps keep simplification consistent across scales. Default: `True`.\r\n- `max_points_for_refinement`: Optional cap for the number of points used in the TLS finetuning stage. If the input has more points, a deterministic subsample is used (or RNG with `random_seed`). This can dramatically reduce runtime on very large point clouds with minimal accuracy loss. Default: `None` (use all points).\r\n\r\n**Returns**: A 4-vertex quadrilateral (counter-clockwise) for the requested stage:\r\n- `until=\"initial\"`: best IoU vs convex hull (may not contain all points)\r\n- `until=\"refined\"`: after TLS finetuning\r\n- `until=\"final\"`: expanded to strictly contain the convex hull (default)\r\n\r\n\r\n## Real Case Example\r\n\r\nLet's simulate a real case scenario where we detect a noisy polygon from a form that we know should be a perfect rectangle (only deformed by perspective).\r\n\r\n```python\r\nimport numpy as np\r\nimport cv2\r\n\r\nimage = cv2.cvtColor(cv2.imread('./resources/input_sample.jpg'), cv2.COLOR_BGR2RGB) \r\n\r\n# Save the Ground Truth corners\r\ntrue_corners = np.array([[50., 100.], [370., 0.], [421., 550.], [0., 614.], [50., 100.]], dtype=np.float32)\r\n\r\n# Generate a simulated noisy detection\r\nsides = [np.linspace([x1, y1], [x2, y2], 20) + np.random.normal(scale=10, size=(20, 2))\r\n for (x1, y1), (x2, y2) in zip(true_corners[:-1], true_corners[1:])]\r\nnoisy_corners = np.concatenate(sides, axis=0)\r\n\r\n# To simplify, we will clip the corners to be within the image\r\nnoisy_corners[:, 0] = np.clip(noisy_corners[:, 0], a_min=0., a_max=image.shape[1])\r\nnoisy_corners[:, 1] = np.clip(noisy_corners[:, 1], a_min=0., a_max=image.shape[0])\r\n```\r\n<div align=\"center\">\r\n<img alt=\"Input Sample\" title=\"Input Sample\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/input_noisy_detection.png\" height=\"300px\" align=\"center\">\r\n</div>\r\n\r\nAnd now, let's run **QuadrilateralFitter** to find the quadrilateral that best approximates our noisy detection (without leaving points outside).\r\n\r\n```python\r\nfrom quadfit import QuadrilateralFitter\r\n\r\n# Define the fitter and compute desired stages\r\nfitter = QuadrilateralFitter(polygon=noisy_corners)\r\nfitted_quadrilateral = np.array(fitter.fit(until=\"final\"), dtype=np.float32)\r\n# Tighter quadrilateral (may exclude some points):\r\ntight_quadrilateral = np.array(fitter.fit(until=\"initial\"), dtype=np.float32)\r\n```\r\n\r\n<div align=\"center\">\r\n <img alt=\"Fitting Process\" title=\"Fitting Process\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/fitting_process.png\" height=\"300px\">\r\n \r\n <img alt=\"Fitted Quadrilateral\" title=\"Fitted Quadrilateral\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/fitted_quadrilateral.png\" height=\"300px\"> \r\n</div>\r\n\r\nFinally, for use cases like this, we could use fitted quadrilaterals to apply a perspective correction to the image, so we can get a visual insight of the results.\r\n\r\n```python\r\n# Generate the destination points for the perspective correction by adjusting it to a perfect rectangle\r\nh, w = image.shape[:2]\r\n\r\nfor quadrilateral in (fitted_quadrilateral, tight_quadrilateral):\r\n # Cast it to a numpy for agile manipulation\r\n quadrilateral = np.array(quadrilateral, dtype=np.float32)\r\n\r\n # Get the bounding box of the fitted quadrilateral\r\n min_x, min_y = np.min(quadrilateral, axis=0)\r\n max_x, max_y = np.max(quadrilateral, axis=0)\r\n\r\n # Define the destination points for the perspective correction\r\n destination_points = np.array(((min_x, min_y), (max_x, min_y),\r\n (max_x, max_y), (min_x, max_y)), dtype=np.float32)\r\n\r\n # Calculate the homography matrix from the quadrilateral to the rectangle\r\n homography_matrix, _ = cv2.findHomography(srcPoints=quadrilateral, dstPoints=destination_points)\r\n # Warp the image using the homography matrix\r\n warped_image = cv2.warpPerspective(src=image, M=homography_matrix, dsize=(w, h))\r\n```\r\n\r\n<div align=\"center\">\r\n <img alt=\"Input Segmentation\" title=\"Input Segmentation\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/input_segmentation.png\" height=\"230px\">\r\n <img alt=\"Corrected Perspective Fitted\" title=\"Corrected Perspective Fitted\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/corrected_perspective_fitted.png\" height=\"230px\">\r\n <img alt=\"Corrected Perspective Tight\" title=\"Corrected Perspective Tight\" src=\"https://raw.githubusercontent.com/KMChris/quadfit/main/resources/corrected_perspective_tight.png\" height=\"230px\">\r\n</div>\r\n",
"bugtrack_url": null,
"license": null,
"summary": "Fork of QuadrilateralFitter rewritten in C. QuadrilateralFitter is an efficient and easy-to-use Python library for fitting irregular quadrilaterals from irregular polygons or any noisy data.",
"version": "1.1.0",
"project_urls": {
"Homepage": "https://github.com/KMChris/quadfit"
},
"split_keywords": [
"quadrilateral",
" fitter",
" polygon",
" shape analysis",
" geometry"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "3ea8c7dd9feb8ccbcfe893bd5dada3b75f8e8a1bbcfb819f7eabbae682fa640d",
"md5": "d7e9206c7bdee17ee7e2d9d3ca8e099c",
"sha256": "aa317f27009cc1b9ee3796f7591616d3f17136380708b629d1969615d52df8c2"
},
"downloads": -1,
"filename": "quadfit-1.1.0-cp311-cp311-win_amd64.whl",
"has_sig": false,
"md5_digest": "d7e9206c7bdee17ee7e2d9d3ca8e099c",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.9",
"size": 43732,
"upload_time": "2025-09-13T00:22:25",
"upload_time_iso_8601": "2025-09-13T00:22:25.839749Z",
"url": "https://files.pythonhosted.org/packages/3e/a8/c7dd9feb8ccbcfe893bd5dada3b75f8e8a1bbcfb819f7eabbae682fa640d/quadfit-1.1.0-cp311-cp311-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "873ab749dc5bb6ffda33780f9778d898e0c460272137fd59a64efb9632ff8e80",
"md5": "3cec5cad4e9ac740c0d2cfb573a2153b",
"sha256": "ec8ab6c6228f676a557264997afa3932cda0ba7de746d8720a81ed0c14751a2b"
},
"downloads": -1,
"filename": "quadfit-1.1.0.tar.gz",
"has_sig": false,
"md5_digest": "3cec5cad4e9ac740c0d2cfb573a2153b",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 23570,
"upload_time": "2025-09-13T00:22:26",
"upload_time_iso_8601": "2025-09-13T00:22:26.801151Z",
"url": "https://files.pythonhosted.org/packages/87/3a/b749dc5bb6ffda33780f9778d898e0c460272137fd59a64efb9632ff8e80/quadfit-1.1.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-09-13 00:22:26",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "KMChris",
"github_project": "quadfit",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [
{
"name": "numpy",
"specs": []
}
],
"lcname": "quadfit"
}
