11

example problem polygon

what algorithm that i can use to get the center of polygon (red point)
case 1 : i try with maxX, maxY, minX, minY and i got the wrong point (black point)
case 2 : i try to get the second max and min coordinate X and Y, but i got problem with the polygon which have point less than 5
case 3 : i add if point count < 5 then use case 1 else use case 2 but i got some error for some polygon

can you tell me the right algorithm for me??

note : pic 4th

explaination for 4th picture

//ma mean max, mi mean min, X1 mean first, X2 mean second
maX1 = maX2 = maY1 = maY2 = 0;
miX1 = miX2 = miY1 = miY2 = 2000;
//aCoor is array of coordinate, format = {x1,y1,x2,y2,x3,y3,x4,y4,...}
for(int i=0; i<aCoor.count(); i+=2)
{
     //point is list of point
     point.Add(aCoor[i],aCoor[i + 1]);
     //this to get second max X
     if(maX2 < aCoor[i])
     {
         maX2 = aCoor[i];
     //this to get first max x
     if(maX1 < maX2) {maX1 += maX2; maX2 = maX1 - maX2; maX1 -= maX2;}
     }

     //this to get second min X
     if(miX2 > aCoor[i])
     {
         miX2 = aCoor[i];
     //this to get first min x
     if(miX1 > miX2) {miX1 += miX2; miX2 = miX1 - miX2; miX1 -= miX2;}
     }

     //this to get second max Y
     if(maY2 < aCoor[i + 1])
     {
         maY2 = aCoor[i + 1];
     //this to get first max x
     if(maY1 < maY2) {maY1 += maY2; maY2 = maY1 - maY2; maY1 -= maY2;}
     }

     //this to get second min Y
     if(miY2 > aCoor[i + 1])
     {
         miY2 = aCoor[i + 1];
     //this to get first min x
     if(miY1 > miY2) {miY1 += miY2; miY2 = miY1 - miY2; miY1 -= miY2;}
     }
}

if(point.Count < 5)
{
    Xcenter = (maX1 + miX1) / 2;
    Ycenter = (maY1 + miY1) / 2;
}
else
{
    Xcenter = (maX2 + miX2) / 2;
    Ycenter = (maY2 + miY2) / 2;
}

this how far i do

Zenithxm
  • 135
  • 3
  • 13

1 Answers1

3

What you are looking for is not the geometric center (or centroid) of the polygon, but the center of the portion of the polygon's axis of symmetry which lies inside the polygon. Let me edit one of your examples to demonstrate:

Edited example

Do you see what I mean?

I picked this example because it demonstrates another flaw in your thinking; this is two polygons, and each of them produce a point that fits the qualifications you're looking for. In your example you just arbitrarily chose one of them as the point you want. (I have seen your edited fourth example; it still has two interiors and does not change my point.)

In any case, what you're looking for is actually the solution to two problems: first, how to find an axis of symmetry for a polygon; second, finding a line segment on that axis of symmetry which also lies in the interior of the polygon. After that, finding the center of that segment is trivial.

I can't post any more links, but there's a paper by P. Highnam out of Carnegie Mellon University entitled Optimal Algorithms for Finding the Symmetries of a Planar Point Set which could help with the first problem, it's a bit involved so I won't explain it here. The second problem just boils down to testing each line segment to see if it contains a point of intersection with a line along the axis of symmetry running through the figure's centroid. Assuming your polygon only has one interior (read: is not like your fourth example), you should get two points. Average them and you have your center.

tonewheel
  • 39
  • 2