27#include <grass/kdtree.h>
49static int sort_new(
const void *
pa,
const void *pb)
54 return (
p1->along < p2->along ? -1 : (
p1->along > p2->along));
66 double x, y, z, along;
70static int sort_new2(
const void *
pa,
const void *pb)
72 NEW2 *
p1 = (NEW2 *)
pa;
73 NEW2 *p2 = (NEW2 *)pb;
75 return (
p1->along < p2->along ? -1 : (
p1->along > p2->along));
95static int find_item_box(
int id,
const struct RTree_Rect *rect,
void *
list)
113static int add_item_box(
int id,
const struct RTree_Rect *rect,
void *
list)
129static void Vect_snap_lines_list_rtree(
struct Map_info *,
const struct ilist *,
132static void Vect_snap_lines_list_kdtree(
struct Map_info *,
const struct ilist *,
175 if (
getenv(
"GRASS_VECTOR_LOWMEM"))
181static void Vect_snap_lines_list_kdtree(
struct Map_info *
Map,
238 for (v = 0; v < Points->
n_points; v++) {
240 G_debug(3,
" vertex v = %d", v);
253 XPnts[point].x = Points->
x[v];
254 XPnts[point].y = Points->
y[v];
255 XPnts[point].anchor = -1;
269 for (point = 1; point <= npoints; point++) {
274 G_debug(3,
" point = %d", point);
276 if (
XPnts[point].anchor >= 0)
279 XPnts[point].anchor = 0;
282 c[0] =
XPnts[point].x;
283 c[1] =
XPnts[point].y;
291 double dx, dy, dist2;
299 dist2 = dx * dx + dy * dy;
358 G_debug(3,
"Snap all vertices");
359 for (v = 0; v < Points->
n_points; v++) {
375 Points->
x[v] =
XPnts[anchor].x;
376 Points->
y[v] =
XPnts[anchor].y;
390 G_debug(3,
"Snap all segments");
391 for (v = 0; v < Points->
n_points - 1; v++) {
393 double x1, x2, y1, y2, xmin, xmax, ymin, ymax;
396 G_debug(3,
" segment = %d end anchors : %d %d", v,
Index[v],
400 x2 = Points->
x[v + 1];
402 y2 = Points->
y[v + 1];
427 G_debug(3,
" search anchors for segment %g,%g to %g,%g", x1, y1,
464 if (status == 0 && dist2 <=
thresh2) {
465 G_debug(4,
" anchor in thresh, along = %lf", along);
485 for (i = 0; i <
nnew; i++) {
486 anchor =
New[i].anchor;
529static void Vect_snap_lines_list_rtree(
struct Map_info *
Map,
566 if (
getenv(
"GRASS_VECTOR_LOWMEM")) {
574 if (
remove(filename) != 0) {
575 G_warning(
_(
"Unable to remove temporary file <%s>: %s"), filename,
604 for (v = 0; v < Points->
n_points; v++) {
605 G_debug(3,
" vertex v = %d", v);
620 if (
List->n_values == 0) {
628 XPnts[point].x = Points->
x[v];
629 XPnts[point].y = Points->
y[v];
630 XPnts[point].anchor = -1;
644 for (point = 1; point <= npoints; point++) {
649 G_debug(3,
" point = %d", point);
651 if (
XPnts[point].anchor >= 0)
654 XPnts[point].anchor = 0;
666 G_debug(4,
" %d points in threshold box",
List->n_values);
668 for (i = 0; i <
List->n_values; i++) {
670 double dx, dy, dist2;
678 dist2 = dx * dx + dy * dy;
732 for (v = 0; v < Points->
n_points; v++) {
750 Points->
x[v] =
XPnts[anchor].x;
751 Points->
y[v] =
XPnts[anchor].y;
765 for (v = 0; v < Points->
n_points - 1; v++) {
767 double x1, x2, y1, y2, xmin, xmax, ymin, ymax;
769 G_debug(3,
" segment = %d end anchors : %d %d", v,
Index[v],
773 x2 = Points->
x[v + 1];
775 y2 = Points->
y[v + 1];
813 for (i = 0; i <
List->n_values; i++) {
833 if (status == 0 && dist2 <=
thresh2) {
834 G_debug(4,
" anchor in thresh, along = %lf", along);
851 for (i = 0; i <
nnew; i++) {
852 anchor =
New[i].anchor;
912 int line, nlines,
ltype;
920 for (line = 1; line <= nlines; line++) {
968 int i, v, line, nlines;
1013 with_z = (with_z != 0);
1021 point = segment = 1;
1027 for (i = 0; i < nlines; i++) {
1031 G_debug(3,
"line = %d", line);
1038 for (v = 0; v <
LPoints->n_points; v++) {
1039 G_debug(3,
" vertex v = %d", v);
1054 G_debug(3,
"List : nvalues = %d",
List->n_values);
1056 if (
List->n_values == 0) {
1114 for (v = 0; v < Points->
n_points; v++) {
1137 for (i = 0; i <
List->n_values; i++) {
1138 double dx =
List->box[i].E - Points->
x[v];
1139 double dy =
List->box[i].N - Points->
y[v];
1143 dz =
List->box[i].T - Points->
z[v];
1145 tmpdist2 = dx * dx + dy * dy + dz * dz;
1169 for (v = 0; v < Points->
n_points; v++) {
1192 for (i = 0; i <
List->n_values; i++) {
1193 double x1, y1, z1, x2, y2, z2;
1197 segment =
List->id[i];
1200 x1 =
List->box[i].W;
1201 x2 =
List->box[i].E;
1204 x1 =
List->box[i].E;
1205 x2 =
List->box[i].W;
1208 y1 =
List->box[i].S;
1209 y2 =
List->box[i].N;
1212 y1 =
List->box[i].N;
1213 y2 =
List->box[i].S;
1216 z1 =
List->box[i].B;
1217 z2 =
List->box[i].T;
1220 z1 =
List->box[i].T;
1221 z2 =
List->box[i].B;
1226 Points->
x[v], Points->
y[v], Points->
z[v], x1, y1, z1, x2, y2,
1229 if (
tmpdist2 < dist2 && status == 0) {
1254 for (v = 0; v < Points->
n_points - 1; v++) {
1255 double x1, x2, y1, y2, z1, z2;
1256 double xmin, xmax, ymin, ymax, zmin, zmax;
1259 x2 = Points->
x[v + 1];
1261 y2 = Points->
y[v + 1];
1264 z2 = Points->
z[v + 1];
1313 for (i = 0; i <
List->n_values; i++) {
1314 double dist2, along;
1320 if (Points->
x[v] ==
List->box[i].E &&
1321 Points->
y[v] ==
List->box[i].N &&
1322 Points->
z[v] ==
List->box[i].T)
1325 if (Points->
x[v + 1] ==
List->box[i].E &&
1326 Points->
y[v + 1] ==
List->box[i].N &&
1327 Points->
z[v + 1] ==
List->box[i].T)
1332 List->box[i].E,
List->box[i].N,
List->box[i].T, x1, y1, z1, x2,
1335 if (dist2 <=
thresh2 && status == 0) {
1336 G_debug(4,
" anchor in thresh, along = %lf", along);
1356 for (i = 0; i <
nnew; i++) {
void Vect_snap_lines_list(struct Map_info *Map, const struct ilist *List_lines, double thresh, struct Map_info *Err)
Snap selected lines to existing vertex in threshold.
void Vect_snap_lines(struct Map_info *Map, int type, double thresh, struct Map_info *Err)
Snap lines in vector map to existing vertex in threshold.
int Vect_snap_line(struct Map_info *Map, struct ilist *reflist, struct line_pnts *Points, double thresh, int with_z, int *nsnapped, int *ncreated)
Snap a line to reference lines in Map with threshold.
void G_percent(long, long, int)
Print percent complete messages.
void G_free(void *)
Free allocated memory.
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 void void G_important_message(const char *,...) __attribute__((format(printf
void G_ilist_add(struct ilist *, int)
Add item to ilist.
int G_debug(int, const char *,...) __attribute__((format(printf
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)
int Vect_reset_boxlist(struct boxlist *)
Reset boxlist structure.
plus_t Vect_get_num_lines(struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
struct boxlist * Vect_new_boxlist(int)
Creates and initializes a struct boxlist.
void Vect_destroy_boxlist(struct boxlist *)
Frees all memory associated with a struct boxlist, including the struct itself.
void Vect_destroy_list(struct ilist *)
Frees all memory associated with a struct ilist, including the struct itself.
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)
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
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_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
int Vect_reset_list(struct ilist *)
Reset ilist structure.
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
int Vect_append_points(struct line_pnts *, const struct line_pnts *, int)
Appends points to the end of a line.
#define GV_FORWARD
Line direction indicator forward/backward.
double dig_distance2_point_to_line(double, double, double, double, double, double, double, double, double, int, double *, double *, double *, double *, int *)
int dig_boxlist_add(struct boxlist *, int, const struct bound_box *)
Header file for msvc/fcntl.c.
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
struct kdtree * kdtree_create(char ndims, int *btol)
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
void kdtree_destroy(struct kdtree *t)
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
List of bounding boxes with id.
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.
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
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.