0
# Circle-Fit
1

2
A comprehensive collection of circle fitting algorithms for Python that enable finding optimal circle parameters from 2D point data. Circle-fit implements multiple sophisticated algorithms including hyperLSQ for high-accuracy least squares fitting, standardLSQ for basic least squares, various SVD-based algebraic approaches (Pratt, Taubin, hyperSVD), geometric methods (Riemann SWFL), iterative optimization (Levenberg-Marquardt), and consistent fitting (KMH method). All algorithms provide a uniform API and support both Python lists and NumPy arrays as input.
3

4
## Package Information
5

6
- **Package Name**: circle-fit
7
- **Language**: Python
8
- **Installation**: `pip install circle-fit`
9

10
## Core Imports
11

12
```python
13
from circle_fit import taubinSVD, hyperLSQ, standardLSQ, plot_data_circle
14
from typing import Union, List, Tuple
15
import numpy as np
16
import numpy.typing as npt
17
```
18

19
Import all available algorithms:
20

21
```python
22
from circle_fit import (
23
    riemannSWFLa, lm, prattSVD, taubinSVD, hyperSVD, 
24
    kmh, hyperLSQ, standardLSQ, plot_data_circle
25
)
26
from typing import Union, List, Tuple
27
import numpy as np
28
import numpy.typing as npt
29
```
30

31
Legacy aliases:
32

33
```python
34
from circle_fit import hyper_fit, least_squares_circle
35
```
36

37
## Basic Usage
38

39
```python
40
from circle_fit import taubinSVD, plot_data_circle
41
import numpy as np
42

43
# Create sample 2D points (as Python list)
44
point_coordinates = [[1, 0], [-1, 0], [0, 1], [0, -1]]
45

46
# Fit a circle using Taubin SVD algorithm (recommended default)
47
xc, yc, r, sigma = taubinSVD(point_coordinates)
48
print(f"Center: ({xc:.3f}, {yc:.3f}), Radius: {r:.3f}, Error: {sigma:.6f}")
49

50
# Also works with NumPy arrays
51
points_array = np.array([[1, 0], [-1, 0], [0, 1], [0, -1]])
52
xc, yc, r, sigma = taubinSVD(points_array)
53

54
# Visualize the fit (requires matplotlib)
55
plot_data_circle(point_coordinates, xc, yc, r)
56
```
57

58
## Capabilities
59

60
### Recommended Algorithm
61

62
For most use cases, `taubinSVD()` provides a good balance of accuracy and robustness.
63

64
```python { .api }
65
def taubinSVD(coords: Union[npt.NDArray, List]) -> Tuple[float, ...]:
66
    """
67
    Algebraic circle fit by G. Taubin using SVD.
68
    
69
    Parameters:
70
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
71
    
72
    Returns:
73
    tuple: (xc, yc, r, sigma) where:
74
        - xc (float): x coordinate of circle center
75
        - yc (float): y coordinate of circle center  
76
        - r (float): radius of fitted circle
77
        - sigma (float): RMS error of the fit
78
    """
79
```
80

81
### High-Accuracy Least Squares
82

83
For maximum accuracy when precision is critical.
84

85
```python { .api }
86
def hyperLSQ(coords: Union[npt.NDArray, List], iter_max: int = 99) -> Tuple[float, ...]:
87
    """
88
    Hyper least squares fitting with "hyperaccuracy" by Kenichi Kanatani, Prasanna Rangarajan.
89
    
90
    Parameters:
91
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
92
    - iter_max (int, optional): Maximum number of iterations. Defaults to 99.
93
    
94
    Returns:
95
    tuple: (xc, yc, r, sigma) where:
96
        - xc (float): x coordinate of circle center
97
        - yc (float): y coordinate of circle center  
98
        - r (float): radius of fitted circle
99
        - sigma (float): RMS error of the fit
100
    """
101
```
102

103
### Standard Least Squares
104

105
Basic least squares circle fitting for simple cases.
106

107
```python { .api }
108
def standardLSQ(coords: Union[np.ndarray, List]) -> Tuple[float, ...]:
109
    """
110
    Standard least squares circle fitting.
111
    
112
    Parameters:
113
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
114
    
115
    Returns:
116
    tuple: (xc, yc, r, sigma) where:
117
        - xc (float): x coordinate of circle center
118
        - yc (float): y coordinate of circle center  
119
        - r (float): radius of fitted circle
120
        - sigma (float): RMS error of the fit
121
    """
122
```
123

124
### Geometric Optimization
125

126
Levenberg-Marquardt algorithm minimizing orthogonal distances in full parameter space.
127

128
```python { .api }
129
def lm(coords: Union[npt.NDArray, List], par_ini: npt.NDArray, iter_max: int = 50, lambda_ini: float = 1, epsilon: float = 0.00001) -> Tuple[float, ...]:
130
    """
131
    Geometric circle fit using Levenberg-Marquardt scheme.
132
    
133
    Parameters:
134
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
135
    - par_ini: 1D np.ndarray. Array of [xc, yc, r] initial guess.
136
    - iter_max (int, optional): Maximum iterations. Defaults to 50.
137
    - lambda_ini (float, optional): Initial correction factor. Defaults to 1.
138
    - epsilon (float, optional): Convergence threshold. Defaults to 0.00001.
139
    
140
    Returns:
141
    tuple: (xc, yc, r, sigma) where:
142
        - xc (float): x coordinate of circle center
143
        - yc (float): y coordinate of circle center  
144
        - r (float): radius of fitted circle
145
        - sigma (float): RMS error of the fit
146
    """
147
```
148

149
### SVD-Based Algebraic Methods
150

151
Fast algebraic approaches using Singular Value Decomposition.
152

153
```python { .api }
154
def prattSVD(coords: Union[npt.NDArray, List]) -> Tuple[float, ...]:
155
    """
156
    Algebraic circle fit by V. Pratt using SVD.
157
    
158
    Parameters:
159
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
160
    
161
    Returns:
162
    tuple: (xc, yc, r, sigma) where:
163
        - xc (float): x coordinate of circle center
164
        - yc (float): y coordinate of circle center  
165
        - r (float): radius of fitted circle
166
        - sigma (float): RMS error of the fit
167
    """
168

169
def hyperSVD(coords: Union[npt.NDArray, List]) -> Tuple[float, ...]:
170
    """
171
    Algebraic circle fit with "hyperaccuracy" using SVD.
172
    
173
    Parameters:
174
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
175
    
176
    Returns:
177
    tuple: (xc, yc, r, sigma) where:
178
        - xc (float): x coordinate of circle center
179
        - yc (float): y coordinate of circle center  
180
        - r (float): radius of fitted circle
181
        - sigma (float): RMS error of the fit
182
    """
183
```
184

185
### Specialized Algorithms
186

187
Advanced algorithms for specific use cases.
188

189
```python { .api }
190
def riemannSWFLa(coords: Union[npt.NDArray, List]) -> Tuple[float, ...]:
191
    """
192
    Riemann circle fit, SWFL version A by Strandlie, Wroldsen, Fruhwirth, and Lillekjendlie.
193
    
194
    Parameters:
195
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
196
    
197
    Returns:
198
    tuple: (xc, yc, r, sigma) where:
199
        - xc (float): x coordinate of circle center
200
        - yc (float): y coordinate of circle center  
201
        - r (float): radius of fitted circle
202
        - sigma (float): RMS error of the fit
203
    """
204

205
def kmh(coords: Union[npt.NDArray, List], iter_max: int = 99, epsilon: float = 1E-9) -> Tuple[float, ...]:
206
    """
207
    Consistent circle fit by A. Kukush, I. Markovsky, S. Van Huffel.
208
    
209
    Parameters:
210
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
211
    - iter_max (int, optional): Maximum iterations. Defaults to 99.
212
    - epsilon (float, optional): Convergence threshold. Defaults to 1E-9.
213
    
214
    Returns:
215
    tuple: (xc, yc, r, sigma) where:
216
        - xc (float): x coordinate of circle center
217
        - yc (float): y coordinate of circle center  
218
        - r (float): radius of fitted circle
219
        - sigma (float): RMS error of the fit
220
    """
221
```
222

223
### Visualization
224

225
Plot data points with fitted circle overlay.
226

227
```python { .api }
228
def plot_data_circle(coords: Union[npt.NDArray, List], xc: float, yc: float, r: float) -> None:
229
    """
230
    Plot data points with fitted circle overlay using matplotlib.
231
    
232
    Parameters:
233
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
234
    - xc (float): x coordinate of circle center
235
    - yc (float): y coordinate of circle center  
236
    - r (float): radius of fitted circle
237
    
238
    Returns:
239
    None
240
    
241
    Raises:
242
    ModuleNotFoundError: If matplotlib is not installed.
243
    """
244
```
245

246
### Legacy Aliases
247

248
Deprecated functions provided for backwards compatibility.
249

250
```python { .api }
251
def hyper_fit(coords: Union[npt.NDArray, List], IterMax: int = 99) -> Tuple[float, ...]:
252
    """
253
    Deprecated alias for hyperLSQ().
254
    
255
    Parameters:
256
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
257
    - IterMax (int, optional): Maximum iterations. Defaults to 99.
258
    
259
    Returns:
260
    tuple: (xc, yc, r, sigma)
261
    
262
    Note:
263
    This function is deprecated. Use hyperLSQ() instead.
264
    """
265

266
def least_squares_circle(coords: Union[npt.NDArray, List]) -> Tuple[float, ...]:
267
    """
268
    Deprecated alias for standardLSQ().
269
    
270
    Parameters:
271
    - coords: 2D List or 2D np.ndarray of shape (n,2). X,Y point coordinates.
272
    
273
    Returns:
274
    tuple: (xc, yc, r, sigma)
275
    
276
    Note:
277
    This function is deprecated. Use standardLSQ() instead.
278
    """
279
```
280

281
## Types
282

283
```python { .api }
284
# Input coordinate formats
285
CoordinateInput = Union[List[List[float]], npt.NDArray]
286

287
# Return type for all fitting functions  
288
CircleFitResult = Tuple[float, float, float, float]
289
# (xc: center x, yc: center y, r: radius, sigma: RMS error)
290

291
# Initial parameter guess for lm() function
292
InitialParameters = npt.NDArray  # Shape: (3,) containing [xc, yc, r]
293
```
294

295
## Error Handling
296

297
Common exceptions that may be raised:
298

299
- **Exception**: Raised by `convert_input()` for unsupported coordinate input types
300
- **ModuleNotFoundError**: Raised by `plot_data_circle()` when matplotlib is not installed
301
- **AssertionError**: Raised by `convert_input()` for incorrectly shaped numpy arrays
302
- **Numerical errors**: Various algorithms may encounter numerical instability with degenerate point sets
303

304
## Usage Examples
305

306
### Comparing Multiple Algorithms
307

308
```python
309
from circle_fit import taubinSVD, hyperLSQ, standardLSQ
310
import numpy as np
311

312
# Sample noisy circle data
313
np.random.seed(42)
314
theta = np.linspace(0, 2*np.pi, 20)
315
true_center = (5, 3)
316
true_radius = 10
317
noise_level = 0.5
318

319
x = true_center[0] + true_radius * np.cos(theta) + np.random.normal(0, noise_level, 20)
320
y = true_center[1] + true_radius * np.sin(theta) + np.random.normal(0, noise_level, 20)
321
coords = np.column_stack([x, y])
322

323
# Compare different algorithms
324
algorithms = [
325
    ("Taubin SVD", taubinSVD),
326
    ("Hyper LSQ", hyperLSQ), 
327
    ("Standard LSQ", standardLSQ)
328
]
329

330
for name, algorithm in algorithms:
331
    xc, yc, r, sigma = algorithm(coords)
332
    print(f"{name}: Center=({xc:.2f}, {yc:.2f}), Radius={r:.2f}, Error={sigma:.4f}")
333
```
334

335
### Using Levenberg-Marquardt with Initial Guess
336

337
```python
338
from circle_fit import lm, taubinSVD
339
import numpy as np
340

341
# First get a rough estimate using Taubin SVD
342
coords = [[1, 0], [-1, 0], [0, 1], [0, -1], [0.5, 0.8]]
343
xc_init, yc_init, r_init, _ = taubinSVD(coords)
344

345
# Use as initial guess for high-precision LM algorithm
346
par_ini = np.array([xc_init, yc_init, r_init])
347
xc, yc, r, sigma = lm(coords, par_ini)
348
print(f"LM result: Center=({xc:.6f}, {yc:.6f}), Radius={r:.6f}, Error={sigma:.8f}")
349
```