union_dbscan_general()

static int union_dbscan_general ( LWGEOM **  geoms, uint32_t  num_geoms, UNIONFIND *  uf, double  eps, uint32_t  min_points, char **  in_a_cluster_ret  )

static

Definition at line 378 of file lwgeom_geos_cluster.c.

References dbscan_update_context(), destroy_strtree(), QueryContext::items_found, LW_FAILURE, LW_SUCCESS, LW_TRUE, lwalloc(), lwfree(), lwgeom_is_empty(), lwgeom_mindistance2d_tolerance(), make_strtree(), QueryContext::num_items_found, STRTree::tree, UF_find(), and union_if_available().

Referenced by union_dbscan().

{
        uint32_t p, i;
        struct STRTree tree;
        struct QueryContext cxt =
        {
                .items_found = NULL,
                .num_items_found = 0,
                .items_found_size = 0
        };
        int success = LW_SUCCESS;
        uint32_t* neighbors;
        char* in_a_cluster;
        char* is_in_core;

        in_a_cluster = lwalloc(num_geoms * sizeof(char));
        memset(in_a_cluster, 0, num_geoms * sizeof(char));

        if (in_a_cluster_ret)
                *in_a_cluster_ret = in_a_cluster;

        /* Bail if we don't even have enough inputs to make a cluster. */
        if (num_geoms <= min_points)
        {
                if (!in_a_cluster_ret)
                        lwfree(in_a_cluster);
                return LW_SUCCESS;
        }

        tree = make_strtree((void**) geoms, num_geoms, LW_TRUE);
        if (tree.tree == NULL)
        {
                destroy_strtree(&tree);
                return LW_FAILURE;
        }

        is_in_core = lwalloc(num_geoms * sizeof(char));
        memset(is_in_core, 0, num_geoms * sizeof(char));
        neighbors = lwalloc(min_points * sizeof(uint32_t));

        for (p = 0; p < num_geoms; p++)
        {
                uint32_t num_neighbors = 0;

                if (lwgeom_is_empty(geoms[p]))
                        continue;

                dbscan_update_context(tree.tree, &cxt, geoms, p, eps);

                /* We didn't find enough points to do anything, even if they are all within eps. */
                if (cxt.num_items_found < min_points)
                        continue;

                for (i = 0; i < cxt.num_items_found; i++)
                {
                        uint32_t q = *((uint32_t*) cxt.items_found[i]);

                        if (num_neighbors >= min_points)
                        {
                                /* If we've already identified p as a core point, and it's already
                                 * in the same cluster in q, then there's nothing to learn by
                                 * computing the distance.
                                 */
                                if (UF_find(uf, p) == UF_find(uf, q))
                                        continue;

                                /* Similarly, if q is already identifed as a border point of another
                                 * cluster, there's no point figuring out what the distance is.
                                 */
                                if (in_a_cluster[q] && !is_in_core[q])
                                        continue;
                        }

                        double mindist = lwgeom_mindistance2d_tolerance(geoms[p], geoms[q], eps);
                        if (mindist == FLT_MAX)
                        {
                                success = LW_FAILURE;
                                break;
                        }

                        if (mindist <= eps)
                        {
                                /* If we haven't hit min_points yet, we don't know if we can union p and q.
                                 * Just set q aside for now.
                                 */
                                if (num_neighbors < min_points)
                                {
                                        neighbors[num_neighbors++] = q;

                                        /* If we just hit min_points, we can now union all of the neighbor geometries
                                         * we've been saving.
                                         */
                                        if (num_neighbors == min_points)
                                        {
                                                uint32_t j;
                                                is_in_core[p] = LW_TRUE;
                                                in_a_cluster[p] = LW_TRUE;
                                                for (j = 0; j < num_neighbors; j++)
                                                {
                                                        union_if_available(uf, p, neighbors[j], is_in_core, in_a_cluster);
                                                }
                                        }
                                }
                                else
                                {
                                        /* If we're above min_points, no need to store our neighbors, just go ahead
                                         * and union them now.  This may allow us to cut out some distance
                                         * computations.
                                         */
                                        union_if_available(uf, p, q, is_in_core, in_a_cluster);
                                }
                        }
                }

                if (!success)
                        break;
        }

        lwfree(neighbors);
        lwfree(is_in_core);

        /* Free in_a_cluster if we're not giving it to our caller */
        if (!in_a_cluster_ret)
                lwfree(in_a_cluster);

        if (cxt.items_found)
                lwfree(cxt.items_found);

        destroy_strtree(&tree);
        return success;
}

Here is the call graph for this function:

Here is the caller graph for this function: