May 25th, 2012 - Medial Axis

I thought this group sounded like a fun idea, so I thought I would suggest one based on something I was looking at earlier in the week.

The challenge:

To find the medial axis of a 2d polygon in 15 native components or less without scripting.

http://en.wikipedia.org/wiki/Medial_axis

http://w3.impa.br/~paesleme/MedialAxis/MedialAxis.html

Good luck!

Attachments:

leaf_shape_lobed(7).gif, 3 KB

Replies to This Discussion

Permalink Reply by Luis Fraguada on May 25, 2012 at 6:53am

http://stackoverflow.com/questions/1069523/find-medial-axis-of-a-po...

I've looked at this before, but I do not think it's actually the medial axis, but an approximation. I think Daniel has done some work with these.

My entry, though again, I do not think it is exactly the medial axis.

Attachments:

mAxis.gh, 8 KB

Permalink Reply by Luis Fraguada on May 25, 2012 at 7:39am

A second version which is more like Daniel's original solution to use a set of points along the boundary curve...same number of components. Reduced both by one component towards the end...

Attachments:

mAxis2.gh, 16 KB

Permalink Reply by Luis Fraguada on May 25, 2012 at 8:03am

Ok, and one more, to deal with 'islands' within the boundary curve. Inspired by this post on codequotidien.

Attachments:

mAxis3.gh, 25 KB

Permalink Reply by rebecca on February 26, 2016 at 6:37pm

Hi Luis,

I created this geometry via tspline tweaks on Rhino.

In order to have more control over the generative form, I was looking up ways to work with tsplines in grasshopper and found threads on voronoi medial axes.

I ran your definition and wondering how best to apply tsplines to the resulting voronoi curves? Or is this even the best way?

Many thanks again - your definition was very helpful.

Attachments:

Section Cut 1A T1.jpg, 192 KB

Permalink Reply by Mateusz Zwierzycki on May 25, 2012 at 8:06am

As far as I know, this is not medial axis - cant remind where I read about this ;/

But the paper Adam linked seems to tell something else - so really dont know now :)

Permalink Reply by Luis Fraguada on May 25, 2012 at 8:17am

Yes, like I said, I think it's an approximation, but perhaps not the real deal....

Permalink Reply by Luis Fraguada on May 25, 2012 at 9:30am

For the points to lie on the medial axis, they should be equidistant from more than one point on the boundary. As we can see here, this gets close, but does not hold up to the definition of Medial Axis...

Permalink Reply by Mateusz Zwierzycki on May 25, 2012 at 1:26pm

I bet this is how GCode for V carving is made. Do you know about any papers that show how to make exact medial axis ? Wikipedia says that curves of medial axis are parabolic, so should be possible to do that.

Back to GCode : distance to closest point on curve = Z axis movement.

Permalink Reply by Luis Fraguada on May 26, 2012 at 1:56am

5. The poster judges the answer. They should offer a sample solution as well when they declare the winner.

I am looking forward to the sample solution from Adam...

Permalink Reply by Adam Holloway on May 26, 2012 at 5:16am

Well, the solution I got was the same as you Luis (using voronoi), although you did it in less components than me:

It seems though that you have proved that it isn't exactly the medial axis that we are getting, so I guess no one has really succeeded...

I did think though that maybe there is another simple way of doing it, based on the article I posted, by generating circles from sets of 3 points on the curve that have normal vectors at obtuse angles to each other. I am looking into figuring this out now.

Permalink Reply by Adam Holloway on May 26, 2012 at 12:05pm

This method, using a delaunay connectivity diagram, appears more accurate (in theory) and uses less components, but I don't get a curve as a result:

Attachments:

medial axis with delaunay.gh, 3 KB

Permalink Reply by Luis Fraguada on May 27, 2012 at 6:09am

Why is it more accurate? Again, take a look at where those points go when you use a CurveCP component. Using the distance as a radius for a circle, it still does not meet the bounding curve at more than one location...