Answered by:
How to find center point of a polygon
Question

I have a polygon (one in three types : convex,nonconvex,with holes) that inculdes a list of vertexs(point x,y) and edges (start point ,end point).
Now i have to find one point to put a label within polygon and is center of largest part
. Are there anyone have solution? Thanks so much.
 Edited by Cuongdx Saturday, November 17, 2012 8:48 AM
Saturday, November 17, 2012 8:31 AM
Answers

Centroid of Vector2D list of points.
public static Vector2 Centroid(this List<Vector2> path) { Vector2 result = path.Aggregate(Vector2.Zero, (current, point) => current + point); result /= path.Count; return result; }
 Proposed as answer by Paul Ishak Friday, November 23, 2012 5:59 PM
 Marked as answer by Lisa Zhu Tuesday, December 4, 2012 6:10 AM
Friday, November 23, 2012 1:54 PM 
1) Now we need to know whether by "hole" he means "cavity as in concave", or "hole as in torus". I believe it is the former, others here believe it is the latter.
2) Agreed. And responders need to assist each other as well as just OP's.
3) After writing my question I refreshed my memory on the relevant geometry, and was reminded that the inscribed circle only exists for these cases: triangles, regular polygons and occasional special cases. Unfortunately the current problem is more general than these, so the inscribed circle will not exist. That leaves the circumscribed circle (what I referred to as the exscribed circle above, and which always exists) and the barycenter or centerofgravity (which also always exists) as common mathematical 'centers'.
4) My approach at this point, having pointed out some of the relevant mathematics and geometry, is to wait for the OP to do his math homework. This is a C# forum, not a Mathematics & Geometry forum. I will assist with coding and other C# issues when that homework is done. I will also assist in identifying "wellknown" math algorithms for welldefined problems, but "general research" in this area does not appeal to me. Other responders will make their own judgement on an appropriate degree of support for the OP in his math homework, which is fine by me.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Thursday, November 22, 2012 8:37 PM 
I still like triangles because every every shape that is formed you can easily calculate and the results will always be precise. I learned to calculate by hand every shape in High School geometry. Your method requires calculus and requires a lot of math. There will still be tiny pieces that will get missed.
With the holes circles you edges of you polygon aren't always going to be straight lines. Some edges become an arc which has an angle and a radius. You start by finding where the circles intersect an edge of the circles. Pieces of the circle outside the poloygon are ignored. The edge that intersects the circle will contain two points of a triangle. The third point of the triangle will be a tangent to the circle from the point on the edge that doesn't intersect the circle.
In 1970 to 1974 I participated in High School Matheletes and was solving these type problem without computers or calculators in competion. And we were given only 3 to 5 minutes to get the answer.
jdweng
Friday, November 23, 2012 8:45 AM
All replies

Your image is not displaying.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Saturday, November 17, 2012 8:34 AM 
No image is showing
"Premature optimization is the root of all evil."  Knuth
Saturday, November 17, 2012 8:35 AM 
well, your image has not shown, but here's a Picasso for you that will help you understand how to center a control into your polygon.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Saturday, November 17, 2012 8:47 AM 
Paul,
What if the polygo is extremely concave, such as a capital 'C', and what if some edges coss over each other?
Cuongdx: There are many possible interpretations of "center" for a polygon. Can you specify which one you intend?
"Premature optimization is the root of all evil."  Knuth If I provoked thought, please click the green arrow If I provoked Aha! please click Propose as Answer
Saturday, November 17, 2012 8:57 AM 
Well, if you are creating your polygon based on an array of points, then it doesn't really matter, does it? You are going to have to iterate through all of your points, searching for the lowest X and Y values, and the highest X and Y values. The algorithm wouldn't connect the dots for you, if you have something special in mind, then you have to modify the algorithm accordingly.
The idea is that you align the center point of the control to the center point of your polygon, and since polygons are capable of being imperfect, you should take this as a general insight and depending on how imperfect the polygon is, be prepared to alter the formula for your exact needs.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Saturday, November 17, 2012 9:10 AM 
Cuongdx:
Various possible meaning of "center" in your case, which you have already stated will be for the largest single nonintersecting component if the input is selfintersecting, are:
 Barycenter, centroid, or "centerofmass" http://en.wikipedia.org/wiki/Centroid
 Chebyshev center, or center of largest inscribed circle http://en.wikipedia.org/wiki/Chebyshev_center
 center of largest exscribed circle (no reference readily found)
"Premature optimization is the root of all evil."  Knuth If I provoked thought, please click the green arrow If I provoked Aha! please click Propose as Answer
Saturday, November 17, 2012 9:27 AM 
I don't think people are really ansering the question you asked. Waht do you think? they are only answering a part of the question. You are looking for "center of largest part ".
So the first thing you need to do is define what a "part" realy is? The solution is to divide the polygon into triangles and calcuate the area of each triange. Since you have a polygon we will assume all edges are straight lines. The algorith will be as follows
1) Start at any one vertices
2) Get the next two vertices so you have three points which is a triangle.
3) Next verify if any of the other vertices in the polygon is inside the triangle.
4) If you find another point inside the triable skip these three points and get another three points.
5) If there is no vertices inside the triangle remove the triangle from the polygon by eliminating the middle vertices from the polygon. Store the removed triangle into a List<> object
6) Repeat process until the entire polygon is divided into triangles. Realize the removing a triangle may divide the polygon into two polygons. I think you one want to remove triangles that are three consecutive points in the polygon. YOu also want to remove any triangles with acute angles (less than 90 degrees). If you have a triangle greater than 90 degrees it indicates that the triangle is describing an area outside the polygon.
7) Now you can process the list of triangles. You can calculate the area of each triangle and the center of mass.
8) You can find the center of the polygon by finding the weighted average of all the triangles. the weight of each triangle is the area of each triangle when you are working with a flat object.
jdweng
 Edited by Joel Engineer Saturday, November 17, 2012 12:33 PM
Saturday, November 17, 2012 12:31 PM 
Here's a question. Suppose the polygon is a square and it has a square hole in the centre. Then there is no largest part and the centre of mass will be in the centre of the hole. Do you have to cope with that?
Disclaimer: Never had to do this so don't know how. I only know that the idea of the centre of a polygon is not cut and dried. Pieter points to some of them.
Regards David R

The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Objectoriented programming offers a sustainable way to write spaghetti code.  Paul Graham.
Every program eventually becomes rococo, and then rubble.  Alan Perlis
The only valid measurement of code quality: WTFs/minute.Saturday, November 17, 2012 12:46 PM 
Here's a question. Suppose the polygon is a square and it has a square hole in the centre. Then there is no largest part and the centre of mass will be in the centre of the hole. Do you have to cope with that?
Disclaimer: Never had to do this so don't know how. I only know that the idea of the centre of a polygon is not cut and dried. Pieter points to some of them.
Regards David R

The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Objectoriented programming offers a sustainable way to write spaghetti code.  Paul Graham.
Every program eventually becomes rococo, and then rubble.  Alan Perlis
The only valid measurement of code quality: WTFs/minute.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions. Edited by Paul Ishak Saturday, November 17, 2012 12:53 PM
Saturday, November 17, 2012 12:49 PM 
It seems to me, rather than worrying about computation of the center, you need to worry about the point being equidistant from any poitn visible in the view. I work with GIS apps, and the labeling of a state or country is somewhat dependent on not only the polygon being visible, but also how much of it is visible. For example, if only Northern Indiana is visible in a map of the Great Lakes, it still deserves a label, even if Indianapolis is not on the map.

MikeSaturday, November 17, 2012 12:51 PM 
We have to assume that polygons don't have rounded edges. The hole is just a cutout that is described by vertices. I assuming the largest part means the whole object or any of the cutouts. Unless the input to the problem is a list of polygons and a list of cutouts for each polygon.
jdweng
Saturday, November 17, 2012 12:55 PM 
Not all donuts have holes; only ring ones, filled ones don't. Sainsbury's banana custard ones certainly did not have holes. :)
I just wondered how the OP wanted to handle a simple case: a square with a square hole at its centre. I.e. a shape with no largest part where the centre lies not in the polygon but in the hole that it surrounds (for some definitions of centre). :)
Regards David R

The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Objectoriented programming offers a sustainable way to write spaghetti code.  Paul Graham.
Every program eventually becomes rococo, and then rubble.  Alan Perlis
The only valid measurement of code quality: WTFs/minute.Saturday, November 17, 2012 1:01 PM 
Paul,
I do not mean to be rude, but your failure to research the geometry is clouding the issue. There are a number of commonly used "centers" for polygons, and you are fixated on one that is less commonly useful than at least three others:
 Barycenter  intersection of medians, or center of gravity (I believe these two are always the same for convex polygons, but less sure for concave ones)
 exocenter  center of largest inscribed circle
 endocenter  center of largest inscribed circle
Occasionally, for triangles at least, the intersection of the heights to all three sides is also useful.
You are fixating on the "rectangular" center, which is dependent on the coordinate axes, and thus is not really an inherent property of the figure at all, but of it's portrayal in a particular coordinate system. This is only useful in drawing applications.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Saturday, November 17, 2012 1:40 PM 
My inference from the original description is that the polygon in each case is described by a single path; that is to say, it can be drawn without the pen ever leaving the paper. Given that assumption, there are then three basic cases to consider:
 Convex polygon  the easy one;
 Concave polygon  harder;
 Intersecting path  the hardest;
However, given the original assumption, the various pieces in case 3 will always 'touch' corner to corner in a chain. As I understand the original specification, in case 3 the "center" of the largest nonintersecting fragment is desired. Wellknown algorithms exist for finding the area of polygons from their path outlines, and for finding the various centers from the path outlines. The trick in 3 is to identify the intersection points of the path segments, as each of these points must be added to two fragments, as additional vertices, as thy are identified. Then the fragments must be identified, theri area determined to identif the largest one, at which time the algorithm of case 2 (it being a generalization of case 1) can be used to determine the required point.
Cuongdx: Can you confirm that I have summarized the problem correctly, and made the correct assumptions?
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
 Edited by Pieter Geerkens Saturday, November 17, 2012 1:55 PM
Saturday, November 17, 2012 1:54 PM 
Pieter
Not sure your inference is correct. The OP does say it can have holes. I don't know what difference that makes, if any.
Nevertheless good stuff  especially about there being more than one way to define centre.
Regards David R

The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Objectoriented programming offers a sustainable way to write spaghetti code.  Paul Graham.
Every program eventually becomes rococo, and then rubble.  Alan Perlis
The only valid measurement of code quality: WTFs/minute.Saturday, November 17, 2012 2:09 PM 
I inferred that he meant "cavities", as in concave, rather than "holes" as in doughnuts. We will have to wait for confirmation from Cuongdx to be sure.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Saturday, November 17, 2012 2:39 PM 
I stll concerned with th ebasic calculations and arriving at the mehtod of doing the caluclation. I made an error with my statement ignoring obtuse triangles (should of been angles greater than 180. So here is an update of my method. It requires dividing the polygon into triangles.
1) The points of the graph are entered going around the Polygon in a counter clockjwise direction
2) Angles of the polygon are caculated from the 2nd point to the first point so the measurement are made in a a counterclockwise direction.
angle = arc tan[(y2  y1)/(x2  x1)]
3) The sum of the angles of the graph (include last point to 1st point) is 180 * (n  2) where n is the number of sides of the graph (number of points). If you don't get the correct answer your points entered in the wrong direction. Reverse the order of the points.
4) Start at any one vertices
5) Get the previous vertices and caculte angle to current vertice. Calculate the angle from the current vertice to the next vertice. add the two angles together to get the angle of the corner. Ingnore vertices where the ange is greater than 180 degrees. The three angles describe a triangle.
6) Next verify if any of the other vertices in the polygon is inside the triangle from step 5. If a vertices is inside the triangle ignore this triangle and go onto next triangle. Use these steps to caculate if a vertice is inside the triangle.
a) Calculate the ange from the current vertice to every other vertice except the previous and
next vertice. If the angle is outside the two angles caculated in step 5 (previous and
next vertices) the vertices is outside the triangle. Skip step b
b) Draw a line from the current vertice to the 2nd vertice. Find were the line intersects
opposite side of triangle. Determine if the 2nd vertice is inside or outside the triangle.
7) If there is no vertices inside the triangle remove the triangle from the polygon by eliminating the middle vertices from the polygon. Store the removed triangle into a List<> object
6) Repeat process until the entire polygon is divided into triangles. Realize that removing a triangle may divide the polygon into two polygons..
7) Now you can process the list of triangles. You can calculate the area of each triangle and the center of mass.
8) You can find the center of the polygon by finding the weighted average of all the triangles. the weight of each triangle is the area of each triangle when you are working with a flat object.
The center of mass is the following
(X1 * area 1) + (X2 * area 2) + (X3 * area 3) + ... divided by number of sides
(Y1 * area 1) + (Y2 * area 2) + (Y3 * area 3) + ... divided by number of sides
jdweng
Saturday, November 17, 2012 6:28 PM 
Joel,
In my engineering program they emphasized NOT reinventing any wheels. You are reinventing a few.
 For inclusion of a point in a triangle, just use the GraphicsPath.IsVisible(Point point) method.
 Calculation of polygon area from vertex coordinates is best done with the wellknown formula described here: http://www.mathopenref.com/coordpolygonarea.html.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Saturday, November 17, 2012 7:19 PM 
Hi, thanks for help me, i can't attach image.But like Family Tree Mike said, i want to set label for a land like a polygon. I thinks center of polygon
Monday, November 19, 2012 7:43 AM 
So, did you get the answer? If yes, please mark it/them as answer(s).
:)
Cheers, Amy
Tuesday, November 20, 2012 9:14 AM 
'i haven't found any expected answer yet.Wednesday, November 21, 2012 1:57 AM

To get the center of the pologon I still feel the solution is to divide the polygon into triangles. find the area of each triagle and the center of each triangle. The center becomes the following no matter what the shape of the polygon or the number of holes.
Average X = (Area trangle1 * triangle 1 center X) + (Area trangle1 * triangle 2 center X) + (...) /number triangels
Average Y = (Area trangle1 * triangle 1 center Y) + (Area trangle2 * triangle 2 center y) + (...) /number triangels
I'm not should how to tell which triangles are in the holes because you don't want to include any triangles in the holes. You original statement that you have a "list of vertices and edges". So do you also have a list of vertices and edges for each of the holes? Do I would asume the first step is to remove the holes from the polygon. As yo remove the holes you will get a new list of edges and vertices. The polygon then may end up being multiple pices. After the holes are removed then you would divide the polygon(s) into triangles. The center will still be the point (Average X, Average Y) of the pice with the largest area.
jdweng
Wednesday, November 21, 2012 6:07 AM 
Paul,
I do not mean to be rude, but your failure to research the geometry...
Pieter, I don't know if you noticed or not, but I did stop responding to this thread because your comment implies that you feel that you are more capable of answering the OP's question. Have you now left this topic for dead? I don't think you should discourage someone else from helping someone else if you can't help them yourself. Just a thought, OP is still standing by.
My point is that you may or may not be correct that my response to this thread is clouding the issue. But think again, is it really? Does it not help clarify "That is an example of what I do not want". Does it not help narrow the problem? Some would think it does, and that makes it relevant.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.
 Edited by Paul Ishak Thursday, November 22, 2012 7:47 PM
Thursday, November 22, 2012 7:36 PM 
No, I haven't left this thread for dead.
However, the OP has not answered the questions asked above about how to correctly refine his requirements, which makes it difficult to get past all the hypotheticals. Chasing down hypotheticals I believe to be an inappropriate activity for a Q&A forum.
I apologize for any offense caused. My intent was to motivate you to research the geometry, not to leave the thread. There are many "centers" for polygons defined by the mathematicians and physicists, and the one that you kept proposing is one that I never saw before. Your answers were detailed, more detailed than I am usually motivated to provide, which is good; but in this case I believed them to be misguided and confusing. However only the OP can answer that for certain, and his recent contributions have not been helpful in that regard.
My participation in these forums is only 5 days old, whereas you have clearly been around much longer than that. If, as I anticipate, my participation in these forums continues to grow we will meet up again. I hope and trust we can put this misunderstanding behind us.
Pieter
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
 Edited by Pieter Geerkens Thursday, November 22, 2012 8:14 PM
Thursday, November 22, 2012 8:13 PM 
Hi, thanks for help me, i can't attach image.But like Family Tree Mike said, i want to set label for a land like a polygon. I thinks center of polygon
Pieter, I believe that this is the OP's clarification on what they need.
Just also bear in mind that sometimes in these forums the path to the answer is not always a strait line, and not always does someone have the exact answer right off the bat, but sometimes this process leads to the right answer. But if we were to refrain to responding to some topics without that process, a great deal of questions in these forums would go unanswered, and a great deal of people would remain unhelped.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Thursday, November 22, 2012 8:23 PM 
1) Now we need to know whether by "hole" he means "cavity as in concave", or "hole as in torus". I believe it is the former, others here believe it is the latter.
2) Agreed. And responders need to assist each other as well as just OP's.
3) After writing my question I refreshed my memory on the relevant geometry, and was reminded that the inscribed circle only exists for these cases: triangles, regular polygons and occasional special cases. Unfortunately the current problem is more general than these, so the inscribed circle will not exist. That leaves the circumscribed circle (what I referred to as the exscribed circle above, and which always exists) and the barycenter or centerofgravity (which also always exists) as common mathematical 'centers'.
4) My approach at this point, having pointed out some of the relevant mathematics and geometry, is to wait for the OP to do his math homework. This is a C# forum, not a Mathematics & Geometry forum. I will assist with coding and other C# issues when that homework is done. I will also assist in identifying "wellknown" math algorithms for welldefined problems, but "general research" in this area does not appeal to me. Other responders will make their own judgement on an appropriate degree of support for the OP in his math homework, which is fine by me.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Thursday, November 22, 2012 8:37 PM 
Hi Joel,Thank you so much. your idea's very intersting, I will try it later. Now I am trying to look for inscribed circle. I will post it soon if I am successful
I thinks we always find a inscribed circle exposure at least 2 edges of polygon.
basically my algorithm is:
1 find Xmax and Xmin, Ymax ,Ymin of vertex ò polygon
2. start from point (Xmin Ymin) to (xmax ymin) and draw a circle with radius R=(xmaxxmin)/2
Examine whether the circle cut the sides of polygon or not If yes, reduce radius till cut point disappears, save the circle
3 Keep running, with vertically and horizontally and choose the circle with the largest radius. Choose max point x and min point x
Friday, November 23, 2012 2:26 AM 
Quick point of terminology: That sounds like the circumcircle, not the inscribed circle.
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Friday, November 23, 2012 3:25 AM 
I still like triangles because every every shape that is formed you can easily calculate and the results will always be precise. I learned to calculate by hand every shape in High School geometry. Your method requires calculus and requires a lot of math. There will still be tiny pieces that will get missed.
With the holes circles you edges of you polygon aren't always going to be straight lines. Some edges become an arc which has an angle and a radius. You start by finding where the circles intersect an edge of the circles. Pieces of the circle outside the poloygon are ignored. The edge that intersects the circle will contain two points of a triangle. The third point of the triangle will be a tangent to the circle from the point on the edge that doesn't intersect the circle.
In 1970 to 1974 I participated in High School Matheletes and was solving these type problem without computers or calculators in competion. And we were given only 3 to 5 minutes to get the answer.
jdweng
Friday, November 23, 2012 8:45 AM 
It not the inscribed circle but it is a circle within polygon with largest radius.
so the center of the circle is the point I was looking for
Friday, November 23, 2012 8:54 AM 
It is still the same. You take a vertice of the polygon and draw two tangents to the circle to get 3 points of a triangle. Then remove the triangle.
jdweng
Friday, November 23, 2012 9:01 AM 
Centroid of Vector2D list of points.
public static Vector2 Centroid(this List<Vector2> path) { Vector2 result = path.Aggregate(Vector2.Zero, (current, point) => current + point); result /= path.Count; return result; }
 Proposed as answer by Paul Ishak Friday, November 23, 2012 5:59 PM
 Marked as answer by Lisa Zhu Tuesday, December 4, 2012 6:10 AM
Friday, November 23, 2012 1:54 PM 
I did this problem before 40 years ago in 5 minutes, it just took me a week to how to do the problem again. The math is very simple if you know how to balance a rod. suppose you had to 8 meter rod with two weights 3Kg and 5Kg. You know the folowing
M1 = 3Kg
M2 = 5Kg
M(t) = M1 + M2 = 8Kg
M1 * L1 = M2 * L2
L1 = 5M
L2 = 3M
The math to solve the problem os a hole in a polygon is exactly the same.
1) First calculate the area of the polygon including the hole which is MT and the center of mass of the polygon. The center of mass is the balance point of the rod.
2) Calculate the mass of the hole which is M1
3) Draw a straight line from the cneter of the hole to the center of the polygon. The distance of between the two center of mass is L1.
4) The mass of the polygon when the hole is removed is M2 = M(t)  M1. The new center of mass after the hole is removed is at position L2. The center of mass after the hole is removed is along an extended straight line that is drawn from the center of mass of the hole to the center of mass of the polygon.
When you have more than one hole you remove one hole at a time get a center of mass. Then remove the next hole using the same math.
jdweng
Saturday, November 24, 2012 9:35 AM 
I recently bought this book, and it has some interesting information pertaining to polygon math. It was worth the 37 I spent. I haven't got to a part that pertains to your question though yet(sry). ++
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Saturday, November 24, 2012 10:07 AM 
Thanks Paul, I will look for that book. (My original degree is in physics.)
"Premature optimization is the root of all evil."  Knuth
If I provoked thought, please click the green arrow
If I provoked Aha! please click Propose as Answer
Saturday, November 24, 2012 6:16 PM 
Thanks Paul, I will look for that book. (My original degree is in physics.)
I'm enjoying this book, so far it's refreshing me on some stuff I already know, but it looks like a couple hundred pages in it gets real fun(and I'll learn some new stuff). You're welcome to email me if you want to ask about it.
Anyways I just wanted to share because I thought the OP(or anyone else looking at this thread) might find it helpful.
If you want something you've never had, you need to do something you've never done.
Everyone(not just the thread starter) should take the time to mark helpful posts, propose answers, and mark answers to questions.Saturday, November 24, 2012 7:07 PM