calculate_mbc()

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().

{
        uint32_t i;

        if(!calculate_mbc_from_support(support, mbc))
        {
                return LW_FAILURE;
        }

        if (num_supporting_points(support) == 3)
        {
                /* If we're entering the function with three supporting points already, our circle
                 * is already fully constrained - we couldn't add another supporting point if we
                 * needed to. So, there's no point in proceeding further.  Welzl (1991) provides
                 * a much better explanation of why this works.
                 * */
                return LW_SUCCESS;
        }

        for (i = 0; i < max_n; i++)
        {
                if (!point_inside_circle(points[i], mbc))
                {
                        /* We've run into a point that isn't inside our circle.  To fix this, we'll
                         * go back in time, and re-run the algorithm for each point we've seen so
                         * far, with the constraint that the current point must be on the boundary
                         * of the circle.  Then, we'll continue on in this loop with the modified
                         * circle that by definition includes the current point. */
                        SUPPORTING_POINTS next_support;
                        memcpy(&next_support, support, sizeof(SUPPORTING_POINTS));

                        add_supporting_point(&next_support, points[i]);
                        if (!calculate_mbc(points, i, &next_support, mbc))
                        {
                                return LW_FAILURE;
                        }
                }
        }

        return LW_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function: