Searching an algorithm to find the center of concave and convex 2d polygons...

[jke]

Hi,

I'm searching for an algorithm with that I can find the 'center' of any 2D Polygon.
I think it is not really the center I search, but I don't know if there is an special name for the point I search.

I attached and an example of two Polygons to this new thread. I search the point in the Polygon where I can draw the biggest circle. Normally this point ist the center but not in these two polygons.

Let me know if you need any more information.

Thanks for any tips.

Jürgen

[cilu]

[ redirected ]

[prometheuzz]

Such a polygon has a "centroid" or "center of gravity". An algorithm is given here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/

[jke]

yes, there are two algorithms under centroid, but I don't know what I should do with them. (I'm not an mathematic professional.) Isn't there an easier example, or can I get with one of the sample sources on this page the centroid? Thanks again for your help.

[jke]

ok, now I've tried it with the sample code from here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/source2.java

I converted this code in my project (c++). So it looks now like this:

double_gs area = 0.0;
int j = 0;
int i = 0;
for(i = 0; i < anz_punkte_effektiv; i++){
j = (i+1) % anz_punkte_effektiv;
area += temp[i].x * temp[j].y;
area -= temp[i].y * temp[j].x;
}
area /= 2.0;

double_gs cx, cy;
cx = 0.0;
cy = 0.0;
double_gs A = area;
i = 0;
j = 0;
double_gs factor = 0.0;
for(i = 0; i < anz_punkte_effektiv; i++){
j = (i+1) % anz_punkte_effektiv;
factor = (temp[i].x*temp[j].y - temp[j].x*temp[i].y);
cx += (temp[i].x + temp[j].x)*factor;
cy += (temp[i].y + temp[j].y)*factor;
}
A *= 6.0f;
factor = 1/A;
cx *= factor;
cy *= factor;

anz_punkte_effektiv is the number of points, and temp is the array of the points of the polygon.

This code will return the correct area of the polygon, but cx and cy, the point of the centroid is not inside the polygon. I attach an picture of the point I receive. This point is not in the polygon, but the point must be inside. Thanks for any tipps.

[prometheuzz]

... This point is not in the polygon, but the point must be inside. Thanks for any tipps.

Ah, okay, then you are not looking for the centroid of a polygon. Perhaps you could "tighten" your definition of the point you're looking for. By looking at the 2nd polygon from the picture in your original post, it is not entirely clear because the circle can be moved is a northern or southern direction and still be the biggest circle.

[jke]

ok, then it is not the centroid of the polygon. I don't know if there is a special name for the point I search. I know that in the second picture of the original post you can move the point in the north or south and it's almost the biggest circle. There it doesn't matter which point will be chosen. I need only one of the points inside of the polygon, where I can draw the biggest circle. Thee circle should also be complete inside of the polygon. Maybe there is a special name for this point I search?

[GremlinSA]

Okay i dont have any algo's or code snips to offer but i do have an idea, or method to offer to the problem ...

Divide the shape into the smaler sub shapes that occur with in it.. (Track each line of the object outwards and check it it intersects anywhere, If it does you've found your subshape..

Get the area of all the subshapes, and the subshape with the larger area, is posibly the subshape that will fit the largest Circle..

I'm not much into C, so i wont be able to asist with coding it..

Gremmy...

[pm_kirkham]

The locus of the centre of the set of circles touching at least two edges of a polygon is called the 'medial axis'. You want a point on the medial axis where the radius of the circle is a maximum.

There are some algorithms for medial axis if you google, but I'm not familiar enough with it to recommend any one in particular. You should be able to demonstrate that the maximum radius will be either where the two edges touched are parallel or where the circle touches more than two edges, so you can prune some of the medial axis away quickly.

[prometheuzz]

The locus of the centre of the set of circles touching at least two edges of a polygon is called the 'medial axis'. You want a point on the medial axis where the radius of the circle is a maximum.

There are some algorithms for medial axis if you google, but I'm not familiar enough with it to recommend any one in particular. You should be able to demonstrate that the maximum radius will be either where the two edges touched are parallel or where the circle touches more than two edges, so you can prune some of the medial axis away quickly.

Since the OP is working with non convex polygons, the 'medial axis' will (always?) contain curved line segments.
Would it be easier to chop the non convex polygon in a (minimal) number of "regular" convex polygons, leaving you with straight line segments, and then "drawing" the circles on the vertices of those line segments?