74 static int srch(
int id,
const struct RTree_Rect *rect,
void *arg)
82 static int compare_xpnts(
const void *Xpnta,
const void *Xpntb)
102 G_warning(
_(
"Break polygons: Bug in binary tree!"));
111 int i, j, k, ret, ltype, broken, last, nlines;
114 int npoints, nallpoints, nmarks;
116 double dx, dy, a1 = 0, a2 = 0;
117 int closed, last_point;
122 static int rect_init = 0;
129 G_debug(1,
"File-based version of Vect_break_polygons()");
132 fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
137 xpntfd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
147 G_debug(3,
"nlines = %d", nlines);
156 G_message(
_(
"Breaking polygons (pass 1: select break points)..."));
158 for (i = 1; i <= nlines; i++) {
176 if (Points->
x[0] == Points->
x[last_point] &&
177 Points->
y[0] == Points->
y[last_point])
182 for (j = 0; j < Points->
n_points; j++) {
186 if (j == last_point && closed)
200 G_debug(3,
"fpoint = %d", fpoint);
203 (!closed && (j == 0 || j == last_point))) {
208 if (j == 0 && closed) {
209 dx = Points->
x[last_point] - Points->
x[0];
210 dy = Points->
y[last_point] - Points->
y[0];
212 dx = Points->
x[1] - Points->
x[0];
213 dy = Points->
y[1] - Points->
y[0];
217 dx = Points->
x[j - 1] - Points->
x[j];
218 dy = Points->
y[j - 1] - Points->
y[j];
220 dx = Points->
x[j + 1] - Points->
x[j];
221 dy = Points->
y[j + 1] - Points->
y[j];
228 lseek(xpntfd, (off_t) (fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
229 read(xpntfd, &XPnt,
sizeof(XPNT2));
238 lseek(xpntfd, (off_t) (fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
239 write(xpntfd, &XPnt,
sizeof(XPNT2));
242 G_debug(3,
"a1 = %f xa1 = %f a2 = %f xa2 = %f", a1,
243 XPnt.a1, a2, XPnt.a2);
244 if ((a1 == XPnt.a1 && a2 == XPnt.a2) ||
245 (a1 == XPnt.a2 && a2 == XPnt.a1)) {
252 lseek(xpntfd, (off_t) (fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
253 write(xpntfd, &XPnt,
sizeof(XPNT2));
260 if (j == 0 || j == (Points->
n_points - 1) ||
273 lseek(xpntfd, (off_t) (npoints - 1) *
sizeof(XPNT2), SEEK_SET);
274 write(xpntfd, &XPnt,
sizeof(XPNT2));
286 G_message(
_(
"Breaking polygons (pass 2: break at selected points)..."));
288 for (i = 1; i <= nlines; i++) {
309 for (j = 1; j < Points->
n_points; j++) {
322 (j == (Points->
n_points - 1) && !broken))
328 G_debug(3,
"fpoint = %d", fpoint);
331 lseek(xpntfd, (off_t) (fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
332 read(xpntfd, &XPnt,
sizeof(XPNT2));
335 if ((j == (Points->
n_points - 1) && broken) ||
338 for (k = last; k <= j; k++) {
348 "Line %d written j = %d n_points(orig,pruned) = %d n_points(new) = %d",
357 if (XPnt.cross && !XPnt.used) {
365 lseek(xpntfd, (off_t) (fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
366 write(xpntfd, &XPnt,
sizeof(XPNT2));
375 if (!broken && n_orig_points > Points->
n_points) {
378 G_debug(3,
"Line %d pruned, npoints = %d", i,
383 G_debug(3,
"Line %d was deleted", i);
387 G_debug(3,
"Line %d was not changed", i);
407 int i, j, k, ret, ltype, broken, last, nlines;
410 int npoints, nallpoints, nmarks;
411 XPNT *XPnt_found, XPnt_search;
412 double dx, dy, a1 = 0, a2 = 0;
413 int closed, last_point, cross;
415 G_debug(1,
"Memory-based version of Vect_break_polygons()");
426 G_debug(3,
"nlines = %d", nlines);
433 XPnt_search.used = 0;
435 G_message(
_(
"Breaking polygons (pass 1: select break points)..."));
437 for (i = 1; i <= nlines; i++) {
455 if (Points->
x[0] == Points->
x[last_point] &&
456 Points->
y[0] == Points->
y[last_point])
461 for (j = 0; j < Points->
n_points; j++) {
465 if (j == last_point && closed)
468 XPnt_search.x = Points->
x[j];
469 XPnt_search.y = Points->
y[j];
475 (!closed && (j == 0 || j == last_point))) {
480 if (j == 0 && closed) {
481 dx = Points->
x[last_point] - Points->
x[0];
482 dy = Points->
y[last_point] - Points->
y[0];
484 dx = Points->
x[1] - Points->
x[0];
485 dy = Points->
y[1] - Points->
y[0];
489 dx = Points->
x[j - 1] - Points->
x[j];
490 dy = Points->
y[j - 1] - Points->
y[j];
492 dx = Points->
x[j + 1] - Points->
x[j];
493 dy = Points->
y[j + 1] - Points->
y[j];
499 if (XPnt_found->cross == 1)
504 XPnt_found->cross = 1;
508 G_debug(3,
"a1 = %f xa1 = %f a2 = %f xa2 = %f", a1,
509 XPnt_found->a1, a2, XPnt_found->a2);
510 if ((a1 == XPnt_found->a1 && a2 == XPnt_found->a2) ||
511 (a1 == XPnt_found->a2 && a2 == XPnt_found->a1)) {
515 XPnt_found->cross = 1;
521 if (j == 0 || j == (Points->
n_points - 1) ||
525 XPnt_search.cross = 1;
531 XPnt_search.cross = 0;
543 G_debug(2,
"Break polygons: unique vertices: %ld", (
long int)RBTree->
count);
552 G_message(
_(
"Breaking polygons (pass 2: break at selected points)..."));
554 for (i = 1; i <= nlines; i++) {
575 for (j = 1; j < Points->
n_points; j++) {
580 (j == (Points->
n_points - 1) && !broken))
585 XPnt_search.x = Points->
x[j];
586 XPnt_search.y = Points->
y[j];
591 if (XPnt_found ==
NULL)
595 if ((j == (Points->
n_points - 1) && broken) ||
598 for (k = last; k <= j; k++) {
608 "Line %d written j = %d n_points(orig,pruned) = %d n_points(new) = %d",
617 if (XPnt_found->cross && !XPnt_found->used) {
622 XPnt_found->used = 1;
630 if (!broken && n_orig_points > Points->
n_points) {
633 G_debug(3,
"Line %d pruned, npoints = %d", i,
638 G_debug(3,
"Line %d was deleted", i);
642 G_debug(3,
"Line %d was not changed", i);
673 if (
getenv(
"GRASS_VECTOR_LOWMEM"))
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
void Vect_break_polygons(struct Map_info *Map, int type, struct Map_info *Err)
Break polygons in vector map.
plus_t Vect_get_num_lines(const struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
off_t Vect_rewrite_line(struct Map_info *, off_t, int, const struct line_pnts *, const struct line_cats *)
Rewrites existing feature (topological level required)
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
int n_points
Number of points.
void * rbtree_find(struct RB_TREE *, const void *)
struct RB_TREE * rbtree_create(rb_compare_fn *, size_t)
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
#define GV_POINT
Feature types used in memory on run time (may change)
void G_message(const char *,...) __attribute__((format(printf
void Vect_break_polygons_mem(struct Map_info *Map, int type, struct Map_info *Err)
double * x
Array of X coordinates.
Feature geometry info - coordinates.
int rbtree_insert(struct RB_TREE *, void *)
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
char * G_tempfile(void)
Returns a temporary file name.
void Vect_break_polygons_file(struct Map_info *Map, int type, struct Map_info *Err)
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
void G_percent(long, long, int)
Print percent complete messages.
double * y
Array of Y coordinates.
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
void G_warning(const char *,...) __attribute__((format(printf
int Vect_line_alive(const struct Map_info *, int)
Check if feature is alive or dead (topological level required)
double * z
Array of Z coordinates.
void rbtree_destroy(struct RB_TREE *)
void Vect_destroy_line_struct(struct line_pnts *)
Frees all memory associated with a line_pnts structure, including the structure itself.
void void G_verbose_message(const char *,...) __attribute__((format(printf
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int G_debug(int, const char *,...) __attribute__((format(printf
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
void Vect_reset_line(struct line_pnts *)
Reset line.