Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!julius.cs.uiuc.edu!psuvax1!osteocyber!dsc
From: dsc@osteocyber.ortho.hmc.psu.edu (david s. channin)
Newsgroups: comp.graphics
Subject: Re:  (want to find a centroid)
Message-ID: <F?hk62t2@cs.psu.edu>
Date: 17 Oct 90 15:27:32 GMT
References: <1990Oct15.022751.10968@hades.ausonics.oz.au> <LAMBERT.90Oct16110003@nankeen.spectrum.cs.unsw.oz.au>
Sender: news@cs.psu.edu (Usenet)
Reply-To: dsc@osteocyber.osteocyber.ortho.hmc.psu.edu (david s. channin)
Organization: Hershey Med Ctr, Penn State Univ., Hershey PA
Lines: 73
Nntp-Posting-Host: osteocyber.ortho.hmc.psu.edu

> I have a 2D problem in which I need to find the centroid of an
> enclosed space (an image of an object). One way I've thought of is
> via flooding (like flood- fill); I have a rather dumb, slow
> algorithm I worked out, and I'm wondering if there's a faster one.

>>The centroid only depends on the boundary of the object, so unless you
>>shapes are only a few pixels in size, it would be faster to follow the
>>boundary of the object and use the formula that calculates the
>>centroid of a polygon from its vertices.

This is from about six years ago. I've used this subroutine quite a bit. Fortunately my friend mark read obscure journals at the time. 

/************************************************************************
*  cmass finds the center of area from a set of X,Y data points that    *
*        MUST BE arranged in counter clockwise order.                   *
*       n   The number of data points                                   *
*       x   The array of x coordinates                                  *
*       y   The array if y coordinates                                  *
*   xcenter The x coordinate of the center [OUT]                        *
*   ycenter The y coordinate of the center [OUT]                        *
*                                                                       *
*                                                                       *
*  Based on equations derived in:                                       *
*     R. Ehrlich and B. Weinberg                                        *
*     "An Exact Method for Characterization of Grain Shape"             *
*     Journal of Sedimentary Petrology                                  *
*     Vol. 40., PP 205-212, 1970                                        *
*                                                                       *
*  Thanks to Mark Saltzman for the fortran source.                      *
************************************************************************/
int cmass(n,x,y,xcenter,ycenter)

  int            n;
  int          x[];
  int          y[];
  double  *xcenter;
  double  *ycenter;

  {
    double        mx,
                  my,
                   a,
                 xr1,
                 yr1,
                 xr2,
                 yr2;
    int            i;

    mx = 0.0;
    my = 0.0;
    a  = 0.0;

    for (i = 0; i LT (n - 1); i++)
      {
        xr1 = (double)x[i];
        xr2 = (double)x[i+1];
        yr1 = (double)y[i];
        yr2 = (double)y[i+1];

        a = a + 0.5 * (yr2 + yr1) * (xr1 - xr2);
        my = my + (yr2 * yr2 + yr2 * yr1 + yr1 * yr1) * (xr1 - xr2) / 6.0;
        mx = mx - (xr2 * xr2 + xr2 * xr1 + xr1 * xr1) * (yr1 - yr2) / 6.0;
      }

    if (a EQ 0.0)
      a = 9.0;

    *xcenter = mx / a;
    *ycenter = my / a;

    return(TRUE);

 }