Geografic-Information-System/lib/vector/vedit/merge.c

/*!
  \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) {
		return -1;
	    }

	    if (line1 <= nlines)
		nlines_merged++;

	    /* update number of lines */
	    G_ilist_add(List, line);
	}
    }				/* for each line */

    /* 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);

    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 mininal 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;
}