merge.c

Go to the documentation of this file.

/*!
   \file lib/vector/vedit/merge.c
 
   \brief Vedit library - merge lines
 
   (C) 2006-2008 by the GRASS Development Team
 
   This program is free software under the GNU General Public License
   (>=v2).  Read the file COPYING that comes with GRASS for details.
 
   \author Jachym Cepicky <jachym.cepicky gmail.com>
   \author Martin Landa <landa.martin gmail.com>
 */
 
#include <grass/vedit.h>
 
/*!
   \brief Merge two given lines a, b
 
   a : Points1/Cats1
   b : Points2/Cats2
   merged line : Points/Cats
 
   \param Points1,Cats1 first line
   \param Points2,Cats2 second line
   \param thresh threshold value
   \param[out] Points result line
 
   \return 1 on success
   \return 0 on error
 */
static int merge_lines(struct line_pnts *Points1, struct line_cats *Cats1,
                       struct line_pnts *Points2, struct line_cats *Cats2,
                       double thresh, struct line_pnts **Points);
 
/*!
   \brief Merge lines/boundaries
 
   At least two lines need to be given.
 
   \param Map pointer to Map_info
   \param List list of selected lines
 
   \return number of merged lines
   \return -1 on error
 */
int Vedit_merge_lines(struct Map_info *Map, struct ilist *List)
{
    struct ilist *List_in_box;
 
    struct line_pnts *Points1, *Points2, *Points;
    struct line_cats *Cats1, *Cats2;
 
    int line_i, i, j;
    int line, line1, type1, line2;
    int do_merge;
 
    /* number of lines (original, selected, merged) */
    int nlines, nlines_merged;
 
    nlines_merged = 0;
 
    if (List->n_values < 2) {
        return 0;
    }
 
    G_debug(1, "Vedit_merge_lines(): merging %d lines", List->n_values);
 
    Points1 = Vect_new_line_struct();
    Cats1 = Vect_new_cats_struct();
    Points2 = Vect_new_line_struct();
    Cats2 = Vect_new_cats_struct();
    Points = Vect_new_line_struct();
 
    List_in_box = Vect_new_list();
 
    nlines = Vect_get_num_lines(Map);
 
    /* merge lines */
    for (line_i = 0; line_i < List->n_values; line_i++) {
        line1 = List->value[line_i];
 
        if (!Vect_line_alive(Map, line1))
            continue;
 
        type1 = Vect_read_line(Map, Points1, Cats1, line1);
 
        if (!(type1 & GV_LINES))
            continue;
 
        /* remove duplicate points */
        Vect_line_prune(Points1);
 
        if (Points1->n_points < 2) {
            G_debug(3, "Vedit_merge_lines(): skipping zero length line");
            continue;
        }
 
        Vect_reset_line(Points);
 
        for (i = 0; i < Points1->n_points; i += Points1->n_points - 1) {
            Vect_reset_list(List_in_box);
 
            /* define searching region */
            Vect_reset_line(Points2);
            /*
               Vect_append_point (Points2, Points1 -> x[i] - thresh,
               Points1 -> y[i] + thresh, Points1 -> z[i]);
               Vect_append_point (Points2, Points1 -> x[i] + thresh,
               Points1 -> y[i] + thresh, Points1 -> z[i]);
               Vect_append_point (Points2, Points1 -> x[i] + thresh,
               Points1 -> y[i] - thresh, Points1 -> z[i]);
               Vect_append_point (Points2, Points1 -> x[i] - thresh,
               Points1 -> y[i] - thresh, Points1 -> z[i]);
             */
            Vect_append_point(Points2, Points1->x[i], Points1->y[i],
                              Points1->z[i]);
 
            /*
             * merge lines only if two lines found in the region
             * i.e. the current line and an adjacent line
             */
            /* NOTE
             * - this merges two lines also if more than two lines are
             *   found in the region, but only two of these lines are
             *   in the List
             * - this not only merges lines connected by end points
             *   but also any adjacent line with a mid point identical
             *   to one of the end points of the current line
             */
            if (0 < Vect_find_line_list(Map, Points1->x[i], Points1->y[i],
                                        Points1->z[i], GV_LINES, 0, 0, NULL,
                                        List_in_box)) {
                do_merge = 1;
                line2 = -1;
                for (j = 0; do_merge && j < List_in_box->n_values; j++) {
                    if (List_in_box->value[j] == line1 ||
                        !Vect_line_alive(Map, List_in_box->value[j]))
                        continue;
 
                    if (Vect_val_in_list(List, List_in_box->value[j])) {
 
                        Vect_read_line(Map, Points2, Cats2,
                                       List_in_box->value[j]);
                        Vect_line_prune(Points2);
                        if (Points2->n_points == 1) {
                            line2 = List_in_box->value[j];
                            do_merge = 1;
                            break;
                        }
                        if (line2 > 0) {
                            /* three lines found
                             * selected lines will be not merged
                             */
                            do_merge = 0;
                        }
                        else {
                            line2 = List_in_box->value[j];
                        }
                    }
                }
 
                if (!do_merge || line2 < 0)
                    continue;
 
                Vect_read_line(Map, Points2, Cats2, line2);
 
                merge_lines(Points1, Cats1, Points2, Cats2, -1.0,
                            &Points); /* do not use threshold value */
 
                G_debug(3, "Vedit_merge_lines(): lines=%d,%d", line1, line2);
 
                if (Points->n_points > 0) {
                    if (Vect_delete_line(Map, line2) == -1) {
                        return -1;
                    }
 
                    if (line2 <= nlines)
                        nlines_merged++;
                }
            }
        } /* for each node */
 
        if (Points->n_points > 0) {
            line = Vect_rewrite_line(Map, line1, type1, Points, Cats1);
            if (line < 0) {
                nlines_merged = -1;
                goto free_exit;
            }
 
            if (line1 <= nlines)
                nlines_merged++;
 
            /* update number of lines */
            G_ilist_add(List, line);
        }
    } /* for each line */
 
free_exit:
    /* destroy structures */
    Vect_destroy_line_struct(Points1);
    Vect_destroy_line_struct(Points2);
    Vect_destroy_line_struct(Points);
 
    Vect_destroy_cats_struct(Cats1);
    Vect_destroy_cats_struct(Cats2);
 
    Vect_destroy_list(List_in_box);
 
    return nlines_merged;
}
 
static int merge_lines(struct line_pnts *Points1, struct line_cats *Cats1,
                       struct line_pnts *Points2, struct line_cats *Cats2,
                       double thresh, struct line_pnts **Points)
{
    struct line_pnts *ps = *Points;
    struct line_cats *cs = Cats1;
 
    int i, mindistidx;
    double mindist;
 
    /* find minimal distance and its index */
    mindist = Vedit_get_min_distance(Points1, Points2, 0, /* TODO 3D */
                                     &mindistidx);
 
    G_debug(3, "   merge line ? index: %d, mindist: %g, thresh: %g", mindistidx,
            mindist, thresh);
 
    if (thresh > 0 && mindist > thresh) {
        return 0;
    }
 
    /* set index and other things */
    switch (mindistidx) {
        /* for each mindistidx create new line */
    case 0:
        Vect_append_points(ps, Points2, GV_BACKWARD);
        if (ps->n_points == Points2->n_points)
            Vect_append_points(ps, Points1, GV_FORWARD);
        break;
    case 1:
        Vect_append_points(ps, Points2, GV_FORWARD);
        if (ps->n_points == Points2->n_points)
            Vect_append_points(ps, Points1, GV_FORWARD);
        break;
    case 2:
        if (ps->n_points == 0)
            Vect_append_points(ps, Points1, GV_FORWARD);
        Vect_append_points(ps, Points2, GV_FORWARD);
        break;
    case 3:
        if (ps->n_points == 0)
            Vect_append_points(ps, Points1, GV_FORWARD);
        Vect_append_points(ps, Points2, GV_BACKWARD);
        break;
    default:
        break;
    }
 
    /* remove duplicate points */
    Vect_line_prune(ps);
 
    /* copy categories if needed */
    for (i = 0; i < Cats2->n_cats; i++) {
        Vect_cat_set(cs, Cats2->field[i], Cats2->cat[i]);
    }
 
    return 1;
}