Center(ish) point of a polygon.
-
Hey does anyone know of an algorithm to find the point that resides inside a polygon that is farthest (on average) to any other point in the polygon? The polygons don't have to be regular and not all points can see the other points (IE you may not be able to draw a line between every point without intersecting the outer edge of the polygon)
-
Hey does anyone know of an algorithm to find the point that resides inside a polygon that is farthest (on average) to any other point in the polygon? The polygons don't have to be regular and not all points can see the other points (IE you may not be able to draw a line between every point without intersecting the outer edge of the polygon)
-
Look up how to calculate the centroid of an arbitrary area. This comes out of the more general study of moments of area.
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
My understanding of centroid means that if your polygon was in the shape of the letter C the centroid would be somewhere outside the polygon (in the middle of the c that is). I could be wrong though.
-
Hey does anyone know of an algorithm to find the point that resides inside a polygon that is farthest (on average) to any other point in the polygon? The polygons don't have to be regular and not all points can see the other points (IE you may not be able to draw a line between every point without intersecting the outer edge of the polygon)
This is a very interesting question. I don't know if there is a known algorithm for that (but I guess there must be). Just a thought: maybe you can start working on a basic idea like drawing a line from each vertex to the middle point of each side (excluding the two sides on which the vertex stands). Then examine the intersection points of these lines (excluding those that lie outside the polygon) and find the one which is farthest on average from all vertexes. Not sure if this is the right way to go, but I hope I gave you some idea to work on. :) Let me know if you find the solution, I'll be very interested.
2+2=5 for very large amounts of 2 (always loved that one hehe!)
-
My understanding of centroid means that if your polygon was in the shape of the letter C the centroid would be somewhere outside the polygon (in the middle of the c that is). I could be wrong though.
Yes, certainly with concave polygons the centroid may but doesn't necessarily lie outside. If I'm understanding your problem this time, you need to formulate it by taking the double integral over the area of the polygon of the distance to each point and an arbitrary point (x,y). Personally, I'd use distance squared and get rid of the pesky square root. Then once you've established the equation of the distance squared over the area, you take the partial derivatives with respect to x and y and find the maximum. The rub probably comes when you have to restrict (x, y) to lie "inside" the polygon. Off the top of my head, that part isn't clear. I'm on the road and tired so that part is left up to the student. :laugh:
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
-
Yes, certainly with concave polygons the centroid may but doesn't necessarily lie outside. If I'm understanding your problem this time, you need to formulate it by taking the double integral over the area of the polygon of the distance to each point and an arbitrary point (x,y). Personally, I'd use distance squared and get rid of the pesky square root. Then once you've established the equation of the distance squared over the area, you take the partial derivatives with respect to x and y and find the maximum. The rub probably comes when you have to restrict (x, y) to lie "inside" the polygon. Off the top of my head, that part isn't clear. I'm on the road and tired so that part is left up to the student. :laugh:
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
Thanks Tim, this has put me on the right track. I am developing an algorithm that will do just this, I hadn't even considered that it was a maximization problem until now. I'll get back to you with my results.
-
Thanks Tim, this has put me on the right track. I am developing an algorithm that will do just this, I hadn't even considered that it was a maximization problem until now. I'll get back to you with my results.
I'd like to hear, especially the constrait to the body of the polygon part. It's easy to say but, I think, mathematically it might me more difficult to express. At least generally. I made it to the airport and, hopefully, tonight I'll be home.
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
-
Hey does anyone know of an algorithm to find the point that resides inside a polygon that is farthest (on average) to any other point in the polygon? The polygons don't have to be regular and not all points can see the other points (IE you may not be able to draw a line between every point without intersecting the outer edge of the polygon)
To calculate the centroid of a polygon: Source: http://en.wikipedia.org/wiki/Centroid[^] and http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]
PointF centroid(PointF[] p) {
// p is an array with the vertices of the polygon
float cx = 0;
float cy = 0;
float a = 0;
float ca;
for (int i = 0; i < p.Length; i++) {
ca = x[i] * y[(i + 1) % p.Length] - x[(i + 1) % p.Length] * y[i];
cx = cx + (x[i] + x[(i + 1) % p.Length]) * ca;
cy = cy + (y[i] + y[(i + 1) % p.Length]) * ca;
a = a + ca / 2;
}
cx = cx / (6 * a);
cy = cy / (6 * a);
return new PointF(cx , cy);
}By the way, I am not sure if what you need is a centroid. Hope this helps, anyway.