Forums Technical Discussion Find best-fit circle (automatically)

Find best-fit circle (automatically)

   1966   7   0
User Avatar
element33
Member
94 posts
Joined: Jan. 2015
Offline
 
I have a slightly uneven poly circle. Is there a way to automatically (not manually) find the best-fit circle, i.e. one that minimizes the sum of distances from the poly? It's like finding a "best fit plane" for near-planar points, but for a circle. There's a "Fit Curve" SOP, but it seems to create a very close NURBS approximation of the shape, not a perfect circle.
Edited by element33 - Dec. 30, 2024 00:44:23
 Report
User Avatar
johnmather
Staff
653 posts
Joined: Aug. 2019
Offline
 
Is this circle 2-dimensional or 3-dimensional?
 Report
User Avatar
element33
Member
94 posts
Joined: Jan. 2015
Offline
 
johnmather
Is this circle 2-dimensional or 3-dimensional?
2-D on the XZ plane
 Report
User Avatar
johnmather
Staff
653 posts
Joined: Aug. 2019
Offline
 
In that case, you can approximate the result algebraically by performing something like this: https://scipy-cookbook.readthedocs.io/items/Least_Squares_Circle.html#Using-an-algebraic-approximation [scipy-cookbook.readthedocs.io]

I've attached a hip file that should do what you want. If you scrub the timeline, you'll be able to see the results for different inputs.

Attachments:
fit.png (45.5 KB)
circlefit.hip (213.0 KB)

 Report
User Avatar
element33
Member
94 posts
Joined: Jan. 2015
Offline
 
johnmather
In that case, you can approximate the result algebraically
Excellent, works great. Fortunately, my poly is static, it doesn't rotate or change shape
 Report
User Avatar
element33
Member
94 posts
Joined: Jan. 2015
Offline
 
johnmather
approximate the result algebraically
John (not sure if you'll see this message): I now have a similar, but somewhat different problem. I have a bunch of points that form a line, albeit a slightly uneven one. I'd like to find the most "ideal" line representing these points i.e. one that minimizes distances from all points. I tried the EdgeStraighten SOP, but it looks like it simply establishes a line through the first and last points, which is not what I want. Your numpy code already solves for least squares (LS), but how do I modify it to spit out the two endpoints of the "ideal" line? I'm having trouble converting the "circle-oriented" LS to a "line-oriented" LS . I checked the cookbook recipes, but I only see "LS circle" not "LS line".
Edited by element33 - Jan. 28, 2025 22:16:40
 Report
User Avatar
element33
Member
94 posts
Joined: Jan. 2015
Offline
 
OK, I think I solved it with respect to the Y coord, based on this SO [stackoverflow.com]:

node = hou.pwd()
geo = node.geometry()
import numpy as np
x = [p.position().x() for p in geo.points()]
y = [p.position().y() for p in geo.points()]
z = [p.position().z() for p in geo.points()]
A = np.stack([y, np.ones(len(y))]).T
xm, xc = np.linalg.lstsq(A, x, rcond=None)[0]
zm, zc = np.linalg.lstsq(A, z, rcond=None)[0]
#print(f"xzm: {xzm}, xzc: {xzc}")
geo.addAttrib(hou.attribType.Global,'xm',xm)
geo.addAttrib(hou.attribType.Global,'xc',xc)
geo.addAttrib(hou.attribType.Global,'zm',zm)
geo.addAttrib(hou.attribType.Global,'zc',zc)

Create a line as tall (Y) as the uneven segment, same num of points, same Y min (X=0,Z=0). Align points in VEX, using detail attribs from the Python node:

@P.x+=@P.y*ch('xm')+ch('xc');
@P.z+=@P.y*ch('zm')+ch('zc');
Edited by element33 - Jan. 28, 2025 23:25:21
 Report
User Avatar
johnmather
Staff
653 posts
Joined: Aug. 2019
Offline
 
You can use least squares, but RANSAC would probably be a better choice if there's noise. You should be able to find numpy snippets online. There's a Numpy implementation here:

https://en.wikipedia.org/wiki/Random_sample_consensus [en.wikipedia.org]
Edited by johnmather - Jan. 29, 2025 13:39:16
 Report
  • Quick Links