PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ circ_node_internal_new()

static CIRC_NODE* circ_node_internal_new ( CIRC_NODE **  c,
int  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 229 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().

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