PostGIS  2.1.10dev-r@@SVN_REVISION@@
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 204 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().

205 {
206  CIRC_NODE *node = NULL;
207  GEOGRAPHIC_POINT new_center, c1;
208  double new_radius;
209  double offset1, dist, D, r1, ri;
210  int i, new_geom_type;
211 
212  LWDEBUGF(3, "called with %d nodes --", num_nodes);
213 
214  /* Can't do anything w/ empty input */
215  if ( num_nodes < 1 )
216  return node;
217 
218  /* Initialize calculation with values of the first circle */
219  new_center = c[0]->center;
220  new_radius = c[0]->radius;
221  new_geom_type = c[0]->geom_type;
222 
223  /* Merge each remaining circle into the new circle */
224  for ( i = 1; i < num_nodes; i++ )
225  {
226  c1 = new_center;
227  r1 = new_radius;
228 
229  dist = sphere_distance(&c1, &(c[i]->center));
230  ri = c[i]->radius;
231 
232  /* Promote geometry types up the tree, getting more and more collected */
233  /* Go until we find a value */
234  if ( ! new_geom_type )
235  {
236  new_geom_type = c[i]->geom_type;
237  }
238  /* Promote singleton to a multi-type */
239  else if ( ! lwtype_is_collection(new_geom_type) )
240  {
241  /* Anonymous collection if types differ */
242  if ( new_geom_type != c[i]->geom_type )
243  {
244  new_geom_type = COLLECTIONTYPE;
245  }
246  else
247  {
248  new_geom_type = lwtype_get_collectiontype(new_geom_type);
249  }
250  }
251  /* If we can't add next feature to this collection cleanly, promote again to anonymous collection */
252  else if ( new_geom_type != lwtype_get_collectiontype(c[i]->geom_type) )
253  {
254  new_geom_type = COLLECTIONTYPE;
255  }
256 
257 
258  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);
259 
260  if ( FP_EQUALS(dist, 0) )
261  {
262  LWDEBUG(3, " distance between centers is zero");
263  new_radius = r1 + 2*dist;
264  new_center = c1;
265  }
266  else if ( dist < fabs(r1 - ri) )
267  {
268  /* new contains next */
269  if ( r1 > ri )
270  {
271  LWDEBUG(3, " c1 contains ci");
272  new_center = c1;
273  new_radius = r1;
274  }
275  /* next contains new */
276  else
277  {
278  LWDEBUG(3, " ci contains c1");
279  new_center = c[i]->center;
280  new_radius = ri;
281  }
282  }
283  else
284  {
285  LWDEBUG(3, " calculating new center");
286  /* New circle diameter */
287  D = dist + r1 + ri;
288  LWDEBUGF(3," D is %g", D);
289 
290  /* New radius */
291  new_radius = D / 2.0;
292 
293  /* Distance from cn1 center to the new center */
294  offset1 = ri + (D - (2.0*r1 + 2.0*ri)) / 2.0;
295  LWDEBUGF(3," offset1 is %g", offset1);
296 
297  /* Sometimes the sphere_direction function fails... this causes the center calculation */
298  /* to fail too. In that case, we're going to fall back ot a cartesian calculation, which */
299  /* is less exact, so we also have to pad the radius by (hack alert) an arbitrary amount */
300  /* which is hopefully always big enough to contain the input edges */
301  if ( circ_center_spherical(&c1, &(c[i]->center), dist, offset1, &new_center) == LW_FAILURE )
302  {
303  circ_center_cartesian(&c1, &(c[i]->center), dist, offset1, &new_center);
304  new_radius *= 1.1;
305  }
306  }
307  LWDEBUGF(3, " new center is (%g %g) new radius is %g", new_center.lon, new_center.lat, new_radius);
308  }
309 
310  node = lwalloc(sizeof(CIRC_NODE));
311  node->p1 = NULL;
312  node->p2 = NULL;
313  node->center = new_center;
314  node->radius = new_radius;
315  node->num_nodes = num_nodes;
316  node->nodes = c;
317  node->edge_num = -1;
318  node->geom_type = new_geom_type;
319  node->pt_outside.x = 0.0;
320  node->pt_outside.y = 0.0;
321  return node;
322 }
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:897
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:982
GEOGRAPHIC_POINT center
POINT2D * p2
POINT2D * p1
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
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:33
#define LW_FAILURE
Definition: liblwgeom.h:54
double x
Definition: liblwgeom.h:284
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:955
double y
Definition: liblwgeom.h:284
POINT2D pt_outside
#define FP_EQUALS(A, B)
double radius
void * lwalloc(size_t size)
Definition: lwutil.c:175
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
#define COLLECTIONTYPE
Definition: liblwgeom.h:66
struct circ_node ** nodes

Here is the call graph for this function:

Here is the caller graph for this function: