PostGIS  2.5.0dev-r@@SVN_REVISION@@

◆ lwgeom_subdivide_recursive()

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

Definition at line 2249 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().

2250 {
2251  const uint32_t maxdepth = 50;
2252  uint32_t nvertices = 0;
2253  uint32_t i, n = 0;
2254  double width = clip->xmax - clip->xmin;
2255  double height = clip->ymax - clip->ymin;
2256  GBOX subbox1, subbox2;
2257  LWGEOM *clipped1, *clipped2;
2258 
2259  if ( geom->type == POLYHEDRALSURFACETYPE || geom->type == TINTYPE )
2260  {
2261  lwerror("%s: unsupported geometry type '%s'", __func__, lwtype_name(geom->type));
2262  }
2263 
2264  if ( width == 0.0 && height == 0.0 )
2265  {
2266  if ( geom->type == POINTTYPE )
2267  {
2269  return 1;
2270  }
2271  else
2272  {
2273  return 0;
2274  }
2275  }
2276 
2277  /* Always just recurse into collections */
2278  if ( lwgeom_is_collection(geom) && geom->type != MULTIPOINTTYPE )
2279  {
2280  LWCOLLECTION *incol = (LWCOLLECTION*)geom;
2281  int n = 0;
2282  for ( i = 0; i < incol->ngeoms; i++ )
2283  {
2284  /* Don't increment depth yet, since we aren't actually subdividing geomtries yet */
2285  n += lwgeom_subdivide_recursive(incol->geoms[i], maxvertices, depth, col, clip);
2286  }
2287  return n;
2288  }
2289 
2290  /* But don't go too far. 2^50 ~= 10^15, that's enough subdivision */
2291  /* Just add what's left */
2292  if ( depth > maxdepth )
2293  {
2295  return 1;
2296  }
2297 
2298  nvertices = lwgeom_count_vertices(geom);
2299  /* Skip empties entirely */
2300  if ( nvertices == 0 )
2301  {
2302  return 0;
2303  }
2304 
2305  /* If it is under the vertex tolerance, just add it, we're done */
2306  if ( nvertices < maxvertices )
2307  {
2309  return 1;
2310  }
2311 
2312  subbox1 = subbox2 = *clip;
2313  if ( width > height )
2314  {
2315  subbox1.xmax = subbox2.xmin = (clip->xmin + clip->xmax)/2;
2316  }
2317  else
2318  {
2319  subbox1.ymax = subbox2.ymin = (clip->ymin + clip->ymax)/2;
2320  }
2321 
2322  if ( height == 0 )
2323  {
2324  subbox1.ymax += FP_TOLERANCE;
2325  subbox2.ymax += FP_TOLERANCE;
2326  subbox1.ymin -= FP_TOLERANCE;
2327  subbox2.ymin -= FP_TOLERANCE;
2328  }
2329 
2330  if ( width == 0 )
2331  {
2332  subbox1.xmax += FP_TOLERANCE;
2333  subbox2.xmax += FP_TOLERANCE;
2334  subbox1.xmin -= FP_TOLERANCE;
2335  subbox2.xmin -= FP_TOLERANCE;
2336  }
2337 
2338  clipped1 = lwgeom_clip_by_rect(geom, subbox1.xmin, subbox1.ymin, subbox1.xmax, subbox1.ymax);
2339  clipped2 = lwgeom_clip_by_rect(geom, subbox2.xmin, subbox2.ymin, subbox2.xmax, subbox2.ymax);
2340 
2341  ++depth;
2342 
2343  if ( clipped1 )
2344  {
2345  n += lwgeom_subdivide_recursive(clipped1, maxvertices, depth, col, &subbox1);
2346  lwgeom_free(clipped1);
2347  }
2348 
2349  if ( clipped2 )
2350  {
2351  n += lwgeom_subdivide_recursive(clipped2, maxvertices, depth, col, &subbox2);
2352  lwgeom_free(clipped2);
2353  }
2354 
2355  return n;
2356 
2357 }
double xmax
Definition: liblwgeom.h:292
LWGEOM * lwgeom_clip_by_rect(const LWGEOM *geom1, double x0, double y0, double x1, double y1)
#define MULTIPOINTTYPE
Definition: liblwgeom.h:87
uint32_t lwgeom_count_vertices(const LWGEOM *geom)
Count points in an LWGEOM.
Definition: lwgeom.c:1228
#define POLYHEDRALSURFACETYPE
Definition: liblwgeom.h:96
uint32_t ngeoms
Definition: liblwgeom.h:506
unsigned int uint32_t
Definition: uthash.h:78
LWGEOM * lwgeom_clone_deep(const LWGEOM *lwgeom)
Deep-clone an LWGEOM object.
Definition: lwgeom.c:513
double ymin
Definition: liblwgeom.h:293
const char * lwtype_name(uint8_t type)
Return the type name string associated with a type number (e.g.
Definition: lwutil.c:218
double xmin
Definition: liblwgeom.h:291
LWGEOM ** geoms
Definition: liblwgeom.h:508
#define TINTYPE
Definition: liblwgeom.h:98
static int lwgeom_subdivide_recursive(const LWGEOM *geom, uint32_t maxvertices, uint32_t depth, LWCOLLECTION *col, const GBOX *clip)
Definition: lwgeom.c:2249
#define FP_TOLERANCE
Floating point comparators.
double ymax
Definition: liblwgeom.h:294
int lwgeom_is_collection(const LWGEOM *geom)
Determine whether a LWGEOM can contain sub-geometries or not.
Definition: lwgeom.c:1078
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:84
uint8_t type
Definition: liblwgeom.h:395
void lwgeom_free(LWGEOM *lwgeom)
Definition: lwgeom.c:1137
LWCOLLECTION * lwcollection_add_lwgeom(LWCOLLECTION *col, const LWGEOM *geom)
Appends geom to the collection managed by col.
Definition: lwcollection.c:187
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
Here is the call graph for this function:
Here is the caller graph for this function: