PostGIS  2.2.8dev-r@@SVN_REVISION@@

◆ tune_areas()

static void tune_areas ( EFFECTIVE_AREAS ea,
int  avoid_collaps,
int  set_area,
double  trshld 

To get the effective area, we have to check what area a point results in when all smaller areas are eliminated.

Definition at line 220 of file effectivearea.c.

References areanode::area, area(), cmpfunc(), destroy_minheap(), POINTARRAY::flags, FLAGS_GET_Z, FP_MAX, getPoint_internal(), EFFECTIVE_AREAS::initial_arealist, initiate_minheap(), EFFECTIVE_AREAS::inpts, MINHEAP::key_array, LWDEBUG, LWDEBUGF, lwerror(), minheap_pop(), minheap_update(), areanode::next, POINTARRAY::npoints, areanode::prev, EFFECTIVE_AREAS::res_arealist, areanode::treeindex, triarea2d(), triarea3d(), and MINHEAP::usedSize.

Referenced by ptarray_calc_areas().

221 {
222  LWDEBUG(2, "Entered tune_areas");
223  const double *P1;
224  const double *P2;
225  const double *P3;
226  double area;
227  int go_on=1;
228  double check_order_min_area = 0;
230  int npoints=ea->inpts->npoints;
231  int i;
232  int current, before_current, after_current;
234  MINHEAP tree = initiate_minheap(npoints);
236  int is3d = FLAGS_GET_Z(ea->inpts->flags);
239  /*Add all keys (index in initial_arealist) into minheap array*/
240  for (i=0;i<npoints;i++)
241  {
242  tree.key_array[i]=ea->initial_arealist+i;
243  LWDEBUGF(2, "add nr %d, with area %lf, and %lf",i,ea->initial_arealist[i].area, tree.key_array[i]->area );
244  }
245  tree.usedSize=npoints;
247  /*order the keys by area, small to big*/
248  qsort(tree.key_array, npoints, sizeof(void*), cmpfunc);
250  /*We have to put references to our tree in our point-list*/
251  for (i=0;i<npoints;i++)
252  {
253  ((areanode*) tree.key_array[i])->treeindex=i;
254  LWDEBUGF(4,"Check ordering qsort gives, area=%lf and belong to point %d",((areanode*) tree.key_array[i])->area, tree.key_array[i]-ea->initial_arealist);
255  }
256  /*Ok, now we have a minHeap, just need to keep it*/
258  /*for (i=0;i<npoints-1;i++)*/
259  i=0;
260  while (go_on)
261  {
262  /*Get a reference to the point with the currently smallest effective area*/
263  current=minheap_pop(&tree, ea->initial_arealist)-ea->initial_arealist;
265  /*We have found the smallest area. That is the resulting effective area for the "current" point*/
266  if (i<npoints-avoid_collaps)
267  ea->res_arealist[current]=ea->initial_arealist[current].area;
268  else
269  ea->res_arealist[current]=FLT_MAX;
271  if(ea->res_arealist[current]<check_order_min_area)
272  lwerror("Oh no, this is a bug. For some reason the minHeap returned our points in the wrong order. Please file a ticket in PostGIS ticket system, or send a mial at the mailing list.Returned area = %lf, and last area = %lf",ea->res_arealist[current],check_order_min_area);
274  check_order_min_area=ea->res_arealist[current];
276  /*The found smallest area point is now regarded as elimnated and we have to recalculate the area the adjacent (ignoring earlier elimnated points) points gives*/
278  /*FInd point before and after*/
279  before_current=ea->initial_arealist[current].prev;
280  after_current=ea->initial_arealist[current].next;
282  P2= (double*)getPoint_internal(ea->inpts, before_current);
283  P3= (double*)getPoint_internal(ea->inpts, after_current);
285  /*Check if point before current point is the first in the point array. */
286  if(before_current>0)
287  {
289  P1= (double*)getPoint_internal(ea->inpts, ea->initial_arealist[before_current].prev);
290  if(is3d)
291  area=triarea3d(P1, P2, P3);
292  else
293  area=triarea2d(P1, P2, P3);
295  ea->initial_arealist[before_current].area = FP_MAX(area,ea->res_arealist[current]);
296  minheap_update(&tree, ea->initial_arealist, ea->initial_arealist[before_current].treeindex);
297  }
298  if(after_current<npoints-1)/*Check if point after current point is the last in the point array. */
299  {
300  P1=P2;
301  P2=P3;
303  P3= (double*)getPoint_internal(ea->inpts, ea->initial_arealist[after_current].next);
306  if(is3d)
307  area=triarea3d(P1, P2, P3);
308  else
309  area=triarea2d(P1, P2, P3);
312  ea->initial_arealist[after_current].area = FP_MAX(area,ea->res_arealist[current]);
313  minheap_update(&tree, ea->initial_arealist, ea->initial_arealist[after_current].treeindex);
314  }
316  /*rearrange the nodes so the eliminated point will be ingored on the next run*/
317  ea->initial_arealist[before_current].next = ea->initial_arealist[current].next;
318  ea->initial_arealist[after_current].prev = ea->initial_arealist[current].prev;
320  /*Check if we are finnished*/
321  if((!set_area && ea->res_arealist[current]>trshld) || (ea->initial_arealist[0].next==(npoints-1)))
322  go_on=0;
324  i++;
325  };
326  destroy_minheap(tree);
327  return;
328 }
static int cmpfunc(const void *a, const void *b)
We create the minheap by ordering the minheap array by the areas in the areanode structs that the min...
Definition: effectivearea.c:91
static double triarea3d(const double *P1, const double *P2, const double *P3)
Calculate the area of a triangle in 3d space.
Definition: effectivearea.c:67
This structure is placed in an array with one member per point.
Definition: effectivearea.h:24
static void destroy_minheap(MINHEAP tree)
Definition: effectivearea.c:48
int npoints
Definition: liblwgeom.h:355
This structure holds a minheap tree that is used to keep track of what points that has the smallest e...
Definition: effectivearea.h:38
static MINHEAP initiate_minheap(int npoints)
Definition: effectivearea.c:37
double area
Definition: effectivearea.h:26
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
static double triarea2d(const double *P1, const double *P2, const double *P3)
Calculate the area of a triangle in 2d.
Definition: effectivearea.c:58
const POINTARRAY * inpts
Definition: effectivearea.h:52
uint8_t flags
Definition: liblwgeom.h:353
uint8_t * getPoint_internal(const POINTARRAY *pa, int n)
Definition: ptarray.c:1706
static void minheap_update(MINHEAP *tree, areanode *arealist, int idx)
The member of the minheap at index idx is changed.
#define FLAGS_GET_Z(flags)
Macros for manipulating the &#39;flags&#39; byte.
Definition: liblwgeom.h:124
double * res_arealist
Definition: effectivearea.h:54
int treeindex
Definition: effectivearea.h:27
int usedSize
Definition: effectivearea.h:41
areanode ** key_array
Definition: effectivearea.h:42
static areanode * minheap_pop(MINHEAP *tree, areanode *arealist)
Get a reference to the point with the smallest effective area from the root of the min heap...
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
#define FP_MAX(A, B)
areanode * initial_arealist
Definition: effectivearea.h:53
Here is the call graph for this function:
Here is the caller graph for this function: