PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ FindPolygons()

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

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

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().

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