PostGIS  2.3.7dev-r@@SVN_REVISION@@
static int calculate_mbc ( const POINT2D **  points,
uint32_t  max_n,
SUPPORTING_POINTS support,
LWBOUNDINGCIRCLE mbc 
)
static

Definition at line 174 of file lwboundingcircle.c.

References add_supporting_point(), calculate_mbc_from_support(), LW_FAILURE, LW_SUCCESS, num_supporting_points(), and point_inside_circle().

Referenced by lwgeom_calculate_mbc().

175 {
176  uint32_t i;
177 
178  if(!calculate_mbc_from_support(support, mbc))
179  {
180  return LW_FAILURE;
181  }
182 
183  if (num_supporting_points(support) == 3)
184  {
185  /* If we're entering the function with three supporting points already, our circle
186  * is already fully constrained - we couldn't add another supporting point if we
187  * needed to. So, there's no point in proceeding further. Welzl (1991) provides
188  * a much better explanation of why this works.
189  * */
190  return LW_SUCCESS;
191  }
192 
193  for (i = 0; i < max_n; i++)
194  {
195  if (!point_inside_circle(points[i], mbc))
196  {
197  /* We've run into a point that isn't inside our circle. To fix this, we'll
198  * go back in time, and re-run the algorithm for each point we've seen so
199  * far, with the constraint that the current point must be on the boundary
200  * of the circle. Then, we'll continue on in this loop with the modified
201  * circle that by definition includes the current point. */
202  SUPPORTING_POINTS next_support;
203  memcpy(&next_support, support, sizeof(SUPPORTING_POINTS));
204 
205  add_supporting_point(&next_support, points[i]);
206  if (!calculate_mbc(points, i, &next_support, mbc))
207  {
208  return LW_FAILURE;
209  }
210  }
211  }
212 
213  return LW_SUCCESS;
214 }
static int calculate_mbc(const POINT2D **points, uint32_t max_n, SUPPORTING_POINTS *support, LWBOUNDINGCIRCLE *mbc)
#define LW_SUCCESS
Definition: liblwgeom.h:79
static int calculate_mbc_from_support(SUPPORTING_POINTS *support, LWBOUNDINGCIRCLE *mbc)
static int point_inside_circle(const POINT2D *p, const LWBOUNDINGCIRCLE *c)
#define LW_FAILURE
Definition: liblwgeom.h:78
static uint32_t num_supporting_points(SUPPORTING_POINTS *support)
static int add_supporting_point(SUPPORTING_POINTS *support, const POINT2D *p)

Here is the call graph for this function:

Here is the caller graph for this function: