PostGIS  2.4.9dev-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 234 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().

235 {
236  LWDEBUG(2, "Entered tune_areas");
237  const double *P1;
238  const double *P2;
239  const double *P3;
240  double area;
241  int go_on=1;
242  double check_order_min_area = 0;
244  int npoints=ea->inpts->npoints;
245  int i;
246  int current, before_current, after_current;
248  MINHEAP tree = initiate_minheap(npoints);
250  int is3d = FLAGS_GET_Z(ea->inpts->flags);
253  /*Add all keys (index in initial_arealist) into minheap array*/
254  for (i=0;i<npoints;i++)
255  {
256  tree.key_array[i]=ea->initial_arealist+i;
257  LWDEBUGF(2, "add nr %d, with area %lf, and %lf",i,ea->initial_arealist[i].area, tree.key_array[i]->area );
258  }
259  tree.usedSize=npoints;
261  /*order the keys by area, small to big*/
262  qsort(tree.key_array, npoints, sizeof(void*), cmpfunc);
264  /*We have to put references to our tree in our point-list*/
265  for (i=0;i<npoints;i++)
266  {
267  ((areanode*) tree.key_array[i])->treeindex=i;
268  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);
269  }
270  /*Ok, now we have a minHeap, just need to keep it*/
272  /*for (i=0;i<npoints-1;i++)*/
273  i=0;
274  while (go_on)
275  {
276  /*Get a reference to the point with the currently smallest effective area*/
277  current=minheap_pop(&tree, ea->initial_arealist)-ea->initial_arealist;
279  /*We have found the smallest area. That is the resulting effective area for the "current" point*/
280  if (i<npoints-avoid_collaps)
281  ea->res_arealist[current]=ea->initial_arealist[current].area;
282  else
283  ea->res_arealist[current]=FLT_MAX;
285  if(ea->res_arealist[current]<check_order_min_area)
286  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);
288  check_order_min_area=ea->res_arealist[current];
290  /*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*/
292  /*FInd point before and after*/
293  before_current=ea->initial_arealist[current].prev;
294  after_current=ea->initial_arealist[current].next;
296  P2= (double*)getPoint_internal(ea->inpts, before_current);
297  P3= (double*)getPoint_internal(ea->inpts, after_current);
299  /*Check if point before current point is the first in the point array. */
300  if(before_current>0)
301  {
303  P1= (double*)getPoint_internal(ea->inpts, ea->initial_arealist[before_current].prev);
304  if(is3d)
305  area=triarea3d(P1, P2, P3);
306  else
307  area=triarea2d(P1, P2, P3);
309  ea->initial_arealist[before_current].area = FP_MAX(area,ea->res_arealist[current]);
310  minheap_update(&tree, ea->initial_arealist, ea->initial_arealist[before_current].treeindex);
311  }
312  if(after_current<npoints-1)/*Check if point after current point is the last in the point array. */
313  {
314  P1=P2;
315  P2=P3;
317  P3= (double*)getPoint_internal(ea->inpts, ea->initial_arealist[after_current].next);
320  if(is3d)
321  area=triarea3d(P1, P2, P3);
322  else
323  area=triarea2d(P1, P2, P3);
326  ea->initial_arealist[after_current].area = FP_MAX(area,ea->res_arealist[current]);
327  minheap_update(&tree, ea->initial_arealist, ea->initial_arealist[after_current].treeindex);
328  }
330  /*rearrange the nodes so the eliminated point will be ingored on the next run*/
331  ea->initial_arealist[before_current].next = ea->initial_arealist[current].next;
332  ea->initial_arealist[after_current].prev = ea->initial_arealist[current].prev;
334  /*Check if we are finnished*/
335  if((!set_area && ea->res_arealist[current]>trshld) || (ea->initial_arealist[0].next==(npoints-1)))
336  go_on=0;
338  i++;
339  };
340  destroy_minheap(tree);
341  return;
342 }
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...
static double triarea3d(const double *P1, const double *P2, const double *P3)
Calculate the area of a triangle in 3d space.
Definition: effectivearea.c:81
This structure is placed in an array with one member per point.
Definition: effectivearea.h:38
static void destroy_minheap(MINHEAP tree)
Definition: effectivearea.c:62
int npoints
Definition: liblwgeom.h:371
This structure holds a minheap tree that is used to keep track of what points that has the smallest e...
Definition: effectivearea.h:52
static MINHEAP initiate_minheap(int npoints)
Definition: effectivearea.c:51
double area
Definition: effectivearea.h:40
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
static double triarea2d(const double *P1, const double *P2, const double *P3)
Calculate the area of a triangle in 2d.
Definition: effectivearea.c:72
const POINTARRAY * inpts
Definition: effectivearea.h:66
uint8_t flags
Definition: liblwgeom.h:369
uint8_t * getPoint_internal(const POINTARRAY *pa, int n)
Definition: ptarray.c:1753
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:140
double * res_arealist
Definition: effectivearea.h:68
int treeindex
Definition: effectivearea.h:41
int usedSize
Definition: effectivearea.h:55
areanode ** key_array
Definition: effectivearea.h:56
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:88
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
#define FP_MAX(A, B)
areanode * initial_arealist
Definition: effectivearea.h:67
Here is the call graph for this function:
Here is the caller graph for this function: