PostGIS  2.5.0dev-r@@SVN_REVISION@@

◆ circ_node_internal_new()

static CIRC_NODE* circ_node_internal_new ( CIRC_NODE **  c,
uint32_t  num_nodes 
)
static

Create a new internal node, calculating the new measure range for the node, and storing pointers to the child nodes.

Definition at line 231 of file lwgeodetic_tree.c.

References circ_node::center, circ_center_cartesian(), circ_center_spherical(), COLLECTIONTYPE, circ_node::edge_num, FP_EQUALS, circ_node::geom_type, GEOGRAPHIC_POINT::lat, GEOGRAPHIC_POINT::lon, LW_FAILURE, lwalloc(), LWDEBUG, LWDEBUGF, lwtype_get_collectiontype(), lwtype_is_collection(), circ_node::nodes, circ_node::num_nodes, circ_node::p1, circ_node::p2, circ_node::pt_outside, circ_node::radius, sphere_distance(), POINT2D::x, and POINT2D::y.

Referenced by circ_nodes_merge().

232 {
233  CIRC_NODE *node = NULL;
234  GEOGRAPHIC_POINT new_center, c1;
235  double new_radius;
236  double offset1, dist, D, r1, ri;
237  uint32_t i, new_geom_type;
238 
239  LWDEBUGF(3, "called with %d nodes --", num_nodes);
240 
241  /* Can't do anything w/ empty input */
242  if ( num_nodes < 1 )
243  return node;
244 
245  /* Initialize calculation with values of the first circle */
246  new_center = c[0]->center;
247  new_radius = c[0]->radius;
248  new_geom_type = c[0]->geom_type;
249 
250  /* Merge each remaining circle into the new circle */
251  for ( i = 1; i < num_nodes; i++ )
252  {
253  c1 = new_center;
254  r1 = new_radius;
255 
256  dist = sphere_distance(&c1, &(c[i]->center));
257  ri = c[i]->radius;
258 
259  /* Promote geometry types up the tree, getting more and more collected */
260  /* Go until we find a value */
261  if ( ! new_geom_type )
262  {
263  new_geom_type = c[i]->geom_type;
264  }
265  /* Promote singleton to a multi-type */
266  else if ( ! lwtype_is_collection(new_geom_type) )
267  {
268  /* Anonymous collection if types differ */
269  if ( new_geom_type != c[i]->geom_type )
270  {
271  new_geom_type = COLLECTIONTYPE;
272  }
273  else
274  {
275  new_geom_type = lwtype_get_collectiontype(new_geom_type);
276  }
277  }
278  /* If we can't add next feature to this collection cleanly, promote again to anonymous collection */
279  else if ( new_geom_type != lwtype_get_collectiontype(c[i]->geom_type) )
280  {
281  new_geom_type = COLLECTIONTYPE;
282  }
283 
284 
285  LWDEBUGF(3, "distance between new (%g %g) and %i (%g %g) is %g", c1.lon, c1.lat, i, c[i]->center.lon, c[i]->center.lat, dist);
286 
287  if ( FP_EQUALS(dist, 0) )
288  {
289  LWDEBUG(3, " distance between centers is zero");
290  new_radius = r1 + 2*dist;
291  new_center = c1;
292  }
293  else if ( dist < fabs(r1 - ri) )
294  {
295  /* new contains next */
296  if ( r1 > ri )
297  {
298  LWDEBUG(3, " c1 contains ci");
299  new_center = c1;
300  new_radius = r1;
301  }
302  /* next contains new */
303  else
304  {
305  LWDEBUG(3, " ci contains c1");
306  new_center = c[i]->center;
307  new_radius = ri;
308  }
309  }
310  else
311  {
312  LWDEBUG(3, " calculating new center");
313  /* New circle diameter */
314  D = dist + r1 + ri;
315  LWDEBUGF(3," D is %g", D);
316 
317  /* New radius */
318  new_radius = D / 2.0;
319 
320  /* Distance from cn1 center to the new center */
321  offset1 = ri + (D - (2.0*r1 + 2.0*ri)) / 2.0;
322  LWDEBUGF(3," offset1 is %g", offset1);
323 
324  /* Sometimes the sphere_direction function fails... this causes the center calculation */
325  /* to fail too. In that case, we're going to fall back to a cartesian calculation, which */
326  /* is less exact, so we also have to pad the radius by (hack alert) an arbitrary amount */
327  /* which is hopefully always big enough to contain the input edges */
328  if ( circ_center_spherical(&c1, &(c[i]->center), dist, offset1, &new_center) == LW_FAILURE )
329  {
330  circ_center_cartesian(&c1, &(c[i]->center), dist, offset1, &new_center);
331  new_radius *= 1.1;
332  }
333  }
334  LWDEBUGF(3, " new center is (%g %g) new radius is %g", new_center.lon, new_center.lat, new_radius);
335  }
336 
337  node = lwalloc(sizeof(CIRC_NODE));
338  node->p1 = NULL;
339  node->p2 = NULL;
340  node->center = new_center;
341  node->radius = new_radius;
342  node->num_nodes = num_nodes;
343  node->nodes = c;
344  node->edge_num = -1;
345  node->geom_type = new_geom_type;
346  node->pt_outside.x = 0.0;
347  node->pt_outside.y = 0.0;
348  return node;
349 }
double sphere_distance(const GEOGRAPHIC_POINT *s, const GEOGRAPHIC_POINT *e)
Given two points on a unit sphere, calculate their distance apart in radians.
Definition: lwgeodetic.c:917
Note that p1 and p2 are pointers into an independent POINTARRAY, do not free them.
GEOGRAPHIC_POINT center
uint32_t num_nodes
uint32_t geom_type
POINT2D * p2
POINT2D * p1
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
static int circ_center_spherical(const GEOGRAPHIC_POINT *c1, const GEOGRAPHIC_POINT *c2, double distance, double offset, GEOGRAPHIC_POINT *center)
Given the centers of two circles, and the offset distance we want to put the new center between them ...
Point in spherical coordinates on the world.
Definition: lwgeodetic.h:47
#define LW_FAILURE
Definition: liblwgeom.h:78
unsigned int uint32_t
Definition: uthash.h:78
double x
Definition: liblwgeom.h:330
static int circ_center_cartesian(const GEOGRAPHIC_POINT *c1, const GEOGRAPHIC_POINT *c2, double distance, double offset, GEOGRAPHIC_POINT *center)
Where the circ_center_spherical() function fails, we need a fall-back.
int lwtype_is_collection(uint8_t type)
Determine whether a type number is a collection or not.
Definition: lwgeom.c:1093
double y
Definition: liblwgeom.h:330
uint32_t lwtype_get_collectiontype(uint8_t type)
Given an lwtype number, what homogeneous collection can hold it?
Definition: lwgeom.c:1120
POINT2D pt_outside
#define FP_EQUALS(A, B)
double radius
void * lwalloc(size_t size)
Definition: lwutil.c:229
CIRC_NODE * node
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
#define COLLECTIONTYPE
Definition: liblwgeom.h:90
struct circ_node ** nodes
Here is the call graph for this function:
Here is the caller graph for this function: