views:

719

answers:

11

I need to find a point that is a visual center of an irregularly shaped polygon. By visual center, I mean a point that appears to be in the center of a large area of the polygon visually. The application is to put a label inside the polygon.

Here is a solution that uses inside buffering:

http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

If this is to be used, what is an effective and fast way to find the buffer? If any other way is to be used, which is that way?

A good example of really tough polygons is a giant thick U (written in Arial Black or Impact or some such font).

Thanks, M

A: 

This problem would probably be analogous to finding the "center of mass" assuming a uniform density.

EDIT: This method won't work if the polygon has "holes"

Janie
No. See the figure #4 in the ESRI paper that the OP linked to.
Jason S
It seems that my assumption is what they used in #2; the only time it breaks down is under this condition:"However, this method provides an incorrect result if a polygon has holes"
Janie
No. Imagine a giant U. There are no holes, and the center of mass is not inside the boundary of the polygon. I think your answer is correct only for convex polygons.
Jason S
I see, thank you for the clarification.
Janie
You're welcome. I like to criticize rather than downvote :-)
Jason S
Thank you; it'd help if the asker gave us some boundary conditions to work with as well!
Janie
A: 

Compute the centre position (x,y) of each edge of the polygon. You can do this by finding the difference between the positions of the ends of each edge. Take the average of each centre in each dimension. This will be the centre of the polygon.

ire_and_curses
I think this suffers the same problem as my solution when it comes to highly non-convex shapes...
Janie
Yep, and without taking a weighted average it also over-emphasizes short edges, even if the polygon is convex.
Pukku
A: 

I think if you broke the polygon back into it's vertices, and then applied a function to find the largest convex hull , and then find the center off that convex hull, it would match closely with the "apparent" center.

Finding the largest convex hull given the vertices: Look under the Simple Polygon paragraph.

Average the vertices of the convex hull to find the center.

CookieOfFortune
I wonder. What would happen, if my polygon was a giant 'U'?
It would select one of the sides. What is the desired behavior in that situation?
CookieOfFortune
For a giant U, an acceptable solution is the middle of the lower thick section.
If the lower thick section is the largest convex hull, then it would be selected. Is there some type of criteria for selected convex hull to be more of a square?
CookieOfFortune
Wont the largest convex hull cover the entire U and be a rectangle?
Oh, you would need to modify the algorithm to not include any interior vertices.
CookieOfFortune
A: 

If I understand the point of the paper you linked to (quite an interesting problem, btw), this "inside buffering" technique is somewhat analogous to modeling the shape in question out of a piece of sugar that's being dissolved by acid from the edges in. (e.g. as the buffer distance increases, less of the original shape remains) The last bit remaining is the ideal spot to place a label.

How to accomplish this in an algorithm unfortunately isn't very clear to me....

Jason S
GIS softwares like PostGIS have functions like ST_Buffer that do this. I don't know how, so quickly.
A: 

Could you place the label at the naive center (of the bounding box, perhaps), and then move it based on the intersections of the local polygon edges and the label's BB? Move along the intersecting edges' normals, and if multiple edges intersect, sum their normals for movement?

Just guessing here; in this sort of problem I would probably try to solve iteratively as long as performance isn't too much of a concern.

dash-tom-bang
+2  A: 

Have you looked into using the centroid formula?

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

http://en.wikipedia.org/wiki/K-means_algorithm

Arron
Centroid == Center of Mass at Uniform Density
Janie
+2  A: 

If you can convert the polygon into a binary image, then you can use the foundation that exists in the field of image processing, e.g.: A Fast Skeleton Algorithm on Block Represented Binary Images.

But this is not really reasonable in the general case, because of discretization errors and extra work.

However, maybe you find these useful:

EDIT: Maybe you want to look for the point that is the center of the largest circle contained in the polygon. It is not necessarily always in the observed centre, but most of the time would probably give the expected result, and only in slightly pathological cases something that is totally off.

Pukku
Also see http://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons
Oren Trutner
I think these are your best bets by far.You could adapt the above by vertically stretching the polygon by a factor of 2 or 3, then searching for the largest circle contained in the stretched polygon. This will give you the largest *ellipse* contained within the polygon, which will give you the best spot to put your label.
jprete
+1  A: 

How about finding the "incircle" of the polygon (the largest circle that fits inside it), and then centering the label at the center of that? Here are a couple of links to get you started:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

This won't work perfectly on every polygon, most likely; a polygon that looked like a C would have the label at a somewhat unpredictable spot. But the advantage would be that the label would always overlap a solid part of the polygon.

Kyralessa
Won't this be slow if a polygon has several triangulations?
I don't know; will it?
Kyralessa
A: 

Not much time to elaborate or test this right now, but I'll try to do more when I get a chance.

Use centroids as your primary method. Test to see if the centroid is within the polygon; if not, draw a line through the nearest point and on to the other side of the polygon. At the midpoint of the section of that line that is within the polygon, place your label.

Because the point that is nearest to the centroid is likely to bound a fairly large area, I think this might give results similar to Kyralessa's incircles. Of course, this might go berserk if you had a polygon with holes. In that case, the incircles would probably fair much better. On the other hand, it defaults to the (quick?) centroid method for the typical cases.

Matt Parker
Pathological test case #3: a symmetrical barbell-like shape with a thin rectangle and two big octagons on the ends. Centroid is within the polygon but the rectangle is a bad place to label since it may not fit.
Jason S
A: 

I am not saying that this is the fastest, but it will give you a point inside the polygon. Calculate the Straight Skeleton. The point you are looking for is on this skeleton. You could pick the one with the shortest normal distance to the center of the bounding box for example.

Harald Scheirich
A: 

You can write the equations for the center of mass of a flat plate in terms of area integrals:

http://ltcconline.net/greenl/courses/202/multipleIntegration/MassMoments.htm

You can use Green's theorem to convert those to contour integrals and use Gauss quadrature to evaluate them around the perimeter of your polygon. This is correct for arbitrarily complex polygons, and even works correctly for shapes with internal holes.

duffymo