81 static int compare_xpnts(
const void *Xpnta,
const void *Xpntb)
101 G_warning(
_(
"Break polygons: Bug in binary tree!"));
111 int i, j, k, ret, ltype, broken, last, nlines;
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);
155 G_message(
_(
"Breaking polygons (pass 1: select break points)..."));
157 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++) {
185 if (j == last_point && closed)
199 G_debug(3,
"fpoint = %d", fpoint);
202 (!closed && (j == 0 || j == last_point))) {
207 if (j == 0 && closed) {
208 dx = Points->
x[last_point] - Points->
x[0];
209 dy = Points->
y[last_point] - Points->
y[0];
211 dx = Points->
x[1] - Points->
x[0];
212 dy = Points->
y[1] - Points->
y[0];
216 dx = Points->
x[j - 1] - Points->
x[j];
217 dy = Points->
y[j - 1] - Points->
y[j];
219 dx = Points->
x[j + 1] - Points->
x[j];
220 dy = Points->
y[j + 1] - Points->
y[j];
227 lseek(xpntfd, (off_t)(fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
228 if (read(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
230 __func__, errno, strerror(errno));
238 lseek(xpntfd, (off_t)(fpoint - 1) *
sizeof(XPNT2),
240 if (write(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
242 __func__, errno, strerror(errno));
245 G_debug(3,
"a1 = %f xa1 = %f a2 = %f xa2 = %f", a1, XPnt.a1,
247 if ((a1 == XPnt.a1 && a2 == XPnt.a2) ||
248 (a1 == XPnt.a2 && a2 == XPnt.a1)) {
253 lseek(xpntfd, (off_t)(fpoint - 1) *
sizeof(XPNT2),
255 if (write(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
257 __func__, errno, strerror(errno));
264 if (j == 0 || j == (Points->
n_points - 1) ||
276 lseek(xpntfd, (off_t)(npoints - 1) *
sizeof(XPNT2), SEEK_SET);
277 if (write(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
279 __func__, errno, strerror(errno));
291 G_message(
_(
"Breaking polygons (pass 2: break at selected points)..."));
293 for (i = 1; i <= nlines; i++) {
314 for (j = 1; j < Points->
n_points; j++) {
326 (j == (Points->
n_points - 1) && !broken))
332 G_debug(3,
"fpoint = %d", fpoint);
335 lseek(xpntfd, (off_t)(fpoint - 1) *
sizeof(XPNT2), SEEK_SET);
336 if (read(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
338 errno, strerror(errno));
341 if ((j == (Points->
n_points - 1) && broken) || XPnt.cross) {
343 for (k = last; k <= j; k++) {
353 "Line %d written j = %d n_points(orig,pruned) = %d "
354 "n_points(new) = %d",
363 if (XPnt.cross && !XPnt.used) {
372 lseek(xpntfd, (off_t)(fpoint - 1) *
sizeof(XPNT2),
374 if (write(xpntfd, &XPnt,
sizeof(XPNT2)) < 0)
376 __func__, errno, strerror(errno));
394 G_debug(3,
"Line %d was deleted", i);
398 G_debug(3,
"Line %d was not changed", i);
418 int i, j, k, ret, ltype, broken, last, nlines;
421 XPNT *XPnt_found, XPnt_search;
422 double dx, dy, a1 = 0, a2 = 0;
423 int closed, last_point, cross;
425 G_debug(1,
"Memory-based version of Vect_break_polygons()");
436 G_debug(3,
"nlines = %d", nlines);
441 XPnt_search.used = 0;
443 G_message(
_(
"Breaking polygons (pass 1: select break points)..."));
445 for (i = 1; i <= nlines; i++) {
464 if (Points->
x[0] == Points->
x[last_point] &&
465 Points->
y[0] == Points->
y[last_point])
470 for (j = 0; j < Points->
n_points; j++) {
473 if (j == last_point && closed)
476 XPnt_search.x = Points->
x[j];
477 XPnt_search.y = Points->
y[j];
483 (!closed && (j == 0 || j == last_point))) {
488 if (j == 0 && closed) {
489 dx = Points->
x[last_point] - Points->
x[0];
490 dy = Points->
y[last_point] - Points->
y[0];
492 dx = Points->
x[1] - Points->
x[0];
493 dy = Points->
y[1] - Points->
y[0];
497 dx = Points->
x[j - 1] - Points->
x[j];
498 dy = Points->
y[j - 1] - Points->
y[j];
500 dx = Points->
x[j + 1] - Points->
x[j];
501 dy = Points->
y[j + 1] - Points->
y[j];
507 if (XPnt_found->cross == 1)
512 XPnt_found->cross = 1;
515 G_debug(3,
"a1 = %f xa1 = %f a2 = %f xa2 = %f", a1,
516 XPnt_found->a1, a2, XPnt_found->a2);
517 if ((a1 == XPnt_found->a1 && a2 == XPnt_found->a2) ||
518 (a1 == XPnt_found->a2 &&
519 a2 == XPnt_found->a1)) {
522 XPnt_found->cross = 1;
527 if (j == 0 || j == (Points->
n_points - 1) ||
531 XPnt_search.cross = 1;
536 XPnt_search.cross = 0;
546 G_debug(2,
"Break polygons: unique vertices: %ld", (
long int)RBTree->
count);
555 G_message(
_(
"Breaking polygons (pass 2: break at selected points)..."));
557 for (i = 1; i <= nlines; i++) {
578 for (j = 1; j < Points->
n_points; j++) {
582 (j == (Points->
n_points - 1) && !broken))
587 XPnt_search.x = Points->
x[j];
588 XPnt_search.y = Points->
y[j];
593 if (XPnt_found ==
NULL)
597 if ((j == (Points->
n_points - 1) && broken) || XPnt_found->cross) {
599 for (k = last; k <= j; k++) {
609 "Line %d written j = %d n_points(orig,pruned) = %d "
610 "n_points(new) = %d",
619 if (XPnt_found->cross && !XPnt_found->used) {
625 XPnt_found->used = 1;
642 G_debug(3,
"Line %d was deleted", i);
646 G_debug(3,
"Line %d was not changed", i);
677 if (getenv(
"GRASS_VECTOR_LOWMEM"))
void Vect_break_polygons_mem(struct Map_info *Map, int type, struct Map_info *Err)
void Vect_break_polygons_file(struct Map_info *Map, int type, struct Map_info *Err)
void Vect_break_polygons(struct Map_info *Map, int type, struct Map_info *Err)
Break polygons in vector map.
void G_percent(long, long, int)
Print percent complete messages.
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void G_warning(const char *,...) __attribute__((format(printf
void void G_verbose_message(const char *,...) __attribute__((format(printf
char * G_tempfile(void)
Returns a temporary file name.
void G_message(const char *,...) __attribute__((format(printf
int G_debug(int, const char *,...) __attribute__((format(printf
int rbtree_insert(struct RB_TREE *, void *)
void * rbtree_find(struct RB_TREE *, const void *)
void rbtree_destroy(struct RB_TREE *)
struct RB_TREE * rbtree_create(rb_compare_fn *, size_t)
void Vect_destroy_line_struct(struct line_pnts *)
Frees all memory associated with a line_pnts structure, including the structure itself.
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)
plus_t Vect_get_num_lines(struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
int Vect_read_line(struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int Vect_line_alive(struct Map_info *, int)
Check if feature is alive or dead (topological level required)
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
void Vect_reset_line(struct line_pnts *)
Reset line.
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
#define GV_POINT
Feature types used in memory on run time (may change)
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Feature geometry info - coordinates.
double * y
Array of Y coordinates.
double * x
Array of X coordinates.
int n_points
Number of points.
double * z
Array of Z coordinates.
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.