23 #include <grass/gis.h>
24 #include <grass/dbmi.h>
25 #include <grass/Vect.h>
26 #include <grass/glocale.h>
41 G_debug(3,
" Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d",
46 if (from != From_node) {
55 G_debug(3,
" EdgeCost += %d (node)", (
int)cost);
61 G_debug(3,
" don't clip first node");
97 const char *ncol,
int geo,
int algorithm)
99 int i, j, from, to, line, nlines, nnodes, ret,
type, cat, skipped, cfound;
101 struct line_pnts *Points;
102 struct line_cats *Cats;
103 double dcost, bdcost, ll;
108 { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
109 struct field_info *Fi;
114 dbCatValArray fvarr, bvarr;
115 int fctype = 0, bctype = 0, nrec;
118 G_debug(1,
"Vect_build_graph(): ltype = %d, afield = %d, nfield = %d",
119 ltype, afield, nfield);
120 G_debug(1,
" afcol = %s, abcol = %s, ncol = %s", afcol, abcol, ncol);
124 Map->graph_line_type = ltype;
133 if (afcol ==
NULL && ll && !geo)
134 Map->cost_multip = 1000000;
136 Map->cost_multip = 1000;
144 Map->edge_fcosts = (
double *)G_malloc((nlines + 1) *
sizeof(double));
145 Map->edge_bcosts = (
double *)G_malloc((nlines + 1) *
sizeof(double));
146 Map->node_costs = (
double *)G_malloc((nnodes + 1) *
sizeof(double));
148 for (i = 1; i <= nlines; i++) {
149 Map->edge_fcosts[i] = -1;
150 Map->edge_bcosts[i] = -1;
152 for (i = 1; i <= nnodes; i++) {
153 Map->node_costs[i] = 0;
180 G_fatal_error(_(
"Database connection not defined for layer %d"),
186 G_fatal_error(_(
"Unable to open database <%s> by driver <%s>"),
187 Fi->database, Fi->driver);
190 if (
db_get_column(driver, Fi->table, afcol, &Column) != DB_OK)
196 if (fctype != DB_C_TYPE_INT && fctype != DB_C_TYPE_DOUBLE)
197 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
204 G_debug(1,
"forward costs: nrec = %d", nrec);
207 if (
db_get_column(driver, Fi->table, abcol, &Column) != DB_OK)
213 if (bctype != DB_C_TYPE_INT && bctype != DB_C_TYPE_DOUBLE)
214 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
221 G_debug(1,
"backward costs: nrec = %d", nrec);
229 for (i = 1; i <= nlines; i++) {
234 if (!(type & ltype & (GV_LINE | GV_BOUNDARY)))
240 "Category of field %d not attached to the line %d -> line skipped",
246 if (fctype == DB_C_TYPE_INT) {
255 G_warning(_(
"Database record for line %d (cat = %d, "
256 "forward/both direction(s)) not found "
257 "(forward/both direction(s) of line skipped)"),
263 if (bctype == DB_C_TYPE_INT) {
274 G_warning(_(
"Database record for line %d (cat = %d, "
275 "backword direction) not found"
276 "(direction of line skipped)"), i, cat);
300 if (dofw && dcost != -1) {
302 G_debug(5,
"Add arc %d from %d to %d cost = %d", i, from, to,
307 Map->edge_fcosts[i] = dcost;
312 G_debug(5,
"bdcost = %f edge_bcosts = %f", bdcost,
313 Map->edge_bcosts[i]);
314 if (dobw && bdcost != -1) {
315 bcost = (
dglInt32_t) Map->cost_multip * bdcost;
316 G_debug(5,
"Add arc %d from %d to %d bcost = %d", -i, to, from,
321 Map->edge_bcosts[i] = bdcost;
327 if (afcol !=
NULL && skipped > 0)
328 G_debug(2,
"%d lines missing category of field %d skipped", skipped,
343 G_debug(2,
"Set nodes' costs");
351 G_fatal_error(_(
"Database connection not defined for layer %d"),
356 G_fatal_error(_(
"Unable to open database <%s> by driver <%s>"),
357 Fi->database, Fi->driver);
360 if (
db_get_column(driver, Fi->table, ncol, &Column) != DB_OK)
366 if (fctype != DB_C_TYPE_INT && fctype != DB_C_TYPE_DOUBLE)
367 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
374 G_debug(1,
"node costs: nrec = %d", nrec);
376 for (i = 1; i <= nnodes; i++) {
381 G_debug(2,
" node = %d nlines = %d", i, nlines);
384 for (j = 0; j < nlines; j++) {
386 G_debug(2,
" line (%d) = %d", j, line);
388 if (!(type & GV_POINT))
392 if (fctype == DB_C_TYPE_INT) {
403 G_warning(_(
"Database record for node %d (cat = %d) not found "
404 "(cost set to 0)"), i, cat);
412 "Category of field %d not attached to any points in node %d"
413 "(costs set to 0)", nfield, i);
422 G_debug(3,
"Set node's cost to %d", cost);
424 Map->node_costs[i] = dcost;
465 struct ilist *List,
double *cost)
467 int i, line, *pclip, cArc, nRet;
472 G_debug(3,
"Vect_net_shortest_path(): from = %d, to = %d", from, to);
494 (
dglInt32_t) to, clipper, pclip, &(Map->spCache));
506 (
dglInt32_t) to, clipper, pclip, &(Map->spCache));
518 *cost = PORT_DOUBLE_MAX;
527 for (i = 0; i < pSPReport->
cArc; i++) {
537 *cost = (double)pSPReport->
nDistance / Map->cost_multip;
539 *cost = (
double)nDistance / Map->cost_multip;
543 cArc = pSPReport->
cArc;
570 G_debug(5,
"Vect_net_get_line_cost(): line = %d, dir = %d", line,
573 if (direction == GV_FORWARD) {
580 if (Map->edge_fcosts[line] == -1) {
585 *cost = Map->edge_fcosts[line];
587 else if (direction == GV_BACKWARD) {
593 if (Map->edge_bcosts[line] == -1) {
598 *cost = Map->edge_bcosts[line];
599 G_debug(5,
"Vect_net_get_line_cost(): edge_bcosts = %f",
600 Map->edge_bcosts[line]);
603 G_fatal_error(_(
"Wrong line direction in Vect_net_get_line_cost()"));
620 G_debug(3,
"Vect_net_get_node_cost(): node = %d", node);
622 *cost = Map->node_costs[node];
624 G_debug(3,
" -> cost = %f", *cost);
648 double x,
double y,
double z,
649 int direction,
double maxdist,
650 int *node1,
int *node2,
int *ln,
double *costs1,
651 double *costs2,
struct line_pnts *Points1,
652 struct line_pnts *Points2,
double *distance)
654 int line, n1, n2, nnodes;
657 static struct line_pnts *Points =
NULL;
658 double cx, cy, cz, c1, c2;
662 G_debug(3,
"Vect_net_nearest_nodes() x = %f y = %f", x, y);
672 *costs1 = PORT_DOUBLE_MAX;
674 *costs2 = PORT_DOUBLE_MAX;
680 *distance = PORT_DOUBLE_MAX;
686 line =
Vect_find_line(Map, x, y, z, Map->graph_line_type, maxdist, 0, 0);
692 npoints = Points->n_points;
696 Vect_line_distance(Points, x, y, z, 0, &cx, &cy, &cz, distance,
NULL,
699 G_debug(4,
"line = %d n1 = %d n2 = %d segment = %d", line, n1, n2,
703 G_debug(4,
"cx = %f cy = %f first = %f %f last = %f %f", cx, cy,
704 Points->x[0], Points->y[0], Points->x[npoints - 1],
705 Points->y[npoints - 1]);
707 if (Points->x[0] == cx && Points->y[0] == cy) {
718 G_debug(3,
"first node nearest");
721 if (Points->x[npoints - 1] == cx && Points->y[npoints - 1] == cy) {
732 G_debug(3,
"last node nearest");
740 if (direction == GV_FORWARD) {
761 if (nnodes == 1 && c1 < 0) {
766 *costs1 = c2 * (length - along) / length;
772 if (direction == GV_FORWARD) {
775 for (i = segment; i < npoints; i++)
780 for (i = npoints - 1; i >= segment; i--)
796 *costs1 = c1 * along / length;
800 *costs2 = c2 * (length - along) / length;
806 if (direction == GV_FORWARD) {
809 for (i = segment - 1; i >= 0; i--)
814 for (i = 0; i < segment; i++)
826 if (direction == GV_FORWARD) {
829 for (i = segment; i < npoints; i++)
834 for (i = npoints - 1; i >= segment; i--)
867 double fx,
double fy,
double fz,
double tx,
868 double ty,
double tz,
double fmax,
double tmax,
869 double *costs,
struct line_pnts *Points,
870 struct ilist *List,
struct line_pnts *FPoints,
871 struct line_pnts *TPoints,
double *fdist,
875 costs, Points, List,
NULL, FPoints, TPoints, fdist, tdist );
899 double fx,
double fy,
double fz,
double tx,
900 double ty,
double tz,
double fmax,
double tmax,
901 double *costs,
struct line_pnts *Points,
902 struct ilist *List,
struct ilist *NodesList,
903 struct line_pnts *FPoints,
904 struct line_pnts *TPoints,
double *fdist,
907 int fnode[2], tnode[2];
908 double fcosts[2], tcosts[2], cur_cst;
909 int nfnodes, ntnodes, fline, tline;
910 static struct line_pnts *APoints, *SPoints, *fPoints[2], *tPoints[2];
911 static struct ilist *LList;
912 static int first = 1;
913 int reachable, shortcut;
914 int i, j,
fn = 0, tn = 0;
918 int from_point_node = 0;
919 int to_point_node = 0;
921 G_debug(3,
"Vect_net_shortest_path_coor()");
936 *costs = PORT_DOUBLE_MAX;
949 if (NodesList !=
NULL)
953 fnode[0] = fnode[1] = tnode[0] = tnode[1] = 0;
957 &(fnode[1]), &fline, &(fcosts[0]),
958 &(fcosts[1]), fPoints[0], fPoints[1], fdist);
962 if ( nfnodes == 1 && fPoints[0]->n_points < 3 ) {
963 from_point_node = fnode[0];
968 &(tnode[0]), &(tnode[1]), &tline, &(tcosts[0]),
969 &(tcosts[1]), tPoints[0], tPoints[1], tdist);
973 if ( ntnodes == 1 && tPoints[0]->n_points < 3 ) {
974 to_point_node = tnode[0];
978 G_debug(3,
"fline = %d tline = %d", fline, tline);
980 reachable = shortcut = 0;
981 cur_cst = PORT_DOUBLE_MAX;
988 if (fline == tline && (nfnodes > 1 || ntnodes > 1)) {
989 double len, flen, tlen, c, fseg, tseg;
990 double fcx, fcy, fcz, tcx, tcy, tcz;
1006 reachable = shortcut = 1;
1008 else if (flen < tlen) {
1011 cur_cst = c * (tlen - flen) / len;
1015 for (i = fseg; i < tseg; i++)
1022 reachable = shortcut = 1;
1028 cur_cst = c * (flen - tlen) / len;
1032 for (i = fseg - 1; i >= tseg; i--)
1039 reachable = shortcut = 1;
1045 for (i = 0; i < nfnodes; i++) {
1046 for (j = 0; j < ntnodes; j++) {
1050 G_debug(3,
"i = %d fnode = %d j = %d tnode = %d", i, fnode[i], j,
1058 cst = fcosts[i] + ncst + tcosts[j];
1059 if (reachable == 0 || cst < cur_cst) {
1069 G_debug(3,
"reachable = %d shortcut = %d cur_cst = %f", reachable,
1080 if (from_point_node > 0)
1083 if (to_point_node > 0)
1092 if (from_point_node > 0 && from_point_node != fnode[fn]) {
1102 G_debug(3,
"Number of lines %d", LList->n_values);
1110 for (i = 0; i < LList->n_values; i++) {
1113 line = LList->value[i];
1114 G_debug(3,
"i = %d line = %d", i, line);
1125 int node, node1, node2;
1147 if (to_point_node > 0 && to_point_node != tnode[tn]) {