PostGIS  2.2.8dev-r@@SVN_REVISION@@

◆ lwgeom_subdivide_recursive()

static int lwgeom_subdivide_recursive ( const LWGEOM geom,
int  maxvertices,
int  depth,
LWCOLLECTION col,
const GBOX clip 
)
static

Definition at line 1899 of file lwgeom.c.

References FP_TOLERANCE, LWCOLLECTION::geoms, lwcollection_add_lwgeom(), lwerror(), lwgeom_clip_by_rect(), lwgeom_clone_deep(), lwgeom_count_vertices(), lwgeom_free(), lwgeom_is_collection(), lwtype_name(), MULTIPOINTTYPE, LWCOLLECTION::ngeoms, POINTTYPE, POLYHEDRALSURFACETYPE, TINTYPE, LWGEOM::type, GBOX::xmax, GBOX::xmin, GBOX::ymax, and GBOX::ymin.

Referenced by lwgeom_grid(), and lwgeom_subdivide().

1900 {
1901  const int maxdepth = 50;
1902  int nvertices = 0;
1903  int i, n = 0;
1904  double width = clip->xmax - clip->xmin;
1905  double height = clip->ymax - clip->ymin;
1906  GBOX subbox1, subbox2;
1907  LWGEOM *clipped1, *clipped2;
1908 
1909  if ( geom->type == POLYHEDRALSURFACETYPE || geom->type == TINTYPE )
1910  {
1911  lwerror("%s: unsupported geometry type '%s'", __func__, lwtype_name(geom->type));
1912  }
1913 
1914  if ( width == 0.0 && height == 0.0 )
1915  {
1916  if ( geom->type == POINTTYPE )
1917  {
1919  return 1;
1920  }
1921  else
1922  {
1923  return 0;
1924  }
1925  }
1926 
1927  /* Always just recurse into collections */
1928  if ( lwgeom_is_collection(geom) && geom->type != MULTIPOINTTYPE )
1929  {
1930  LWCOLLECTION *incol = (LWCOLLECTION*)geom;
1931  int n = 0;
1932  for ( i = 0; i < incol->ngeoms; i++ )
1933  {
1934  /* Don't increment depth yet, since we aren't actually subdividing geomtries yet */
1935  n += lwgeom_subdivide_recursive(incol->geoms[i], maxvertices, depth, col, clip);
1936  }
1937  return n;
1938  }
1939 
1940  /* But don't go too far. 2^25 = 33M, that's enough subdivision */
1941  /* Signal callers above that we depth'ed out with a negative */
1942  /* return value */
1943  if ( depth > maxdepth )
1944  {
1945  return 0;
1946  }
1947 
1948  nvertices = lwgeom_count_vertices(geom);
1949  /* Skip empties entirely */
1950  if ( nvertices == 0 )
1951  {
1952  return 0;
1953  }
1954 
1955  /* If it is under the vertex tolerance, just add it, we're done */
1956  if ( nvertices < maxvertices )
1957  {
1959  return 1;
1960  }
1961 
1962  subbox1 = subbox2 = *clip;
1963  if ( width > height )
1964  {
1965  subbox1.xmax = subbox2.xmin = (clip->xmin + clip->xmax)/2;
1966  }
1967  else
1968  {
1969  subbox1.ymax = subbox2.ymin = (clip->ymin + clip->ymax)/2;
1970  }
1971 
1972  if ( height == 0 )
1973  {
1974  subbox1.ymax += FP_TOLERANCE;
1975  subbox2.ymax += FP_TOLERANCE;
1976  subbox1.ymin -= FP_TOLERANCE;
1977  subbox2.ymin -= FP_TOLERANCE;
1978  }
1979 
1980  if ( width == 0 )
1981  {
1982  subbox1.xmax += FP_TOLERANCE;
1983  subbox2.xmax += FP_TOLERANCE;
1984  subbox1.xmin -= FP_TOLERANCE;
1985  subbox2.xmin -= FP_TOLERANCE;
1986  }
1987 
1988  clipped1 = lwgeom_clip_by_rect(geom, subbox1.xmin, subbox1.ymin, subbox1.xmax, subbox1.ymax);
1989  clipped2 = lwgeom_clip_by_rect(geom, subbox2.xmin, subbox2.ymin, subbox2.xmax, subbox2.ymax);
1990 
1991  if ( clipped1 )
1992  {
1993  n += lwgeom_subdivide_recursive(clipped1, maxvertices, ++depth, col, &subbox1);
1994  lwgeom_free(clipped1);
1995  }
1996 
1997  if ( clipped2 )
1998  {
1999  n += lwgeom_subdivide_recursive(clipped2, maxvertices, ++depth, col, &subbox2);
2000  lwgeom_free(clipped2);
2001  }
2002 
2003  return n;
2004 
2005 }
double xmax
Definition: liblwgeom.h:277
LWGEOM * lwgeom_clip_by_rect(const LWGEOM *geom1, double x0, double y0, double x1, double y1)
#define MULTIPOINTTYPE
Definition: liblwgeom.h:73
#define POLYHEDRALSURFACETYPE
Definition: liblwgeom.h:82
int lwgeom_count_vertices(const LWGEOM *geom)
Count points in an LWGEOM.
Definition: lwgeom.c:1140
LWGEOM * lwgeom_clone_deep(const LWGEOM *lwgeom)
Deep-clone an LWGEOM object.
Definition: lwgeom.c:433
double ymin
Definition: liblwgeom.h:278
const char * lwtype_name(uint8_t type)
Return the type name string associated with a type number (e.g.
Definition: lwutil.c:188
double xmin
Definition: liblwgeom.h:276
LWGEOM ** geoms
Definition: liblwgeom.h:493
#define TINTYPE
Definition: liblwgeom.h:84
#define FP_TOLERANCE
Floating point comparators.
double ymax
Definition: liblwgeom.h:279
int lwgeom_is_collection(const LWGEOM *geom)
Determine whether a LWGEOM can contain sub-geometries or not.
Definition: lwgeom.c:991
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:70
uint8_t type
Definition: liblwgeom.h:380
static int lwgeom_subdivide_recursive(const LWGEOM *geom, int maxvertices, int depth, LWCOLLECTION *col, const GBOX *clip)
Definition: lwgeom.c:1899
void lwgeom_free(LWGEOM *lwgeom)
Definition: lwgeom.c:1050
LWCOLLECTION * lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom)
Appends geom to the collection managed by col.
Definition: lwcollection.c:174
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
Here is the call graph for this function:
Here is the caller graph for this function: