GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-2653d7b383
plus_node.c
Go to the documentation of this file.
1 /**
2  * \file plus_node.c
3  *
4  * \brief Vector library - update topo for nodes (lower level functions)
5  *
6  * Lower level functions for reading/writing/manipulating vectors.
7  *
8  * This program is free software under the GNU General Public License
9  * (>=v2). Read the file COPYING that comes with GRASS for details.
10  *
11  * \author CERL (probably Dave Gerdes), Radim Blazek
12  *
13  * \date 2001-2006
14  */
15 
16 #include <stdlib.h>
17 #include <math.h>
18 #include <grass/vector.h>
19 #include <grass/glocale.h>
20 
21 static double dist_squared(double, double, double, double);
22 
23 /*!
24  * \brief Add line info to node
25  *
26  * Line will be negative if END node
27  *
28  * 'node' must of course already exist space will be allocated to add 'line' to
29  * array
30  *
31  * Lines are sorted in increasing angle order and
32  * degenerated lines are set to -9 (ignored).
33  *
34  * \param[in] plus pointer to Plus_head structure
35  * \param[in] nodeid node id
36  * \param[in] lineid line id
37  * \param[in] points line geometry
38  * \param[in] type line type
39  *
40  * \return -1 on error
41  * \return 0 line not added (degenerate)
42  * \return new number of lines in node
43  */
44 int dig_node_add_line(struct Plus_head *plus, int nodeid, int lineid,
45  const struct line_pnts *points, int type)
46 {
47  register int i;
48  float angle;
49  int ret;
50  struct P_node *node;
51 
52  G_debug(3, "dig_node_add_line(): node = %d line = %d", nodeid, lineid);
53 
54  node = plus->Node[nodeid];
55 
56  /* reallocate memory */
57  ret = dig_node_alloc_line(node, 1);
58  if (ret == -1)
59  return -1;
60 
61  angle = -9.;
62  if (type & GV_LINES) {
63  if (lineid < 0)
64  angle = dig_calc_end_angle(points, 0);
65  else
66  angle = dig_calc_begin_angle(points, 0);
67  }
68  G_debug(3, " angle = %f", angle);
69 
70  i = node->n_lines;
71  while (i > 0) {
72  if (angle >= node->angles[i - 1])
73  break;
74  node->angles[i] = node->angles[i - 1];
75  node->lines[i] = node->lines[i - 1];
76 
77  i--;
78  }
79  node->angles[i] = angle;
80  node->lines[i] = lineid;
81 
82  node->n_lines++;
83 
84  G_debug(
85  3,
86  "dig_node_add_line(): line %d added position %d n_lines: %d angle %f",
87  lineid, i, node->n_lines, angle);
88 
89  return ((int)node->n_lines);
90 }
91 
92 /*!
93  * \brief Add new node to plus structure
94  *
95  * \param[in] plus pointer to Plus_head structure
96  * \param[in] x,y,z coordinates
97  *
98  * \return -1 on error
99  * \return number of node
100  */
101 int dig_add_node(struct Plus_head *plus, double x, double y, double z)
102 {
103  int nnum;
104  struct P_node *node;
105 
106  /* First look if we have space in array of pointers to nodes
107  * and reallocate if necessary */
108  G_debug(3, "dig_add_node(): n_nodes = %d, alloc_nodes = %d", plus->n_nodes,
109  plus->alloc_nodes);
110  if (plus->n_nodes >= plus->alloc_nodes) { /* array is full */
111  if (dig_alloc_nodes(plus, 1000) == -1)
112  return -1;
113  }
114 
115  /* allocate node structure */
116  nnum = plus->n_nodes + 1;
117 
118  plus->Node[nnum] = dig_alloc_node();
119 
120  node = plus->Node[nnum];
121  node->x = x;
122  node->y = y;
123  node->z = z;
124 
125  dig_spidx_add_node(plus, nnum, x, y, z);
126 
127  plus->n_nodes++;
128 
129  G_debug(3, "new node = %d, n_nodes = %d, alloc_nodes = %d", nnum,
130  plus->n_nodes, plus->alloc_nodes);
131 
132  return (nnum);
133 }
134 
135 /*!
136  * \brief Return actual index into node arrays of the first set of matching
137  * coordinates
138  *
139  * \param[in] plus pointer to Plus_head structure
140  * \param[in] x,y coordinates
141  * \param[in] thresh threshold value
142  *
143  * \return node index
144  * \return -1 if no node found
145  */
146 int dig_which_node(struct Plus_head *plus, double x, double y, double thresh)
147 {
148  register int i;
149  register int first_time;
150  register int have_match;
151  int winner;
152  double least_dist, dist;
153  struct P_node *node;
154 
155  first_time = 1;
156  have_match = 0;
157  winner = 0;
158  least_dist = 0.0;
159  for (i = 1; i <= plus->n_nodes; i++) {
160  if (plus->Node[i] == NULL)
161  continue;
162 
163  node = plus->Node[i];
164  if ((fabs(node->x - x) <= thresh) && (fabs(node->y - y) <= thresh)) {
165  dist = dist_squared(x, y, node->x, node->y);
166  if (first_time) {
167  least_dist = dist;
168  first_time = 0;
169  winner = i;
170  have_match = 1;
171  }
172  if (dist < least_dist) {
173  least_dist = dist;
174  winner = i;
175  }
176  }
177  }
178 
179  if (!have_match)
180  return (-1);
181 
182  return (winner);
183 } /* which_node () */
184 
185 /*!
186  * \brief Return line angle
187  *
188  * Lines is specified by line id in topology, NOT by order number.
189  * Negative id if looking for line end point.
190  *
191  * \param[in] plus pointer to Plus_head structure
192  * \param[in] nodeid node id
193  * \param[in] lineid line id
194  *
195  * \return line angle <-PI,PI>
196  * \return 0 not reached
197  */
198 float dig_node_line_angle(struct Plus_head *plus, int nodeid, int lineid)
199 {
200  int i, nlines;
201  struct P_node *node;
202 
203  G_debug(3, "dig_node_line_angle: node = %d line = %d", nodeid, lineid);
204 
205  node = plus->Node[nodeid];
206  nlines = node->n_lines;
207 
208  for (i = 0; i < nlines; i++) {
209  if (node->lines[i] == lineid)
210  return (node->angles[i]);
211  }
212 
213  G_fatal_error(_("Attempt to read line angle for the line which is not "
214  "connected to the node: "
215  "node %d, line %d"),
216  nodeid, lineid);
217 
218  return 0.0; /* not reached */
219 }
220 
221 static double dist_squared(double x1, double y1, double x2, double y2)
222 {
223  double dx, dy;
224 
225  dx = x1 - x2;
226  dy = y1 - y2;
227  return (dx * dx + dy * dy);
228 }
#define NULL
Definition: ccmath.h:32
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
int G_debug(int, const char *,...) __attribute__((format(printf
#define GV_LINES
Definition: dig_defines.h:193
int dig_alloc_nodes(struct Plus_head *, int)
Reallocate array of pointers to nodes.
Definition: struct_alloc.c:105
int dig_spidx_add_node(struct Plus_head *, int, double, double, double)
Add new node to spatial index.
Definition: spindex.c:291
float dig_calc_begin_angle(const struct line_pnts *, double)
Definition: angle.c:31
int dig_node_alloc_line(struct P_node *, int)
Allocate space in P_node struct.
Definition: struct_alloc.c:69
float dig_calc_end_angle(const struct line_pnts *, double)
Definition: angle.c:83
struct P_node * dig_alloc_node(void)
Allocate new node structure.
Definition: struct_alloc.c:30
#define _(str)
Definition: glocale.h:10
float dig_node_line_angle(struct Plus_head *plus, int nodeid, int lineid)
Return line angle.
Definition: plus_node.c:198
int dig_which_node(struct Plus_head *plus, double x, double y, double thresh)
Return actual index into node arrays of the first set of matching coordinates.
Definition: plus_node.c:146
int dig_add_node(struct Plus_head *plus, double x, double y, double z)
Add new node to plus structure.
Definition: plus_node.c:101
int dig_node_add_line(struct Plus_head *plus, int nodeid, int lineid, const struct line_pnts *points, int type)
Add line info to node.
Definition: plus_node.c:44
Topological feature - node.
Definition: dig_structs.h:1433
double x
X coordinate.
Definition: dig_structs.h:1437
plus_t n_lines
Number of attached lines (size of lines, angle)
Definition: dig_structs.h:1456
float * angles
List of angles of connected lines.
Definition: dig_structs.h:1472
plus_t * lines
List of connected lines.
Definition: dig_structs.h:1463
double z
Z coordinate (used only for 3D data)
Definition: dig_structs.h:1445
double y
Y coordinate.
Definition: dig_structs.h:1441
Basic topology-related info.
Definition: dig_structs.h:769
plus_t n_nodes
Current number of topological features derived from vector geometries.
Definition: dig_structs.h:923
plus_t alloc_nodes
Number of allocated nodes.
Definition: dig_structs.h:958
struct P_node ** Node
Array of nodes.
Definition: dig_structs.h:867
Feature geometry info - coordinates.
Definition: dig_structs.h:1651
#define x