Bus error - Help!

Hi,

I've been asked to see if I can fix a C program so that it will run on a mac. It currently compiles and runs perfectly on a linux machine, but as soon as you run it on a mac, it will compile, but quit with a bus error very early on. The full code is here:

// Program for the construction of cartograms (density-equalizing map
// projections) using the Gastner-Newman technique. The program needs polygon
// coordinates and a count of cases in each region as input, calculates the new
// coordinates, and writes these to a file. Postscript images of the original
// map and the cartogram are created.

// WRITTEN BY MICHAEL GASTNER, September 20, 2004.

// If you use output created by this program please acknowledge the use of this
// code and its first publication in:
// "Generating population density-equalizing maps", Michael T. Gastner and
// M. E. J. Newman, Proceedings of the National Academy of Sciences of the
// United States of America, vol. 101, pp. 7499-7504, 2004.

// The input coordinates in MAPGENFILE must be in ArcInfo "generate" format of
// the type:

// 1
// 0.3248690E+06 0.8558454E+06
// 0.3248376E+06 0.8557575E+06
// 0.3248171E+06 0.8556783E+06
// 0.3247582E+06 0.8556348E+06
// 0.3246944E+06 0.8555792E+06
// 0.3246167E+06 0.8555253E+06
// ...
// 0.3250221E+06 0.8557324E+06
// 0.3249436E+06 0.8557322E+06
// 0.3248690E+06 0.8558454E+06
// END
// 1
// 0.3248690E+06 0.8558454E+06
// 0.3249651E+06 0.8558901E+06
// 0.3250519E+06 0.8559769E+06
// 0.3250691E+06 0.8561246E+06
// 0.3249678E+06 0.8560541E+06
// 0.3249003E+06 0.8560088E+06
// ...
// 0.3076424E+06 0.8477603E+06
// 0.3075691E+06 0.8477461E+06
// 0.3075595E+06 0.8476719E+06
// END
// 2
// 0.6233591E+06 0.6056502E+06
// 0.6235193E+06 0.6056467E+06
// 0.6235054E+06 0.6055372E+06
// ...
// ...
// ...
// 0.7384296E+06 0.2334260E+06
// 0.7383532E+06 0.2345770E+06
// END
// END

// The number of cases in CENSUSFILE must be given in the form
// region #cases (optional comment), e. g:

// 43 0.9 Alabama
// 51 0.3 Alaska
// 37 0.8 Arizona
// 47 0.6 Arkansas
// 25 5.4 California
// 32 0.8 Colorado
// 19 0.8 Connecticut
// 29 0.3 Delaware
// 28 0.3 District of Columbia
// 49 2.5 Florida
// 45 1.3 Georgia
// 1 0.4 Hawaii
// ...

// The output coordinates are written to CARTGENFILE in ArcInfo "generate"
// format. A postscript image of the original input is prepared as MAP2PS,
// an image of the cartogram as CART2PS.

// Modified on Oct 29, 2004. The number of divisions in each dimension lx, ly
// will now be determined from the input map. Also fixed array bound
// violations in intpol and newt2, and centered the ps-files.

// Modified on Dec 3, 2004. Introduced pointers bbmaxx,bbmaxy,bbminx,bbminy -
// the bounding box coordinates for each polygon - to reduce calculations in
// crnmbr. Thanks to Chris Brunsdon for the suggestion.
// Program now terminates with error message if there is no density specified
// in CENSUSFILE for a region on the map.
// "Donut" polygons are now handled properly. Polygons oriented clockwise will
// be considered exterior boundaries. If they are oriented anti-clockwise they
// are holes inside an enclosing polygon. (Unconventional for mathematicians,
// but this is ArcGIS standard.) The identifier is either that of the enclosing
// polygon, or -99999 in which case it is a hole in the preceding polygon.
// The population can now be a floating-point number.
// If a region contains exactly zero population, it will be replaced by
// MINPOPFAC times the smallest positive population in any region.
// Obviously, MINPOPFAC should be <1, I will set it to 0.1 by default. This
// should reduce the value of sigma necessary for the integrator to finish
// properly.

// Modified on March 31, 2005. Initialized maxchange in nonlinvoltra() as
// INFTY. Replaced crnmbr() by a similar, but faster routine interior().
// Many thanks to Stuart Anderson for pointing out this shortcut.

// TO DO LIST:
// - Do Gaussian blur within nonlinvoltra as a simple call to calcv and
// eliminate gaussianblur().
// - Modify the NR code for the FFTs to deal more naturally with the fencepost
// issue. No more copying of arrays in sinft and cosft.
// - Write truly two-dimensional versions of coscosft, cossinft, and sincosft.
// See Chan and Ho: A new two-dimensional fast cosine transform algorithm,
// IEEE Transactions on Signal Processing, 39, 481ff. (1991).
// - Read polygon data directly from shapefile instead of generate file.
// - Reorganize data structures. It is currently quite a mess to read.

// Inclusions

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

// Definitions

#define CART2PS "./cart.ps","w" // Cartogram image.
#define CARTGENFILE "./cartogram.gen" // Cartogram generate file.
#define CENSUSFILE "./census.dat","r" // Input.
#define CONVERGENCE 1e-100 // Convergence criterion for integrator.
// #define DISPLFILE "./displ.dat","w"
#define FALSE 0
#define HINITIAL 1e-4 // Initial time step size in nonlinvoltra.
#define IMAX 50 // Maximum number of iterations in Newton-Raphson routine.
#define INFTY 1e100
#define LINELENGTH 1000
#define MAP2PS "map.ps","w" // Map image.
#define MAPGENFILE "./map.gen","r" // Input coordinates.
#define MAX(a,b) ((b>a)?(b):(a))
#define MAXINTSTEPS 3000 // Maximum number of time steps in nonlinvoltra.
#define MAXNSQLOG 18 // The number of sample points for rho_0 is <~2^MAXNSQLOG.
#define MIN(a,b) ((b<a)?(b):(a))
#define MINH 1e-5 // Smallest permitted time step in the integrator.
#define MINPOPFAC 0.1 // Replace 0 population by a fraction of the minimum.
#define NR_END 1
#define NSUBDIV 1 // Number of linear subdivisions for digitizing the density.
#define PADDING 1.5 // Determines space between map and boundary.
#define PI 3.141592653589793
#define SIGMA 0.1 // Initial width of Gaussian blur.
#define SIGMAFAC 1.2 // Increase sigma by this factor. Must be > 1.
#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr;
#define TIMELIMIT 1e8 // Maximum time allowed in integrator.
#define TOLF 1e-3 // Sensitivity w. r. t. function value in newt2.
#define TOLINT 1e-3 // Sensitivity of the integrator.
#define TOLX 1e-3 // Sensitivity w. r. t. independent variables in newt2.
#define TRUE !FALSE

// Types

typedef int BOOLEAN;
typedef struct
{
float x;
float y;
} POINT;

// Globals

float bbmaxx,*bbmaxy,*bbminx,*bbminy,**gridvx,*gridvy,maxx,maxy,minpop,
minx,miny,polymaxx,polymaxy,polyminx,polyminy, *rho,**rho_0,**vx,**vy,*x,
*xappr,xstepsize,**y,*yappr,ystepsize;
int lx,ly,maxid,nblurs=0,npoly, npolycorn,*npolyinreg,nregcorn,nregion,
polygonid,**polyinreg,*regionid,*regionidinv,*within;
POINT *polycorn,*regcorn;

// Function prototypes

int readline(char line[],FILE *infile);
void countpoly(FILE *infile);
void countcorn(FILE *infile);
void readcorn(FILE *infile);
void makeregion(void);
void pspicture(FILE *outfile);
void bboxes(void);
void interior(void);
double regionarea(int ncrns,POINT *polygon);
void digdens(void);
void four1(float data[],unsigned long nn,int isign);
void realft(float data[],unsigned long n,int isign);
void cosft(float z[],unsigned long n,int isign);
void sinft(float z[],unsigned long n,int isign);
void coscosft(float **y,int isign1,int isign2);
void cossinft(float **y,int isign1,int isign2);
void sincosft(float **y,int isign1,int isign2);
float **dmatrix(long nrl,long nrh,long ncl,long nch);
float *d3tensor(long nrl, long nrh, long ncl, long nch, long ndl, long ndh);
void free_matrix(float **m,long nrl,long nrh,long ncl,long nch);
void free_f3tensor(float *t,long nrl,long nrh,long ncl,long nch,long ndl,
long ndh);
void fourn(float data[],unsigned long nn[],int ndim,int isign);
void rlft3(float *data,float **speq,unsigned long nn1,unsigned long nn2,
unsigned long nn3,int isign);
void gaussianblur(void);
void initcond(void);
void calcv(float t);
float intpol(float **arr,float x,float y);
BOOLEAN newt2(float h,float *xappr,float xguess,float *yappr,float yguess,
int j,int k);
BOOLEAN nonlinvoltra(void);
POINT transf(POINT p);
void cartogram(void);

// Function to read one line.

int readline(char line[],FILE *infile)
{
if (fgets(line,LINELENGTH,infile)==NULL) return 1;
return 0;
}

// Function to count the number of polygons.

void countpoly(FILE *infile)
{
char line[LINELENGTH];

npoly = 0;
while (!readline(line,infile)) if (line[0] == 'E') npoly++;
npoly--; // The .gen file ends with two consecutive "END"s.
}

// Function to count polygon corners. Also determines minimum/maximum x-/y-
// coordinate.

void countcorn(FILE *infile)
{
BOOLEAN bnd_ok = FALSE;
char line[LINELENGTH];
float x,y;
int polyctr=0,ratiolog;

npolycorn = (int*)calloc(npoly,sizeof(int));
polycorn = (POINT *)malloc(npoly*sizeof(POINT));
readline(line,infile); // Skip first line.
readline(line,infile);
sscanf(line,"%f %f",&x,&y);
polyminx = x; polymaxx = x; polyminy = y; polymaxy = y;
npolycorn[0] = 1;
while (!readline(line,infile))
{
if (line[0] != 'E')
{
sscanf(line,"%f %f",&x,&y);
if (x < polyminx) polyminx = x;
if (x > polymaxx) polymaxx = x;
if (y < polyminy) polyminy = y;
if (y > polymaxy) polymaxy = y;
npolycorn[polyctr]++;
}
else
{
readline(line,infile);
polycorn[polyctr] = (POINT )malloc(npolycorn[polyctr]sizeof(POINT));
polyctr++;
}
}
if (ceil(log((polymaxx-polyminx)/(polymaxy-polyminy))/log(2))+
floor(log((polymaxx-polyminx)/(polymaxy-polyminy))/log(2))>
2*log((polymaxx-polyminx)/(polymaxy-polyminy))/log(2))
ratiolog = (int)floor(log((polymaxx-polyminx)/(polymaxy-polyminy))/log(2));
else
ratiolog = (int)ceil(log((polymaxx-polyminx)/(polymaxy-polyminy))/log(2));
lx = (int)pow(2,(int)(0.5*(ratiolog+MAXNSQLOG)));
ly = (int)pow(2,(int)(0.5*(MAXNSQLOG-ratiolog)));
if ((polymaxx-polyminx)/lx > (polymaxy-polyminy)/ly)
{
maxx = 0.5 ((1PADDING)*polymaxx(1-PADDING)polyminx);
minx = 0.5 ((1-PADDING)*polymaxx(1PADDING)polyminx);
maxy = 0.5 (polymaxypolyminy(maxx-minx)ly/lx);
miny = 0.5 (polymaxy+polyminy-(maxx-minx)ly/lx);
}
else
{
maxy = 0.5 ((1PADDING)*polymaxy(1-PADDING)polyminy);
miny = 0.5 ((1-PADDING)*polymaxy(1PADDING)polyminy);
maxx = 0.5 (polymaxxpolyminx(maxy-miny)lx/ly);
minx = 0.5 (polymaxx+polyminx-(maxy-miny)lx/ly);
}

// Uncomment the next lines for interactive choice of boundary conditions.

/* printf("For the %i polygon(s) under consideration:\n",npoly);
printf("minimum x = %f\tmaximum x = %f\n",polyminx,polymaxx);
printf("minimum y = %f\tmaximum y = %f\n",polyminy,polymaxy);
while (!bnd_ok)
{
printf("Type in your choice of boundaries.\nminx = ");
scanf("%f",&minx);
printf("maxx = ");
scanf("%f",&maxx);
printf("miny = ");
scanf("%f",&miny);
printf("maxy = ");
scanf("%f",&maxy);
if (minx>polyminx || maxx<polymaxx || miny>polyminy || maxy<polymaxy)
printf("Invalid choice, does not enclose the polygon(s).\n");
else bnd_ok = TRUE;
}*/
}

// Function to read polygon corners. The first and last vertex of each polygon
// must be identical.

void readcorn(FILE *infile)
{
char line[LINELENGTH];
float xcoord,ycoord;
int i,id,polyctr=0;

polygonid = (int )malloc(npolysizeof(int));
xstepsize = (maxx-minx)/lx;
ystepsize = (maxy-miny)/ly;
if (fabs((xstepsize/ystepsize)-1)>1e-3)
fprintf(stderr,"WARNING: Area elements are not square: %f : %f\n",
xstepsize,ystepsize);
readline(line,infile);
sscanf(line,"%i",&id);
polygonid[polyctr] = id;
i = 0;
while (!readline(line,infile))
{
if (line[0] != 'E')
{
sscanf(line,"%f %f",&xcoord,&ycoord);
polycorn[polyctr] .x = (xcoord-minx)/xstepsize;
polycorn[polyctr][i++].y = (ycoord-miny)/ystepsize;
}
else
{
// Is first and last vertex the same?
if (fabs(polycorn[polyctr][0].x-
polycorn[polyctr][npolycorn[polyctr]-1].x)+
fabs(polycorn[polyctr][0].y-
polycorn[polyctr][npolycorn[polyctr]-1].y)>1e-12)
{
fprintf(stderr,
"ERROR: %i-th polygon does not close upon itself.\n",
polyctr+1);
fprintf(stderr,"Identifier %i, first point %f %f.\n",
polygonid[polyctr],polycorn[polyctr][0].x*xstepsize+minx,
polycorn[polyctr][0].y*ystepsize+miny);
exit(1);
}
readline(line,infile);
sscanf(line,"%i",&id);
i = 0;
polyctr++;
if (polyctr<npoly) polygonid[polyctr] = id;
}
}
polyminx = (polyminx-minx)/xstepsize;
polyminy = (polyminy-miny)/ystepsize;
polymaxx = (polymaxx-minx)/xstepsize;
polymaxy = (polymaxy-miny)/ystepsize;
}
// Function to make regions from polygons.
void makeregion(void)
{
BOOLEAN repeat;
int i,lastid,minid,polyctr,ptctr,regctr;
// Count the number of regions.
nregion = 0;
maxid = minid = polygonid[0];
for (polyctr=0; polyctr<npoly; polyctr++)
{
if (polygonid[polyctr] == -99999) continue;
if (polygonid[polyctr]>maxid || polygonid[polyctr]<minid) nregion++;
else
{
repeat = FALSE;
for (i=0; i<polyctr; i++)
if (polygonid[polyctr]==polygonid)
{
repeat = TRUE;
break;
}
if (!repeat) nregion++;
}
if (polygonid[polyctr]>maxid) maxid = polygonid[polyctr];
if (polygonid[polyctr]<minid) minid = polygonid[polyctr];
}
if (minid < 0)
{
fprintf(stderr,
"ERROR: Negative region identifier %i.\n",minid);
exit(1);
}

// Match region identifiers.

regionid = (int )malloc(nregionsizeof(int));
nregion = 0;
maxid = minid = polygonid[0];
for (polyctr=0; polyctr<npoly; polyctr++)
{
if (polygonid[polyctr] == -99999) continue;
if (polygonid[polyctr]>maxid || polygonid[polyctr]<minid)
regionid[nregion++] = polygonid[polyctr];
else
{
repeat = FALSE;
for (i=0; i<polyctr; i++)
if (polygonid[polyctr]==polygonid )
{
repeat = TRUE;
break;
}
if (!repeat) regionid[nregion++] = polygonid[polyctr];
}
if (polygonid[polyctr]>maxid) maxid = polygonid[polyctr];
if (polygonid[polyctr]<minid) minid = polygonid[polyctr];
}
regionidinv = (int)malloc((maxid+1)sizeof(int));
// Negative number for unused identifiers.
for (i=0; i<=maxid; i++) regionidinv = -1;
for (regctr=0; regctr<nregion; regctr++)
regionidinv[regionid[regctr]] = regctr;

// Which polygons contribute to which regions?

npolyinreg = (int*)calloc(nregion,sizeof(int));
polyinreg = (int *)malloc(nregion*sizeof(int));
lastid = polygonid[0];
for (polyctr=0; polyctr<npoly; polyctr++)
{
if (polygonid[polyctr] != -99999)
{
npolyinreg[regionidinv[polygonid[polyctr]]]++;
lastid = polygonid[polyctr];
}
else npolyinreg[regionidinv[lastid]]++;
}
for (regctr=0; regctr<nregion; regctr++)
polyinreg[regctr] = (int )malloc(npolyinreg[regctr]sizeof(int));
for (regctr=0; regctr<nregion; regctr++) npolyinreg[regctr] = 0;
lastid = polygonid[0];
for (polyctr=0; polyctr<npoly; polyctr++)
{
if (polygonid[polyctr] != -99999)
{
polyinreg[regionidinv[polygonid[polyctr]]]
[npolyinreg[regionidinv[polygonid[polyctr]]]++] = polyctr;
lastid = polygonid[polyctr];
}
else polyinreg[regionidinv[lastid]][npolyinreg[regionidinv[lastid]]++]
= polyctr;
}

// Make regions from polygons. Start and end each polygon at (0,0).

nregcorn = (int*)calloc(nregion,sizeof(int));
regcorn = (POINT *)malloc(nregion*sizeof(POINT));
for (regctr=0; regctr<nregion; regctr++)
{
for (i=0; i<npolyinreg[regctr]; i++)
nregcorn[regctr] += npolycorn[polyinreg[regctr] ]+1;
nregcorn[regctr]++;
}
for (regctr=0; regctr<nregion; regctr++)
{
regcorn[regctr] = (POINT)malloc(nregcorn[regctr]sizeof(POINT));
ptctr = 0;
regcorn[regctr][ptctr].x = regcorn[regctr][ptctr++].y = 0.0;
for (polyctr=0; polyctr<npolyinreg[regctr]; polyctr++)
{
for (i=0; i<npolycorn[polyinreg[regctr][polyctr]]; i++)
regcorn[regctr][ptctr++] = polycorn[polyinreg[regctr][polyctr]];
regcorn[regctr][ptctr].x = regcorn[regctr][ptctr++].y = 0.0;
}
}
}

// Function to prepare a map in postscript standard letter format.

void pspicture(FILE *outfile)
{
char line[LINELENGTH];
float addx,addy,b,conv,g,r;
int ptctr,regctr;

if (11*lx > 8.5*ly)
{
conv = (float)8.5*72/lx;
addx = 0;
addy = 11 36-8.5*36ly/lx;
}
else
{
conv = (float)11*72/ly;
addx = 8.5 36-11*36lx/ly;
addy = 0;
}
fprintf(outfile,"0.5 setlinewidth\n");
for (regctr=0; regctr<nregion; regctr++)
{
fprintf(outfile,"newpath\n");
fprintf(outfile,"%f %f moveto\n",
regcorn[regctr][1].x*conv+addx,
regcorn[regctr][1].y*conv+addy);
for (ptctr=2; ptctr<nregcorn[regctr]; ptctr++)
{
if (fabs(regcorn[regctr][ptctr].x)+
fabs(regcorn[regctr][ptctr].y)>1e-12)
fprintf(outfile,"%f %f lineto\n",
regcorn[regctr][ptctr].x*conv+addx,
regcorn[regctr][ptctr].y*conv+addy);
else
{
fprintf(outfile,"closepath\n");
if (ptctr<nregcorn[regctr]-1)
{
ptctr++;
fprintf(outfile,"%f %f moveto\n",
regcorn[regctr][ptctr].x*conv+addx,
regcorn[regctr][ptctr].y*conv+addy);
}
}
}
// Determine colors for map (without better knowledge I will do it
// arbitrarily).

if (regctr%3 == 0)
{
r = (float)regctr/nregion;
g = 1-(float)regctr/nregion;
b = fabs(1-2*(float)regctr/nregion);
}
else if (regctr%3 == 1)
{
b = (float)regctr/nregion;
r = 1-(float)regctr/nregion;
g = fabs(1-2*(float)regctr/nregion);
}
else
{
g = (float)regctr/nregion;
b = 1-(float)regctr/nregion;
r = fabs(1-2*(float)regctr/nregion);
}
fprintf(outfile,"%f %f %f setrgbcolor\ngsave\nfill\n",r,g,b);
fprintf(outfile,"grestore\n0 setgray stroke\n");
}
fprintf(outfile,"showpage\n");
}

// Function to find the bounding box for each polygon.

void bboxes(void)
{
int i,j;
float maxx, minx, maxy, miny;

bbmaxx = (float )malloc(npolysizeof(float));
bbmaxy = (float )malloc(npolysizeof(float));
bbminx = (float )malloc(npolysizeof(float));
bbminy = (float )malloc(npolysizeof(float));
for (i = 0; i < npoly; i++)
{
maxx = polycorn [0].x;
maxy = polycorn[0].y;
minx = maxx;
miny = maxy;
for (j = 0; j < npolycorn ; j++)
{
if (polycorn[j].x > maxx) maxx = polycorn [j].x;
if (polycorn[j].x < minx) minx = polycorn [j].x;
if (polycorn[j].y < miny) miny = polycorn [j].y;
if (polycorn[j].y > maxy) maxy = polycorn [j].y;
}
bbmaxx=maxx;
bbmaxy =maxy;
bbminx=minx;
bbminy =miny;
}
}
void interior(void)
{
int i,inhowmanyregions,inregion[2],j,k,l,m,n,regctr;
// Initialize within[][]. -1 means outside all regions.
for (i=0; i<=lx; i++) for (j=0; j<=ly; j++) within[j] = -1;

// Fill within[][].

for (i=0; i<nregion; i++) for (j=0; j<npolyinreg ; j++)
for (k=0, n=npolycorn[polyinreg[j]]-1;
k<npolycorn[polyinreg [j]]; n=k++)
for (l=(int)ceil(MIN(polycorn[polyinreg[j]][k-1].y,
polycorn[polyinreg [j]][k].y));
l<MAX(polycorn[polyinreg[j]][k-1].y,
polycorn[polyinreg [j]][k].y); l++)
for (m=(int)floor(bbminx[polyinreg[j]]);
m<(polycorn[polyinreg [j]][n].x-
polycorn[polyinreg[j]][k].x)*
(l-polycorn[polyinreg [j]][k].y)/
(polycorn[polyinreg[j]][n].y-
polycorn[polyinreg [j]][k].y)+
polycorn[polyinreg[j]][k].x;
m++)
within[m][l] = i-within[m][l]-1;
}

// Function to determine polygon area. This is needed to determine the average
// population.
// The problem in short is to find the area of a polygon whose vertices are
// given. Recall Stokes' theorem in 3d for a vector field v:
// integral[around closed curve dA]v(x,y,z).ds =
// integral[over area A]curl(v).dA.
// Now let v(x,y,z) = (0,Q(x,y),0) and dA = (0,0,dx*dy). Then
// integral[around closed curve dA]Q(x,y)dy = integral[over area A]dQ/dx dxdy.
// If Q = x:
// A = integral[over area A]dx*dy = integral[around closed curve dA]x dy.
// For every edge from (x ,y) to (x[i 1],y[i1]) there is a
// parametrization
// (x(t),y(t)) = ((1-t)x tx[i+1],(1-t)y+ty[i1]), 0<t<1
// so that the path integral along this edge is
// int[from 0 to 1]{(1-t)xt*x[i+1]}(y[i1]-y)dt =
// 0.5(y[i1]-y)(x+x[i1]).
// Summing over all edges yields:
//
// Area = 0.5*[(x[0]+x[1])(y[1]-y[0]) + (x[1]+x[2])(y[2]-y[1]) + ...
// ...(x[n-1]+x[n])(y[n]-y[n-1])+(x[n]x[0])(y[0]-y[n])]
// ArcGIS treats a clockwise direction as positive, so there is a minus sign.
double regionarea(int ncrns,POINT *polygon)
{
double area=0;
int i;
for (i=0; i<ncrns-1; i++)
area -=
0.5(polygon.xpolygon[i+1].x)(polygon[i1].y-polygon.y);
return area -= 0.5(polygon[ncrns-1].x+polygon[0].x)
(polygon[0].y-polygon[ncrns-1].y);
}
// Function to digitize density.
void digdens(void)
{
char line[LINELENGTH];
double area,avgdens,*cases,dens,minpop=INFTY,ncases,totarea=0.0,totpop=0.0;
FILE* infile;
int i,id,ii,inhowmanyregions,inregion[2],j,jj,regctr;
if ((infile=fopen(CENSUSFILE))==NULL)
{
fprintf(stderr,"ERROR: Cannot find CENSUSFILE.\n");
exit(1);
}
// Find the minimum positive number of cases.
while (!readline(line,infile))
{
sscanf(line,"%i %lf",&id,&ncases);
if (ncases<minpop && ncases>1e-12) minpop = ncases;
}
fclose(infile);
// Store the number of cases in an array.
cases = (double)malloc(nregionsizeof(double));
for (i=0; i<nregion; i++) cases = -1.0;
infile = fopen(CENSUSFILE);
while (!readline(line,infile))
{
sscanf(line,"%i %lf",&id,&ncases);
if (id>maxid || regionidinv[id]<0)
{
fprintf(stderr,"ERROR: Identifier %i in CENSUSFILE does not\n",id);
fprintf(stderr,"match any identifier in generate file.\n");
exit(1);
}
if (ncases>1e-12) totpop += (cases[regionidinv[id]] = ncases);
else totpop += (cases[regionidinv[id]] = MINPOPFAC*minpop);
}
for (regctr=0; regctr<nregion; regctr++) if (cases[regctr] < 0.0)
{
fprintf(stderr,"ERROR: No density for region %i?\n",regionid[regctr]);
fprintf(stderr,"cases = %f\n",cases[regctr]);
exit(1);
}
fclose(infile);
// Calculate regions' areas, total area to be mapped, regional and average
// densities.
area = (double)malloc(nregionsizeof(double));
for (regctr=0; regctr<nregion; regctr++)
totarea += (area[regctr] = regionarea(nregcorn[regctr],regcorn[regctr]));
dens = (double)malloc(nregionsizeof(double));
for (regctr=0; regctr<nregion; regctr++)
dens[regctr] = cases[regctr]/area[regctr];
avgdens = totpop/totarea;
// Digitize density.
for (i=0; i<=lx; i++) for (j=0; j<=ly; j++) rho_0[j] = 0; // Initialize.
printf("digitizing density ...\n");
for (i=0; i<lx; i++) for (j=0; j<ly; j++)
{
if (within[j]==-1) rho_0[j] = avgdens;
else rho_0[j] = dens[within[j]];
}
// Fill the edges correctly.
rho_0[0][0] += rho_0[0][ly] + rho_0[lx][0] + rho_0[lx][ly];
for (i=1; i<lx; i++) rho_0[0] += rho_0[ly];
for (j=1; j<ly; j++) rho_0[0][j] += rho_0[lx][j];
for (i=0; i<lx; i++) rho_0[ly] = rho_0[0];
for (j=0; j<=ly; j++) rho_0[lx][j] = rho_0[0][j];
// Replace rho_0 by Fourier transform
coscosft(rho_0,1,1);
free(area);
free(cases);
for (i=0; i<npoly; i++) free(polycorn);
free(polycorn);
for (i=0; i<nregion; i++) free(regcorn);
free(regcorn);
free(dens);
free(npolycorn);
free(nregcorn);
free(polygonid);
free(regionid);
free(regionidinv);
free(bbmaxx);
free(bbmaxy);
free(bbminx);
free(bbminy);
for (i=0; i<nregion; i++) free(polyinreg);
free(polyinreg);
free(npolyinreg);
}
// Function to replace data[1...2*nn] by its discrete Fourier transform, if
// isign is input as 1; or replaces data[1...2*nn] by nn times its inverse
// discrete Fourier transform, if isign is input as -1. data is a complex array
// of length nn or, equivalently, a real array of length 2*nn. nn MUST be an
// integer power of 2 (this is not checked for!).
// From "Numerical Recipes in C".
void four1(float data[],unsigned long nn,int isign)
{
double theta,wi,wpi,wpr,wr,wtemp;
float tempi,tempr;
unsigned long i,istep,j,m,mmax,n;
n=nn<<1;
j=1;
for (i=1; i<n; i+=2)
{
if (j>i)
{
// This is the bit-reversal section of the routine.
SWAP(data[j],data);
SWAP(data[j1],data[i1]); // Exchange the two complex numbers.
}
m=n>>1;
while (m>=2 && j>m)
{
j -= m;
m>>=1;
}
j += m;
}
// Here begins the Danielson-Lanczos section of the routine.
mmax=2;
while (n>mmax) // Outer loop executed log_2 nn times.
{
istep = mmax<<1;
// Initialize the trigonometric recurrence.
theta = isign*(6.28318530717959/mmax);
wtemp = sin(0.5*theta);
wpr = -2.0wtempwtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (m=1; m<mmax; m+=2) // Here are the two nested inner loops.
{
for (i=m; i<=n; i+=istep)
{
j=i+mmax; // This is the Danielson-Lanczos formula
tempr=wrdata[j]-widata[j+1];
tempi=wrdata[j1]widata[j];
data[j]=data-tempr;
data[j1]=data[i1]-tempi;
data += tempr;
data[i+1] += tempi;
}
wr = (wtemp=wr)wpr-wiwpi+wr; // Trigonometric recurrence.
wi = wiwprwtempwpiwi;
}
mmax=istep;
}
}
// Function to calculate the Fourier Transform of a set of n real-valued data
// points. It replaces this data (which is stored in array data[1...n]) by the
// positive frequency half of its complex Fourier Transform. The real-valued
// first and last components of the complex transform are returned as elements
// data[1] and data[2] respectively. n must be a power of 2. This routine also
// calculates the inverse transform of a complex data array if it is the
// transform of real data. (Result in this case must be multiplied by 2/n).
// From "Numerical Recipes in C".
void realft(float data[],unsigned long n,int isign)
{
double theta,wi,wpi,wpr,wr,wtemp;
float c1=0.5,c2,h1i,h1r,h2i,h2r;
unsigned long i,i1,i2,i3,i4,np3;
theta = 3.141592653589793/(double) (n>>1); // Initialize the recurrence
if (isign == 1)
{
c2 = -0.5;
four1(data,n>>1,1); // The forward transform is here.
}
else // Otherwise set up for an inverse transform.
{
c2 = 0.5;
theta = -theta;
}
wtemp = sin(0.5*theta);
wpr = -2.0wtempwtemp;
wpi = sin(theta);
wr = 1.0+wpr;
wi = wpi;
np3 = n+3;
for (i=2; i<=(n>>2); i++) // Case i=1 done separately below.
{
i4 = 1(i3=np3-(i2=1+(i1=ii-1)));
// The two separate transforms are separated out of data.
h1r = c1*(data[i1]+data[i3]);
h1i = c1*(data[i2]-data[i4]);
h2r = -c2*(data[i2]+data[i4]);
h2i = c2*(data[i1]-data[i3]);
// Here they are recombined to form the true transform of the original
// data.
data[i1] = h1r+wrh2r-wih2i;
data[i2] = h1iwrh2iwih2r;
data[i3] = h1r-wrh2r+wih2i;
data[i4] = -h1iwrh2iwih2r;
wr = (wtemp=wr)wpr-wiwpi+wr; // The recurrence.
wi = wiwprwtempwpiwi;
}
if (isign == 1)
{
data[1] = (h1r=data[1])+data[2]; // Squeeze the first and last data
// together to get them all within the original array.
data[2] = h1r-data[2];
}
else
{
data[1] = c1*((h1r=data[1])+data[2]);
data[2] = c1*(h1r-data[2]);
// This is the inverse transform for the case isign = -1.
four1(data,n>>1,-1);
}
}
// Function to calculate the cosine transform of a set z[0...n] of real-valued
// data points. The transformed data replace the original data in array z. n
// must be a power of 2. For forward transform set isign=1, for back transform
// isign = -1. (Note: The factor 2/n has been taken care of.)
// From "Numerical Recipes in C".
void cosft(float z[],unsigned long n,int isign)
{
double theta,wi=0.0,wpi,wpr,wr=1.0,wtemp;
float *a,sum,y1,y2;
int j,n2;
// Numerical Recipes starts counting at 1 which is rather confusing. I will
// count from 0.
a = (float)malloc((n+2)sizeof(float));
for (j=1; j<=n+1; j++) a[j] = z[j-1];
// Here is the Numerical Recipes code.
theta=PI/n; //Initialize the recurrence.
wtemp = sin(0.5*theta);
wpr = -2.0wtempwtemp;
wpi = sin(theta);
sum = 0.5*(a[1]-a[n+1]);
a[1] = 0.5*(a[1]a[n1]);
n2 = n+2;
for (j=2; j<=(n>>1); j++)
{
wr = (wtemp=wr)wpr-wiwpi+wr;
wi = wiwprwtempwpiwi;
y1 = 0.5*(a[j]+a[n2-j]);
y2 = (a[j]-a[n2-j]);
a[j] = y1-wi*y2;
a[n2-j] = y1+wi*y2;
sum += wr*y2;
}
realft(a,n,1);
a[n+1] = a[2];
a[2] = sum;
for (j=4; j<=n; j+=2)
{
sum += a[j];
a[j] = sum;
}
// Finally I revert to my counting method.
if (isign == 1) for (j=1; j<=n+1; j++) z[j-1] = a[j];
else if (isign == -1) for (j=1; j<=n+1; j++) z[j-1] = 2.0*a[j]/n;
free(a);
}
// Function to calculate the sine transform of a set of n real-valued data
// points stored in array z[0..n]. The number n must be a power of 2. On exit
// z is replaced by its transform. For forward transform set isign=1, for back
// transform isign = -1.
void sinft(float z[],unsigned long n,int isign)
{
double theta,wi=0.0,wpi,wpr,wr=1.0,wtemp;
float *a,sum,y1,y2;
int j;
unsigned long n2=n+2;
// See my comment about Numerical Recipe's counting above. Note that the last
// component plays a completely passive role and does not need to be stored.
a = (float*) malloc((n+1)*sizeof(float));
for (j=1; j<=n; j++) a[j] = z[j-1];
// Here is the Numerical Recipes code.
theta = PI/(double)n; // Initialize the recurrence.
wtemp = sin(0.5*theta);
wpr = -2.0wtempwtemp;
wpi = sin(theta);
a[1] = 0.0;
for (j=2; j<=(n>>1)+1; j++)
{
// Calculate the sine for the auxiliary array.
wr = (wtemp=wr)wpr-wiwpi+wr;
// The cosine is needed to continue the recurrence.
wi = wiwprwtempwpiwi;
// Construct the auxiliary array.
y1 = wi*(a[j]+a[n2-j]);
y2 = 0.5*(a[j]-a[n2-j]);
// Terms j and N-j are related.
a[j] = y1+y2;
a[n2-j] = y1-y2;
}
// Transform the auxiliary array.
realft(a,n,1);
// Initialize the sum used for odd terms below.
a[1] *= 0.5;
sum = a[2] = 0.0;
// Even terms determined directly. Odd terms determined by running sum.
for (j=1; j<=n-1; j+=2)
{
sum += a[j];
a[j] = a[j+1];
a[j+1] = sum;
}
// Change the indices.
if (isign == 1) for (j=1; j<=n; j++) z[j-1] = a[j];
else if (isign == -1) for (j=1; j<=n; j++) z[j-1] = 2.0*a[j]/n;
z[n] = 0.0;
free(a);
}
// Function to calculate a two-dimensional cosine Fourier transform. Forward/
// backward transform in x: isign1 = +/-1, in y: isign2 = +/-1.
void coscosft(float **y,int isign1,int isign2)
{
float temp[lx+1];
unsigned long i,j;
for (i=0; i<=lx; i++)
{
cosft(y,ly,isign2);
}
for (j=0; j<=ly; j++)
{
for (i=0; i<=lx; i++) temp=y[j];
cosft(temp,lx,isign1);
for (i=0; i<=lx; i++) y[j]=temp;
}
}
// Function to calculate a cosine Fourier transform in x and a sine transform
// in y. Forward/backward transform in x: isign1 = +/-1, in y: isign2 = +/-1.
void cossinft(float **y,int isign1,int isign2)
{
float temp[lx+1];
unsigned long i,j;
for (i=0; i<=lx; i++)
{
sinft(y,ly,isign2);
}
for (j=0; j<=ly; j++)
{
for (i=0; i<=lx; i++) temp=y[j];
cosft(temp,lx,isign1);
for (i=0; i<=lx; i++) y[j]=temp;
}
}
// Function to calculate a sine Fourier transform in x and a cosine transform
// in y. Forward/backward transform in x: isign1 = +/-1, in y: isign2 = +/-1.
void sincosft(float **y,int isign1,int isign2)
{
float temp[lx+1];
unsigned long i,j;
for (i=0; i<=lx; i++)
{
cosft(y,ly,isign2);
}
for (j=0; j<=ly; j++)
{
for (i=0; i<=lx; i++) temp=y[j];
sinft(temp,lx,isign1);
for (i=0; i<=lx; i++) y[j]=temp;
}
}
// Function to allocate a float matrix with subscript range
// m[nrl..nrh][ncl..nch]. From "Numerical Recipes in C".
float **dmatrix(long nrl,long nrh,long ncl,long nch)
{
long i, nrow=nrh-nrl1,ncol=nch-ncl1;
float **m;
/* allocate pointers to rows */
m=(float **) malloc((unsigned int)((nrow+NR_END)sizeof(float)));
if (!m)
{
fprintf(stderr,"allocation failure 1 in matrix()\n");
exit(1);
}
m += NR_END;
m -= nrl;
/* allocate rows and set pointers to them */
m[nrl]=(float *) malloc((unsigned int)((nrowncol+NR_END)sizeof(float)));
if (!m[nrl])
{
fprintf(stderr,"allocation failure 2 in matrix()\n");
exit(1);
}
m[nrl] += NR_END;
m[nrl] -= ncl;
for(i=nrl1;i<=nrh;i+) m=m[i-1]+ncol;
/* return pointer to array of pointers to rows */
return m;
}
// Function to allocate a float 3tensor with range
// t[nrl..nrh][ncl..nch][ndl..ndh]. From "Numerical Recipes in C".
float *d3tensor(long nrl, long nrh, long ncl, long nch, long ndl, long ndh)
{
long i,j,nrow=nrh-nrl1,ncol=nch-ncl+1,ndep=ndh-ndl1;
float *t;

/* allocate pointers to pointers to rows */
t=(float *) malloc((size t)((nrow+NREND) sizeof(float*)));
if (!t)
{
fprintf(stderr,"allocation failure 1 in f3tensor()\n");
exit(1);
}
t += NR_END;
t -= nrl;

/* allocate pointers to rows and set pointers to them */
t[nrl]=(float **) malloc((size t)((nrowncol+NREND)*sizeof(float)));
if (!t[nrl])
{
fprintf(stderr,"allocation failure 2 in f3tensor()\n");
exit(1);
}
t[nrl] += NR_END;
t[nrl] -= ncl;

/* allocate rows and set pointers to them */
t[nrl][ncl]=(float *) malloc((size t)((nrowncol*ndep+NREND)sizeof(float)));
if (!t[nrl][ncl])
{
fprintf(stderr,"allocation failure 3 in f3tensor()\n");
exit(1);
}
t[nrl][ncl] += NR_END;
t[nrl][ncl] -= ndl;

for(j=ncl 1;j<=nch;j+) t[nrl][j]=t[nrl][j-1]+ndep;
for(i=nrl 1;i<=nrh;i+) {
t =t[i-1]+ncol;
t[ncl]=t[i-1][ncl]+ncol*ndep;
for(j=ncl 1;j<=nch;j+) t [j]=t[j-1]+ndep;
}

/* return pointer to array of pointers to rows */
return t;
}

void free_matrix(float **m,long nrl,long nrh,long ncl,long nch)
{
free((char*) (m[nrl]+ncl-1));
free((char*) (m+nrl-1));
}

void free_f3tensor(float *t,long nrl,long nrh,long ncl,long nch,long ndl,
long ndh)
{
free((char*) (t[nrl][ncl]+ndl-1));
free((char*) (t[nrl]+ncl-1));
free((char*) (t+nrl-1));
}

// Function to replace data by its ndim-dimensional discrete Fourier transform,
// if isign is input as 1. nn[1..ndim] is an integer array containing the
// lengths of each dimension (number of complex values), which MUST be all
// powers of 2. data is a real array of length twice the product of these
// lengths, in which the data are stored as in a multidimensional complex
// array: real and imaginary parts of each element are in consecutive
// locations, and the rightmost index of the array increases most rapidly as
// one proceeds along data. For a two-dimensional array, this is equivalent to
// storing the arrays by rows. If isign is input as -1, data is replaced by its
// inverse transform times the product of the lengths of all dimensions.

void fourn(float data[],unsigned long nn[],int ndim,int isign)
{
int idim;
unsigned long i1,i2,i3,i2rev,i3rev,ip1,ip2,ip3,ifp1,ifp2;
unsigned long ibit,k1,k2,n,nprev,nrem,ntot;
double tempi,tempr;
float theta,wi,wpi,wpr,wr,wtemp;

for (ntot=1, idim=1; idim<=ndim; idim++)
ntot *= nn[idim];
nprev = 1;
for (idim=ndim; idim>=1; idim--)
{
n = nn[idim];
nrem = ntot/(n*nprev);
ip1=nprev << 1;
ip2 = ip1*n;
ip3 = ip2*nrem;
i2rev = 1;
for (i2=1; i2<=ip2; i2+=ip1)
{
if (i2 < i2rev)
{
for (i1=i2; i1<=i2+ip1-2; i1+=2)
{
for (i3=i1; i3<=ip3; i3+=ip2)
{
i3rev = i2rev+i3-i2;
SWAP(data[i3],data[i3rev]);
SWAP(data[i3 1],data[i3rev1]);
}
}
}
ibit = ip2>>1;
while (ibit>=ip1 && i2rev>ibit)
{
i2rev -= ibit;
ibit >>= 1;
}
i2rev += ibit;
}
ifp1 = ip1;
while (ifp1 < ip2)
{
ifp2 = ifp1 << 1;
theta = 2 isignPI/(ifp2/ip1);
wtemp = sin(0.5*theta);
wpr = -2.0 wtempwtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (i3=1; i3<=ifp1; i3+=ip1)
{
for (i1=i3; i1<=i3+ip1-2; i1+=2)
{
for (i2=i1; i2<=ip3; i2+=ifp2)
{
k1 = i2;
k2 = k1+ifp1;
tempr = (float)wr data[k2]-(float)widata[k2+1];
tempi = (float)wr data[k21](float)widata[k2];
data[k2] = data[k1]-tempr;
data[k2+1] = data[k1+1]-tempi;
data[k1] += tempr;
data[k1+1] += tempi;
}
}
wr = (wtemp=wr) wpr-wiwpi+wr;
wi = wi wprwtempwpiwi;
}
ifp1 = ifp2;
}
nprev *= n;
}
}

// Function to calculate a three-dimensional Fourier transform of
// data[1..nn1][1..nn2][1..nn3] (where nn1=1 for the case of a logically two-
// dimensional array). This routine returns (for isign=1) the complex fast
// Fourier transform as two complex arrays: On output, data contains the zero
// and positive frequency values of the third frequency component, while
// speq[1..nn1][1..2*nn2] contains the Nyquist critical frequency values of the
// third frequency component. First (and second) frequency components are
// stored for zero, positive, and negative frequencies, in standard wrap-around
// order. See Numerical Recipes for description of how complex values are
// arranged. For isign=-1, the inverse transform (times nn1 nn2nn3/2 as a
// constant multiplicative factor) is performed, with output data (viewed as
// real array) deriving from input data (viewed as complex) and speq. For
// inverse transforms on data not generated first by a forward transform, make
// sure the complex input data array satisfies property 12.5.2 from NR. The
// dimensions nn1, nn2, nn3 must always be integer powers of 2.

void rlft3(float *data,float **speq,unsigned long nn1,unsigned long nn2,
unsigned long nn3,int isign)
{
double theta,wi,wpi,wpr,wr,wtemp;
float c1,c2,h1r,h1i,h2r,h2i;
unsigned long i1,i2,i3,j1,j2,j3,nn[4],ii3;

if (1+&data[nn1][nn2][nn3]-&data[1][1][1] != nn1 nn2nn3)
{
fprintf(stderr,
"rlft3: problem with dimensions or contiguity of data array\n");
exit(1);
}
c1 = 0.5;
c2 = -0.5*isign;
theta = 2 isign(PI/nn3);
wtemp = sin(0.5*theta);
wpr = -2.0 wtempwtemp;
wpi = sin(theta);
nn[1] = nn1;
nn[2] = nn2;
nn[3] = nn3 >> 1;

// Case of forward transform. Here is where most all of the compute time is
// spent. Extend data periodically into speq.

if (isign == 1)
{
fourn(&data[1][1][1]-1,nn,3,isign);
for (i1=1; i1<=nn1; i1++)
for (i2=1, j2=0; i2<=nn2; i2++)
{
speq[i1][++j2] = data[i1][i2][1];
speq[i1][++j2] = data[i1][i2][2];
}
}
for (i1=1; i1<=nn1; i1++)
{
// Zero frequency is its own reflection; otherwise locate corresponding
// negative frequency in wrap-around order.

j1 = (i1 != 1 ? nn1-i1+2 : 1);

// Initialize trigonometric recurrence.

wr = 1.0;
wi = 0.0;
for (ii3=1, i3=1; i3<=(nn3>>2)+1; i3 +,ii3=2)
{
for (i2=1; i2<=nn2; i2++)
{
if (i3 == 1)
{
j2 = (i2 != 1 ? ((nn2-i2)<<1)+3 : 1);
h1r = c1*(data[i1][i2][1]+speq[j1][j2]);
h1i = c1*(data[i1][i2][2]-speq[j1][j2+1]);
h2i = c2*(data[i1][i2][1]-speq[j1][j2]);
h2r = -c2*(data[i1][i2][2] speq[j1][j21]);
data[i1][i2][1] = h1r+h2r;
data[i1][i2][2] = h1i+h2i;
speq[j1][j2] = h1r-h2r;
speq[j1][j2+1] = h2i-h1i;

}
else
{
j2 = (i2 != 1 ? nn2-i2+2 : 1);
j3 = nn3+3-(i3<<1);
h1r = c1*(data[i1][i2][ii3]+data[j1][j2][j3]);
h1i = c1*(data[i1][i2][ii3 1]-data[j1][j2][j31]);
h2i = c2*(data[i1][i2][ii3]-data[j1][j2][j3]);
h2r = -c2*(data[i1][i2][ii3 1]+data[j1][j2][j31]);
data[i1][i2][ii3] = h1r+wr h2r-wih2i;
data[i1][i2][ii3+1] = h1i wrh2iwih2r;
data[j1][j2][j3] = h1r-wr h2r+wih2i;
data[j1][j2][j3+1] = -h1i wrh2iwih2r;
}
}

// Do the recurrence.

wr = (wtemp=wr) wpr-wiwpi+wr;
wi = wi wprwtempwpiwi;
}
}

// Case of reverse transform.

if (isign == -1)
fourn(&data[1][1][1]-1,nn,3,isign);
}

// Function to perform Gaussian blur.

void gaussianblur(void)
{
float **blur,***conv,***pop,**speqblur,**speqconv,*speqpop;
int i,j,p,q;

blur = d3tensor(1,1,1,lx,1,ly);
conv = d3tensor(1,1,1,lx,1,ly);
pop = d3tensor(1,1,1,lx,1,ly);
speqblur = dmatrix(1,1,1,2*lx);
speqconv = dmatrix(1,1,1,2*lx);
speqpop = dmatrix(1,1,1,2*lx);

// Fill population and convolution matrix.

for (i=1; i<=lx; i++) for (j=1; j<=ly; j++)
{
if (i > lx/2) p = i-1-lx;
else p = i-1;
if (j > ly/2) q = j-1-ly;
else q = j-1;
pop[1] [j] = rho_0[i-1][j-1];
conv[1][j] = 0.5*
(erf((p+0.5)/(sqrt(2.0) (SIGMApow(SIGMAFAC,nblurs))))-
erf((p-0.5)/(sqrt(2.0) (SIGMA*pow(SIGMAFAC,nblurs)))))
(erf((q+0.5)/(sqrt(2.0) (SIGMApow(SIGMAFAC,nblurs))))-
erf((q-0.5)/(sqrt(2.0) (SIGMA*pow(SIGMAFAC,nblurs)))))/(lxly);
}

// Fourier transform.

rlft3(pop,speqpop,1,lx,ly,1);
rlft3(conv,speqconv,1,lx,ly,1);

// Multiply pointwise.

for (i=1; i<=lx; i++)
for (j=1; j<=ly/2; j++)
{
blur[1] [2*j-1] =
pop[1][2 j-1]*conv[1][2j-1]-
pop[1][2j]*conv[1][2j];
blur[1][2*j] =
pop[1][2j]*conv[1][2j-1]+
pop[1][2j-1]*conv[1][2j];
}
for (i=1; i<=lx; i++)
{
speqblur[1][2*i-1] =
speqpop[1][2i-1]*speqconv[1][2i-1]-
speqpop[1][2i]*speqconv[1][2i];
speqblur[1][2*i] =
speqpop[1][2i]*speqconv[1][2i-1]+
speqpop[1][2i-1]*speqconv[1][2i];
}
// Backtransform.
rlft3(blur,speqblur,1,lx,ly,-1);
// Write to rho_0.
for (i=1; i<=lx; i++) for (j=1; j<=ly; j++) rho_0[i-1][j-1] = blur[1][j];
free_f3tensor(blur,1,1,1,lx,1,ly);
free_f3tensor(conv,1,1,1,lx,1,ly);
free_f3tensor(pop,1,1,1,lx,1,ly);
free_matrix(speqblur,1,1,1,2*lx);
free_matrix(speqconv,1,1,1,2*lx);
free_matrix(speqpop,1,1,1,2*lx);
}
// Function to initialize rho_0. The original density is blurred with width
// SIGMA*pow(SIGMAFAC,nblurs).
void initcond(void)
{
float maxpop;
int i,j;
// Reconstruct population density.
coscosft(rho_0,-1,-1);
// There must not be negative densities.
for (i=0; i<lx; i++) for (j=0; j<ly; j++) if (rho_0[j]<-1e10)
{
fprintf(stderr,"ERROR: Negative density in DENSITYFILE.\n");
exit(1);
}
// Perform Gaussian blur.
printf("Gaussian blur ...\n");
gaussianblur();
// Find the mimimum density. If it is very small suggest an increase in
// SIGMA.
minpop = rho_0[0][0];
maxpop = rho_0[0][0];
for (i=0; i<lx; i++) for (j=0; j<ly; j++) if (rho_0[j]<minpop)
minpop = rho_0[j];
for (i=0; i<lx; i++) for (j=0; j<ly; j++) if (rho_0[j]>maxpop)
maxpop = rho_0[j];
if (0<minpop && minpop<1e-8*maxpop)
{
fprintf(stderr,"Minimimum population very small (%f). Integrator\n",
minpop);
fprintf(stderr,
"will probably converge very slowly. You can speed up the\n");
fprintf(stderr,"process by increasing SIGMA to a value > %f.\n",
SIGMA*pow(SIGMAFAC,nblurs));
}
// Replace rho_0 by cosine Fourier transform in both variables.
coscosft(rho_0,1,1);
}
// Function to calculate the velocity field
void calcv(float t)
{
int j,k;
// Fill rho with Fourier coefficients.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
rho[j][k] = exp(-((PIj/lx)*(PI*j/lx)+(PI*k/ly)*(PI*k/ly))*t)rho_0[j][k];
// Calculate the Fourier coefficients for the partial derivative of rho.
// Store temporary results in arrays gridvx, gridvy.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
gridvx[j][k] = -(PIj/lx)rho[j][k];
gridvy[j][k] = -(PIk/ly)rho[j][k];
}
// Replace rho by cosine Fourier backtransform in both variables.
coscosft(rho,-1,-1);
// Replace vx by sine Fourier backtransform in the first and cosine Fourier
// backtransform in the second variable.
sincosft(gridvx,-1,-1);
// Replace vy by cosine Fourier backtransform in the first and sine Fourier
// backtransform in the second variable.
cossinft(gridvy,-1,-1);
// Calculate the velocity field.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
gridvx[j][k] = -gridvx[j][k]/rho[j][k];
gridvy[j][k] = -gridvy[j][k]/rho[j][k];
}
}
// Function to bilinearly interpolate a two-dimensional array. For higher
// accuracy one could consider higher order interpolation schemes.
float intpol(float **arr,float x,float y)
{
int gaussx,gaussy;
float deltax,deltay;
// Decompose x and y into an integer part and a decimal.
gaussx = (int)x;
gaussy = (int)y;
deltax = x-gaussx;
deltay = y-gaussy;
// Interpolate.
if (gaussx==lx && gaussy==ly)
return arr[gaussx][gaussy];
if (gaussx==lx)
return (1-deltay)arr[gaussx][gaussy]deltayarr[gaussx][gaussy1];
if (gaussy==ly)
return (1-deltax)arr[gaussx][gaussy]deltaxarr[gaussx1][gaussy];
return (1-deltax)(1-deltay)arr[gaussx][gaussy]+
(1-deltax)deltayarr[gaussx][gaussy1]
deltax(1-deltay)arr[gaussx1][gaussy]
deltaxdeltayarr[gaussx1][gaussy1];
}
// Function to find the root of the system of equations
// xappr-0.5h*v_x(t+h,xappr,yappr)-x[j][k]-0.5*hvx[j][k]=0,
// yappr-0.5h*v_y(t+h,xappr,yappr)-y[j][k]-0.5*hvy[j][k]=0
// with Newton-Raphson. Returns TRUE after sufficient convergence.
BOOLEAN newt2(float h,float *xappr,float xguess,float *yappr,float yguess,
int j,int k)
{
float deltax,deltay,dfxdx,dfxdy,dfydx,dfydy,fx,fy;
int gaussx,gaussxplus,gaussy,gaussyplus,i;
// Initial guess.
*xappr = xguess;
*yappr = yguess;
for (i=1; i<=IMAX; i++)
{
// fx, fy are the left-hand sides of the two equations. Find
// v_x(t+h,xappr,yappr), v_y(t+h,xappr,yappr) by interpolation.
fx = xappr-0.5*h*intpol(gridvx,*xappr,*yappr)-x[j][k]-0.5*hvx[j][k];
fy = yappr-0.5*h*intpol(gridvy,*xappr,*yappr)-y[j][k]-0.5*hvy[j][k];
// Linearly approximate the partial derivatives of fx, fy with a finite
// difference method. More elaborate techniques are possible, but this
// quick and dirty method appears to work reasonably for our purpose.
gaussx = (int)(*xappr);
gaussy = (int)(*yappr);
if (gaussx == lx) gaussxplus = 0;
else gaussxplus = gaussx+1;
if (gaussy == ly) gaussyplus = 0;
else gaussyplus = gaussy+1;
deltax = x[j][k] - gaussx;
deltay = y[j][k] - gaussy;
dfxdx = 1 - 0.5h
((1-deltay)*(gridvx[gaussxplus][gaussy]-gridvx[gaussx][gaussy])+
deltay*(gridvx[gaussxplus][gaussyplus]-gridvx[gaussx][gaussyplus]));
dfxdy = -0.5h
((1-deltax)*(gridvx[gaussx][gaussyplus]-gridvx[gaussx][gaussy])+
deltax*(gridvx[gaussxplus][gaussyplus]-gridvx[gaussxplus][gaussy]));
dfydx = -0.5h
((1-deltay)*(gridvy[gaussxplus][gaussy]-gridvy[gaussx][gaussy])+
deltay*(gridvy[gaussxplus][gaussyplus]-gridvy[gaussx][gaussyplus]));
dfydy = 1 - 0.5h
((1-deltax)*(gridvy[gaussx][gaussyplus]-gridvy[gaussx][gaussy])+
deltax*(gridvy[gaussxplus][gaussyplus]-gridvy[gaussxplus][gaussy]));
// If the current approximation is (xappr,yappr) for the zero of
// (fx(x,y),fy(x,y)) and J is the Jacobian, then we can approximate (in
// vector notation) for |delta|<<1:
// f((xappr,yappr)+delta) = f(xappr,yappr)+J*delta.
// Setting f((xappr,yappr)+delta)=0 we obtain a set of linear equations
// for the correction delta which moves f closer to zero, namely
// J*delta = -f.
// The improved approximation is then x = xappr+delta.
// The process will be iterated until convergence is reached.
if ((fx*fx + fy*fy) < TOLF) return TRUE;
deltax = (fy*dfxdy - fxdfydy)/(dfxdxdfydy - dfxdy*dfydx);
deltay = (fx*dfydx - fydfxdx)/(dfxdxdfydy - dfxdy*dfydx);
if ((deltax*deltax + deltay*deltay) < TOLX) return TRUE;
*xappr += deltax;
*yappr += deltay;
//printf("deltax %f, deltay %f\n",deltax,deltay);
}
fprintf(stderr,"newt2 failed, increasing sigma to %f.\n",
SIGMA*pow(SIGMAFAC,nblurs));
return FALSE;
}
// Function to integrate the nonlinear Volterra equation. Returns TRUE after
// the displacement field converged, after MAXINTSTEPS integration steps, or
// if the time exceeds TIMELIMIT.
BOOLEAN nonlinvoltra(void)
{
BOOLEAN stepsize_ok;
#ifdef DISPLFILE
FILE *displfile = fopen(DISPLFILE);
#endif
float h,maxchange=INFTY,t,vxplus,vyplus,xguess,yguess;
int i,j,k;
do
{
initcond();
nblurs++;
if (minpop<0.0)
fprintf(stderr,
"Minimum population negative, will increase sigma to %f\n",
SIGMA*pow(SIGMAFAC,nblurs));
}
while (minpop<0.0);
h = HINITIAL;
t = 0; // Start at time t=0.
// (x[j][k],y[j][k]) is the position for the element that was at position
// (j,k) at time t=0.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
x[j][k] = j;
y[j][k] = k;
}
calcv(0.0);
// (gridvx[j][k],gridvy[j][k]) is the velocity at position (j,k).
// (vx[j][k],vy[j][k]) is the velocity at position (x[j][k],y[j][k]).
// At t=0 they are of course identical.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
vx[j][k] = gridvx[j][k];
vy[j][k] = gridvy[j][k];
}
i = 1; // i counts the integration steps.
// Here is the integrator.
do
{
stepsize_ok = TRUE;
calcv(t+h);
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
// First take a naive integration step. The velocity at time t+h for
// the element [j][k] is approximately
// v(th,x[j][k]+hvx[j][k],y[j][k]hvy[j][k]).
// The components, call them vxplus and vyplus, are interpolated from
// gridvx and gridvy.
vxplus = intpol(gridvx,x[j][k]hvx[j][k],y[j][k]hvy[j][k]);
vyplus = intpol(gridvy,x[j][k]hvx[j][k],y[j][k]hvy[j][k]);
// Based on (vx[j][k],vy[j][k]) and (vxplus,vyplus) we expect the
// new position at time t+h to be:
xguess = x[j][k] + 0.5h(vx[j][k]+vxplus);
yguess = y[j][k] + 0.5h(vy[j][k]+vyplus);
// Then we make a better approximation by solving the two nonlinear
// equations:
// xappr[j][k]-0.5hv_x(t+h,xappr[j][k],yappr[j][k])-
// x[j][k]-0.5hvx[j][k]=0,
// yappr[j][k]-0.5hv_y(t+h,xappr[j][k],yappr[j][k])-
// y[j][k]-0.5hvy[j][k]=0
// with Newton-Raphson and (xguess,yguess) as initial guess.
// If newt2 fails to converge, exit nonlinvoltra.
if (!newt2(h,&xappr[j][k],xguess,&yappr[j][k],yguess,j,k))
return FALSE;
// If the integration step was too large reduce the step size.
if ((xguess-xappr[j][k])*(xguess-xappr[j][k])+
(yguess-yappr[j][k])*(yguess-yappr[j][k]) > TOLINT)
{
if (h<MINH)
{
fprintf(stderr,
"Time step below %f, increasing SIGMA to %f\n",
h,SIGMA*pow(SIGMAFAC,nblurs));
nblurs++;
return FALSE;
}
h /= 10;
stepsize_ok = FALSE;
break;
}
}
if (!stepsize_ok) continue;
else
{
t += h;
maxchange = 0.0; // Monitor the maximum change in positions.
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
{
if ((x[j][k]-xappr[j][k])*(x[j][k]-xappr[j][k])+
(y[j][k]-yappr[j][k])*(y[j][k]-yappr[j][k]) > maxchange)
maxchange =
(x[j][k]-xappr[j][k])*(x[j][k]-xappr[j][k])+
(y[j][k]-yappr[j][k])*(y[j][k]-yappr[j][k]);
x[j][k] = xappr[j][k];
y[j][k] = yappr[j][k];
vx[j][k] = intpol(gridvx,xappr[j][k],yappr[j][k]);
vy[j][k] = intpol(gridvy,xappr[j][k],yappr[j][k]);
}
}
h *= 1.2; // Make the next integration step larger.
if (i%10==0) printf("time %f\n",t);
i++;
} while (i<MAXINTSTEPS && t<TIMELIMIT && maxchange>CONVERGENCE);
if (maxchange>CONVERGENCE)
fprintf(stderr,
"WARNING: Insufficient convergence within %i steps, time %f.\n",
MAXINTSTEPS,TIMELIMIT);
#ifdef DISPLFILE
// Write displacement field to file.
fprintf(displfile,"time %f\nminx %f\nmaxx %f\nminy %f\nmaxy %f\n",
t,minx,maxx,miny,maxy);
fprintf(displfile,"sigma %f\n",SIGMA*pow(SIGMAFAC,nblurs-1));
fprintf(displfile,"background %f\nlx\nly\n\n",0,lx,ly);
for (j=0; j<=lx; j++) for (k=0; k<=ly; k++)
fprintf(displfile,"j %i, k %i, x %f, y %f\n",j,k,x[j][k],y[j][k]);
fclose(displfile);
#endif
return TRUE;
}
// Function to transform points according to displacement field.
POINT transf(POINT p)
{
float deltax,deltay,den,t,u;
int gaussx,gaussy;
POINT a,b,c,d,ptr;
p.x = (p.x-minx)*lx/(maxx-minx);
p.y = (p.y-miny)*ly/(maxy-miny);
gaussx = (int)p.x;
gaussy = (int)p.y;
if (gaussx<0 || gaussx>lx || gaussy<0 || gaussy>ly)
{
fprintf(stderr,"ERROR: Coordinate limits exceeded in transf.\n");
exit(1);
}
deltax = p.x - gaussx;
deltay = p.y - gaussy;
// The transformed point is the intersection of the lines:
// (I) connecting
// (1-deltax)(x,y[gaussx][gaussy])deltax(x,y[gaussx1][gaussy])
// and
// (1-deltax)(x,y[gaussx][gaussy1])+deltax(x,y[gaussx+1][gaussy1])
// (II) connecting
// (1-deltay)(x,y[gaussx][gaussy])deltay(x,y[gaussx][gaussy1])
// and
// (1-deltay)(x,y[gaussx1][gaussy])+deltay(x,y[gaussx+1][gaussy1]).
// Call these four points a, b, c and d.
a.x = (1-deltax)*x[gaussx][gaussy] + deltax*x[gaussx+1][gaussy];
a.y = (1-deltax)*y[gaussx][gaussy] + deltax*y[gaussx+1][gaussy];
b.x = (1-deltax)*x[gaussx][gaussy+1] + deltax*x[gaussx1][gaussy1];
b.y = (1-deltax)*y[gaussx][gaussy+1] + deltax*y[gaussx1][gaussy1];
c.x = (1-deltay)*x[gaussx][gaussy] + deltay*x[gaussx][gaussy+1];
c.y = (1-deltay)*y[gaussx][gaussy] + deltay*y[gaussx][gaussy+1];
d.x = (1-deltay)*x[gaussx+1][gaussy] + deltay*x[gaussx1][gaussy1];
d.y = (1-deltay)*y[gaussx+1][gaussy] + deltay*y[gaussx1][gaussy1];
// Solve the vector equation a+t(b-a) = c+u(d-c) for the scalars t, u.
if (fabs(den=(b.x-a.x)(c.y-d.y)+(a.y-b.y)(c.x-d.x))<1e-12)
{
fprintf(stderr,"ERROR: Transformed area element has parallel edges.\n");
exit(1);
}
t = ((c.x-a.x)(c.y-d.y)+(a.y-c.y)(c.x-d.x))/den;
u = ((b.x-a.x)(c.y-a.y)+(a.y-b.y)(c.x-a.x))/den;
if (t<-1e-3|| t>1+1e-3 || u<-1e-3 || u>1+1e-3)
fprintf(stderr,"WARNING: Transformed area element non-convex.\n");
ptr.x = (1-(a.x+t(b.x-a.x))/lx)minx + ((a.x+t(b.x-a.x))/lx)maxx;
ptr.y = (1-(a.y+t(b.y-a.y))/ly)miny + ((a.y+t(b.y-a.y))/ly)maxy;
return ptr;
}
// Function to read spatial features from user-specified file and map to
// cartogram.
void cartogram(void)
{
char id[LINELENGTH],line[LINELENGTH];
FILE infile,outfile;
float xcoord,ycoord;
POINT p;
infile = fopen(MAPGENFILE);
outfile = fopen(CARTGENFILE,"w");
while (!readline(line,infile))
{
if (sscanf(line,"%s %f %f",&id,&xcoord,&ycoord)==3)
{
p.x = xcoord;
p.y = ycoord;
p = transf(p);
fprintf(outfile,"%s %f %f\n",id,p.x,p.y);
}
else if (sscanf(line,"%f %f",&xcoord,&ycoord)==2)
{
p.x = xcoord;
p.y = ycoord;
p = transf(p);
fprintf(outfile,"%f %f\n",p.x,p.y);
}
else
{
sscanf(line,"%s",&id);
fprintf(outfile,"%s\n",id);
}
}
fclose(infile);
fclose(outfile);
}
main(void)
{
BOOLEAN n;
char c;
FILE genfile,psfile = fopen(MAP2PS);
float oldlx,oldly,oldmaxx,oldmaxy,oldminx,oldminy,totarea;
int i,polyctr,regctr;
// Read the polygon coordinates.
if ((genfile = fopen(MAPGENFILE)) == NULL)
{
fprintf(stderr,"ERROR: Cannot find MAPGENFILE\n");
exit(1);
}
countpoly(genfile);
fclose(genfile);
genfile = fopen(MAPGENFILE);
countcorn(genfile);
fclose(genfile);
genfile = fopen(MAPGENFILE);
readcorn(genfile);
fclose(genfile);
makeregion();
printf("%i polygon(s), %i region(s)\n",npoly,nregion);
printf("lx=%i, ly=%i\n",lx,ly);
// Calculate total area.
//totarea = 0.0;
//for (regctr=0; regctr<nregion; regctr++)
//{
// printf("region %i has area %f, contains %i polygons\n",regionid[regctr],
// regionarea(nregcorn[regctr],regcorn[regctr]),npolyinreg[regctr]);
// totarea += regionarea(nregcorn[regctr],regcorn[regctr]);
//}
//printf("totarea = %f\n",totarea);
// Make map.
pspicture(psfile);
fclose(psfile);
// Allocate memory for arrays.
gridvx = (float*)malloc((lx+1)*sizeof(float));
gridvy = (float*)malloc((lx+1)*sizeof(float));
rho = (float*)malloc((lx+1)*sizeof(float));
rho_0 = (float*)malloc((lx+1)*sizeof(float));
vx = (float*)malloc((lx+1)*sizeof(float));
vy = (float*)malloc((lx+1)*sizeof(float));
x = (float*)malloc((lx+1)*sizeof(float));
xappr = (float*)malloc((lx+1)*sizeof(float));
y = (float*)malloc((lx+1)*sizeof(float));
yappr = (float*)malloc((lx+1)*sizeof(float));
within = (int*)malloc((lx+1)*sizeof(int));
for (i=0; i<=lx; i++)
{
gridvx = (float)malloc((ly+1)sizeof(float));
gridvy = (float)malloc((ly+1)sizeof(float));
rho = (float)malloc((ly+1)sizeof(float));
rho_0 = (float)malloc((ly+1)sizeof(float));
vx = (float)malloc((ly+1)sizeof(float));
vy = (float)malloc((ly+1)sizeof(float));
x = (float)malloc((ly+1)sizeof(float));
xappr = (float)malloc((ly+1)sizeof(float));
y = (float)malloc((ly+1)sizeof(float));
yappr = (float)malloc((ly+1)sizeof(float));
within = (int)malloc((ly+1)sizeof(int));
}
// Digitize the density.
bboxes();
interior();
digdens();
// Solve the diffusion equation.
do n = nonlinvoltra(); while (!n);
// Print cartogram generate file.
cartogram();
// Read the transformed polygon coordinates.
oldlx = lx;
oldly = ly;
oldmaxx = maxx;
oldmaxy = maxy;
oldminx = minx;
oldminy = miny;
genfile = fopen(CARTGENFILE,"r");
countpoly(genfile);
fclose(genfile);
genfile = fopen(CARTGENFILE,"r");
countcorn(genfile);
fclose(genfile);
lx = oldlx;
ly = oldly;
maxx = oldmaxx;
maxy = oldmaxy;
minx = oldminx;
miny = oldminy;
genfile = fopen(CARTGENFILE,"r");
readcorn(genfile);
fclose(genfile);
makeregion();
// Make cartogram
psfile = fopen(CART2PS);
pspicture(psfile);
fclose(psfile);
}
The part of the code where the bus error occurs is this:
void interior(void)
{
int i,inhowmanyregions,inregion[2],j,k,l,m,n,regctr;
// Initialize within[][]. -1 means outside all regions.
for (i=0; i<=lx; i++) for (j=0; j<=ly; j++) within[j] = -1;
// Fill within[][].
for (i=0; i<nregion; i++) for (j=0; j<npolyinreg; j++)
for (k=0, n=npolycorn[polyinreg[j]]-1;
k<npolycorn[polyinreg[j]]; n=k++)
for (l=(int)ceil(MIN(polycorn[polyinreg[j]][k-1].y,
polycorn[polyinreg[j]][k].y));
l<MAX(polycorn[polyinreg[j]][k-1].y,
polycorn[polyinreg[j]][k].y); l++)
for (m=(int)floor(bbminx[polyinreg[j]]);
m<(polycorn[polyinreg[j]][n].x-
polycorn[polyinreg[j]][k].x)*
(l-polycorn[polyinreg[j]][k].y)/
(polycorn[polyinreg[j]][n].y-
polycorn[polyinreg[j]][k].y)+
polycorn[polyinreg[j]][k].x;
m++)
within[m][l] = i-within[m][l]-1;
}
I really have no idea what is going on. Can anyone help?
Thanks,
mooseguy