Polygon to circle

[thoma.v]

Hi Odforce!
I have a large three-dimensional hexagonal mesh. Now I need to approximate every polygon of it by a circle that best fits the given shape. What would be the most efficient way to address this problem in Houdini?

Any opinions or suggestions are greatly appreciated!

[loopyllama]

so you want to replace a bunch of triangles with circles?

http://www.efunda.com/math/areas/circleinscribetrianglegen.cfm

 

take your mesh, feed it into a divide and turn on compute dual (gives you the midpoints),  add the radius math to each midpoint after the divide, feed that into a copy sop that takes a circle. stamp radius value into the circle radius

[michael]

you could try the measure SOP - set to area, then place a circle at the prim centre with a radius defined by the radius

or the average distance from the centroid to the points...

upload a sample mesh if you need more help

[thoma.v]

Thanks Jim, thanks Michael!

@Jim: The polygons are not triangles but hexagons so I don´t think the math will work.

@Michael: That is a great idea and works like a charm for regular polygons. Unfortunately it does not work so good for distorted ones. I´ve uploaded a small part of the model where you can see the problem.

 

Thanks again! 

polyToCircle.hipnc

[mestela]

convert sop in circle mode?

 

it tends to fit to the widest rather than the smallest size, a prim sop to tweak the scale of each prim before the convert can be used to fudge it. works pretty well for most cases.

 

 

fit_circles.hipnc

[thoma.v]

Thanks Matt but that´s what I did in the uploaded file. One problem is that I need circles not ellipses . The other one is the center of the circle. When I transform a circle to find a good approximation "by hand" it seems that its center does not correspond with the centroid of the polygon and so far I have no idea how to tackle this problem.

[michael]

yeah - I figured this would happen...

matt has a nice idea

you could also build curves in a foreach that connect the points of each hexagon...

but now we're entering Crazytown...

[mestela]

Heh, serves me right for not looking at your scene first.

 

Here's the start of an idea, needs improvement. Basically iterate through each hexagon, get the points, calculate the midpoints of the edges, measure the distance between each opposite pair of edges, determine the shortest one, create a point at the midpoint of the shortest width, and set the radius from that.

 

Doesn't handle concave shapes very well, and its hardcoded for hexagons, but should give you a start. Google seems to have lots of examples of inscribing a circle in a hexagon, should be trivial (!?!) to apply that to the little vex wrangle here.

 

polyToCircle2.hipnc

 

Edited February 24, 2016 by mestela

[anim]

you can find straight skeleton using PolyExpand SOP which will give you distance as well, then just construct circle from the furthest point

 

it should work for both convex and concave n-gons, they will however be flattened to best fit plane

ts_incircles.hipnc

[Shinjipierre]

define "that best fits the given shape"

 

do you mean the largest circle contained in the primitive or can it just get bigger than the shape?

[thoma.v]

Thanks Matt, thanks Tomas for the scene files! Unfortunately this is not what I was looking for. My apologies for the confusion and my vague description of the problem!

I´ll do my best to explain what I´m after: What I´m trying to do is to measure the average deviation between the polygon and the circle. In this context "circle that best fits the given shape" means to find a circle such that the distance to all points of the polygon is as small as possible. It´s kinda hard to explain in words but the picture should show what I mean.

 

Thanks again!

Edited February 24, 2016 by thoma.v

[f1480187]

Yet another method.

 

// Primitive Wrangle.
// Radius from mean centroid-to-point distances.
addpointattrib(0, "N", {0.0, 0.0, 0.0});
addpointattrib(0, "pscale", 0.0);

float dists[];
foreach (int pt; primpoints(0, @primnum))
{
    vector pt_pos = point(0, "P", pt);
    float dist = distance(@P, pt_pos);
    append(dists, dist);
}
float mean_dist = avg(dists);

int pt = addpoint(0, @P);
setpointattrib(0, "pscale", pt, mean_dist);
setpointattrib(0, "N", pt, @N);

removeprim(0, @primnum, true);

average_circles.hipnc

[thoma.v]

Many thanks, that´s a nice solution and works very well for most of the polygons. Finding the circle-center for the few distorted ones is still a problem but I have a vague idea how to resolve this in a Foreach-Sop. I´ll let you know how it goes.

 

 

 

[michael]

are you making chain mail?

[petz]

there are different ways how you can do this depending on geometry and accuracy. generally it´s a typical minimization problem and could be solved by using a least squares approach but you can also try to solve it geometrically.
if you compute the largest inscribed and the smallest circumsribed circle you´ll get a good approximation by blending between them. for the inner circle rely on the file from anim or use the one in this thread (for pre-houdini 15 versions). for the outer circle use the bounding sop in sphere mode.
another method would be to find the intersections of two lines orthogonal to all consecutive edges. calculate the average of all intersection which are inside the prim and you´ll get the center of the circle. after that compute the average distance to the vertices and use this as radius.
the third option would be to find the best fittiing circle by using least squares. this works for pretty much every case and ensures that the squared sum of distances from all points to the circle is the smallest possible.

hth.
petz

polyToCircle1.hipnc

[thoma.v]

Thanks Petz, that's what I was looking for! Works like a charm!

@Michael: Ha, ha, no, not a chain mail! I work in the field of computational design and would like to know how much every polygon deviates from a regular shaped hexagon. Use it fo a chain mail is not a bad idea, though.