Geografic-Information-System/lib/vector/Vlib/remove_duplicates.c

/*!
   \file remove_duplicates.c

   \brief Vector library - clean geometry (remove duplicates)

   Higher level functions for reading/writing/manipulating vectors.

   (C) 2001-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 Radim Blazek

   \date 2001
 */

#include <stdlib.h>
#include <grass/gis.h>
#include <grass/Vect.h>
#include <grass/glocale.h>

/*!
   \brief Remove duplicate lines from vector map.

   Remove duplicate lines of given types from vector map. Duplicate lines may be optionally 
   written to error map. Input map must be opened on level 2 for update. Categories are merged.

   \param Map vector map where duplicate lines will be deleted
   \param type type of line to be delete
   \param Err vector map where duplicate lines will be written or NULL

   \return void
 */
void
Vect_remove_duplicates(struct Map_info *Map, int type, struct Map_info *Err)
{
    struct line_pnts *APoints, *BPoints;
    struct line_cats *ACats, *BCats, *Cats;
    int i, j, c, atype, btype, bline;
    int nlines, nbcats_orig;
    BOUND_BOX ABox;
    struct ilist *List;
    int ndupl;


    APoints = Vect_new_line_struct();
    BPoints = Vect_new_line_struct();
    ACats = Vect_new_cats_struct();
    BCats = Vect_new_cats_struct();
    Cats = Vect_new_cats_struct();
    List = Vect_new_list();

    nlines = Vect_get_num_lines(Map);

    G_debug(1, "nlines =  %d", nlines);
    /* Go through all lines in vector, for each select lines which overlap MBR of
     *  this line and check if some of them is identical. If someone is identical
     *  remove current line. (In each step just one line is deleted)
     */

    ndupl = 0;

    for (i = 1; i <= nlines; i++) {
	if (!Vect_line_alive(Map, i))
	    continue;

	atype = Vect_read_line(Map, APoints, ACats, i);
	if (!(atype & type))
	    continue;

	Vect_line_box(APoints, &ABox);
	Vect_select_lines_by_box(Map, &ABox, type, List);
	G_debug(3, "  %d lines selected by box", List->n_values);

	for (j = 0; j < List->n_values; j++) {
	    bline = List->value[j];
	    G_debug(3, "  j = %d bline = %d", j, bline);
	    if (i == bline)
		continue;

	    btype = Vect_read_line(Map, BPoints, BCats, bline);

	    /* check for duplicates */
	    if (!Vect_line_check_duplicate(APoints, BPoints, Vect_is_3d(Map)))
		continue;

	    /* Lines area identical -> remove current */
	    if (Err) {
		Vect_write_line(Err, atype, APoints, ACats);
	    }

	    Vect_delete_line(Map, i);

	    /* Merge categories */
	    nbcats_orig = BCats->n_cats;

	    for (c = 0; c < ACats->n_cats; c++)
		Vect_cat_set(BCats, ACats->field[c], ACats->cat[c]);

	    if (BCats->n_cats > nbcats_orig) {
		G_debug(4, "cats merged: n_cats %d -> %d", nbcats_orig,
			BCats->n_cats);
		Vect_rewrite_line(Map, bline, btype, BPoints, BCats);
	    }

	    ndupl++;

	    break;		/* line was deleted -> take the next one */
	}
	nlines = Vect_get_num_lines(Map);	/* For future when lines with cats will be rewritten */
	G_debug(3, "nlines =  %d\n", nlines);
    }
}

/*!
   \brief Check for duplicate lines

   \param APoints first line geometry
   \param BPoints second line geometry

   \return 1 duplicate
   \return 0 not duplicate
 */
int Vect_line_check_duplicate(const struct line_pnts *APoints,
			      const struct line_pnts *BPoints, int with_z)
{
    int k;
    int npoints;
    int forw, backw;

    if (APoints->n_points != BPoints->n_points)
	return 0;

    npoints = APoints->n_points;

    /* Forward */
    forw = 1;
    for (k = 0; k < APoints->n_points; k++) {
	if (APoints->x[k] != BPoints->x[k] ||
	    APoints->y[k] != BPoints->y[k] ||
	    (with_z && APoints->z[k] != BPoints->z[k])) {
	    forw = 0;
	    break;
	}
    }

    /* Backward */
    backw = 1;
    for (k = 0; k < APoints->n_points; k++) {
	if (APoints->x[k] != BPoints->x[npoints - k - 1] ||
	    APoints->y[k] != BPoints->y[npoints - k - 1] ||
	    (with_z && APoints->z[k] != BPoints->z[npoints - k - 1])) {
	    backw = 0;
	    break;
	}
    }

    if (!forw && !backw)
	return 0;

    return 1;
}