PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ FindPolygons()

int FindPolygons ( SHPObject obj,
Ring ***  Out 
)

Definition at line 437 of file shp2pgsql-core.c.

438 {
439  Ring **Outer; /* Pointers to Outer rings */
440  int out_index=0; /* Count of Outer rings */
441  Ring **Inner; /* Pointers to Inner rings */
442  int in_index=0; /* Count of Inner rings */
443  int pi; /* part index */
444 
445 #if POSTGIS_DEBUG_LEVEL > 0
446  static int call = -1;
447  call++;
448 #endif
449 
450  LWDEBUGF(4, "FindPolygons[%d]: allocated space for %d rings\n", call, obj->nParts);
451 
452  /* Allocate initial memory */
453  Outer = (Ring **)malloc(sizeof(Ring *) * obj->nParts);
454  Inner = (Ring **)malloc(sizeof(Ring *) * obj->nParts);
455 
456  /* Iterate over rings dividing in Outers and Inners */
457  for (pi=0; pi < obj->nParts; pi++)
458  {
459  int vi; /* vertex index */
460  int vs; /* start index */
461  int ve; /* end index */
462  int nv; /* number of vertex */
463  double area = 0.0;
464  Ring *ring;
465 
466  /* Set start and end vertexes */
467  if (pi == obj->nParts - 1)
468  ve = obj->nVertices;
469  else
470  ve = obj->panPartStart[pi + 1];
471 
472  vs = obj->panPartStart[pi];
473 
474  /* Compute number of vertexes */
475  nv = ve - vs;
476 
477  /* Allocate memory for a ring */
478  ring = (Ring *)malloc(sizeof(Ring));
479  ring->list = (Point *)malloc(sizeof(Point) * nv);
480  ring->n = nv;
481  ring->next = NULL;
482  ring->linked = 0;
483 
484  /* Iterate over ring vertexes */
485  for (vi = vs; vi < ve; vi++)
486  {
487  int vn = vi+1; /* next vertex for area */
488  if (vn == ve)
489  vn = vs;
490 
491  ring->list[vi - vs].x = obj->padfX[vi];
492  ring->list[vi - vs].y = obj->padfY[vi];
493  ring->list[vi - vs].z = obj->padfZ[vi];
494  ring->list[vi - vs].m = obj->padfM[vi];
495 
496  area += (obj->padfX[vi] * obj->padfY[vn]) -
497  (obj->padfY[vi] * obj->padfX[vn]);
498  }
499 
500  /* Close the ring with first vertex */
501  /*ring->list[vi].x = obj->padfX[vs]; */
502  /*ring->list[vi].y = obj->padfY[vs]; */
503  /*ring->list[vi].z = obj->padfZ[vs]; */
504  /*ring->list[vi].m = obj->padfM[vs]; */
505 
506  /* Clockwise (or single-part). It's an Outer Ring ! */
507  if (area < 0.0 || obj->nParts == 1)
508  {
509  Outer[out_index] = ring;
510  out_index++;
511  }
512  else
513  {
514  /* Counterclockwise. It's an Inner Ring ! */
515  Inner[in_index] = ring;
516  in_index++;
517  }
518  }
519 
520  LWDEBUGF(4, "FindPolygons[%d]: found %d Outer, %d Inners\n", call, out_index, in_index);
521 
522  /* Put the inner rings into the list of the outer rings */
523  /* of which they are within */
524  for (pi = 0; pi < in_index; pi++)
525  {
526  Point pt, pt2;
527  int i;
528  Ring *inner = Inner[pi], *outer = NULL;
529 
530  pt.x = inner->list[0].x;
531  pt.y = inner->list[0].y;
532 
533  pt2.x = inner->list[1].x;
534  pt2.y = inner->list[1].y;
535 
536  /*
537  * If we assume that the case of the "big polygon w/o hole
538  * containing little polygon w/ hold" is ordered so that the
539  * big polygon comes first, then checking the list in reverse
540  * will assign the little polygon's hole to the little polygon
541  * w/o a lot of extra fancy containment logic here
542  */
543  for (i = out_index - 1; i >= 0; i--)
544  {
545  int in;
546 
547  in = PIP(pt, Outer[i]->list, Outer[i]->n);
548  if ( in || PIP(pt2, Outer[i]->list, Outer[i]->n) )
549  {
550  outer = Outer[i];
551  break;
552  }
553  }
554 
555  if (outer)
556  {
557  outer->linked++;
558  while (outer->next)
559  outer = outer->next;
560 
561  outer->next = inner;
562  }
563  else
564  {
565  /* The ring wasn't within any outer rings, */
566  /* assume it is a new outer ring. */
567  LWDEBUGF(4, "FindPolygons[%d]: hole %d is orphan\n", call, pi);
568 
569  Outer[out_index] = inner;
570  out_index++;
571  }
572  }
573 
574  *Out = Outer;
575  /*
576  * Only free the containing Inner array, not the ring elements, because
577  * the rings are now owned by the linked lists in the Outer array elements.
578  */
579  free(Inner);
580 
581  return out_index;
582 }
Datum area(PG_FUNCTION_ARGS)
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
void * malloc(YYSIZE_T)
void free(void *)
int PIP(Point P, Point *V, int n)
PIP(): crossing number test for a point in a polygon input: P = a point, V[] = vertex points of a pol...
int * panPartStart
Definition: shapefil.h:345
int nVertices
Definition: shapefil.h:348
double * padfZ
Definition: shapefil.h:351
double * padfX
Definition: shapefil.h:349
int nParts
Definition: shapefil.h:344
double * padfM
Definition: shapefil.h:352
double * padfY
Definition: shapefil.h:350
Point * list
unsigned int linked
struct struct_ring * next

References area(), free(), struct_ring::linked, struct_ring::list, LWDEBUGF, struct_point::m, malloc(), struct_ring::n, struct_ring::next, SHPObject::nParts, SHPObject::nVertices, SHPObject::padfM, SHPObject::padfX, SHPObject::padfY, SHPObject::padfZ, SHPObject::panPartStart, PIP(), struct_point::x, struct_point::y, and struct_point::z.

Referenced by GeneratePolygonGeometry().

Here is the call graph for this function:
Here is the caller graph for this function: