how to get the largest circle inside a concave shape

[oatcracker]

Hi, may I ask how to get the largest circle inside a concave polygon in whatever shape in Houdini?

 

Thanks!

[oatcracker]

sorry, what I mean is convex shape polygon ...

[eetu]

An interesting problem, this

 

It seems there is no general solution for this (after some googling). Here is a try using iteration - in some cases this method converges very slowly (you can spot the nonoptimal ones in the screenshot) so there is clear room for improvement. Also you could check for triangles and use the exact solution for those.

ee_incircles.hip

[Shinjipierre]

Thought that was a fun problem as well. (how nerdy is that on a scale of 1 to Stephen Hawking?)

I did my own quick answer to it. It could be optimized with iterations instead of sampling zillion of times but I'm lazy

I also added a counter to check which answer has most area covered. 

 

edit : noticed that I forgot to attach my file....

ee_incircles_v2.hipnc

Edited September 29, 2014 by Shinjipierre

[oat]

interesting solution, eetu! May I ask what's going on inside the foreach_iterate node, especially the two ray nodes? Thanks!

[eetu]

The ray node finds the closest point on the polygon edges, and then the following point node nudges the center point away from that direction. Repeat many times, always nudging by a smaller amount, and you should end up with a pretty good approximation of the point where there is the most room around it.

 

Shinjipierre's brute force method uses point cloud lookups to find the closest point, which is probably quite a bit faster. His method seems to be quite a bit faster with better results, so I recommend using that (And it works with inconvex shapes as well)

[Skybar]

A bit slow, but a quickie 3D-version with:

ee_incircles_v3.hipnc

 

[3__]

clever answers

next question: how would you get the largest rectangle inside the polygon?

[magneto]

Is there a non-approximate way to do this?

[eetu]

Is there a non-approximate way to do this?

 

As far as I know, nope.

(except for triangles)

 

clever answers

next question: how would you get the largest rectangle inside the polygon?

 

Now that is nasty

Edited September 30, 2014 by eetu

[magneto]

As far as I know, nope.

(except for triangles)

 

Do you think one could do this for triangles defined by the polygon and then combine these circles? I assume calculating the circle that contains other circles is trivial?

[eetu]

Do you think one could do this for triangles defined by the polygon and then combine these circles? I assume calculating the circle that contains other circles is trivial?

 

Sadly, I don't think it works that way, but keep thinking!

 

[Shinjipierre]

 how would you get the largest rectangle inside the polygon?

 

 

You mean, largest area, I guess... That sounds complicated

[petz]

Is there a non-approximate way to do this?

 

one way would be to solve it geometrically by building the polygon skeleton. one of the resulting points is per definition the centerpoint of the largest inscribed circle. should also work with non-convex polygons.

the following example might be a good start

http://forums.odforce.net/topic/14151-roof-generator/?p=116552

[eetu]

one way would be to solve it geometrically by building the polygon skeleton. one of the resulting points is per definition the centerpoint of the largest inscribed circle. should also work with non-convex polygons.

the following example might be a good start

 

Ohhhh that's very interesting, I didn't realize that at all. cool!

[magneto]

 

one way would be to solve it geometrically by building the polygon skeleton. one of the resulting points is per definition the centerpoint of the largest inscribed circle. should also work with non-convex polygons.
the following example might be a good start

http://forums.odforce.net/topic/14151-roof-generator/?p=116552

 

Thansk petz, I was expecting you

[oat]

Thank you all very much!

 

I got a lot to digest and learn from your advices, especailly the iterative process.

 

Much obligied!

[Shinjipierre]

one way would be to solve it geometrically by building the polygon skeleton. one of the resulting points is per definition the centerpoint of the largest inscribed circle. should also work with non-convex polygons.

 

 

But that center point also seems to be approximated. (briefly looking at the file, that's a cool process).

Also, with that method you'll still have to approximate the largest radius by sampling the edges, nah?

[petz]

But that center point also seems to be approximated. (briefly looking at the file, that's a cool process).

Also, with that method you'll still have to approximate the largest radius by sampling the edges, nah?

 

why would that be an approximation?

the polygon skeleton can be computed with floating point precision and if you have the skeleton you also have the exact centerpoint of the largest circle. the only thing left to do is finding the radius. this could be done with a bit of vector math (again floating point precision) or for example by using xyzdist() in vex. so, all in all i would say you´ll get a pretty good result.

sampling the edges is not necessary since you just need the distance between a point and a line. well, not entirely true as long as you are using xyzdist() because this function relays on GU_RayIntersect where the distance is computed essentially by shooting rays. but i´m not sure if this is what you meant?

largest_circle.hipnc