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;
107 { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
108 struct field_info *Fi;
113 dbCatValArray fvarr, bvarr;
114 int fctype = 0, bctype = 0, nrec;
117 G_debug(1,
"Vect_build_graph(): ltype = %d, afield = %d, nfield = %d",
118 ltype, afield, nfield);
119 G_debug(1,
" afcol = %s, abcol = %s, ncol = %s", afcol, abcol, ncol);
123 Map->graph_line_type = ltype;
132 if (afcol ==
NULL && ll && !geo)
133 Map->cost_multip = 1000000;
135 Map->cost_multip = 1000;
143 Map->edge_fcosts = (
double *)G_malloc((nlines + 1) *
sizeof(double));
144 Map->edge_bcosts = (
double *)G_malloc((nlines + 1) *
sizeof(double));
145 Map->node_costs = (
double *)G_malloc((nnodes + 1) *
sizeof(double));
147 for (i = 1; i <= nlines; i++) {
148 Map->edge_fcosts[i] = -1;
149 Map->edge_bcosts[i] = -1;
151 for (i = 1; i <= nnodes; i++) {
152 Map->node_costs[i] = 0;
179 G_fatal_error(_(
"Database connection not defined for layer %d"),
185 G_fatal_error(_(
"Unable to open database <%s> by driver <%s>"),
186 Fi->database, Fi->driver);
189 if (
db_get_column(driver, Fi->table, afcol, &Column) != DB_OK)
195 if (fctype != DB_C_TYPE_INT && fctype != DB_C_TYPE_DOUBLE)
196 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
203 G_debug(1,
"forward costs: nrec = %d", nrec);
206 if (
db_get_column(driver, Fi->table, abcol, &Column) != DB_OK)
212 if (bctype != DB_C_TYPE_INT && bctype != DB_C_TYPE_DOUBLE)
213 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
220 G_debug(1,
"backward costs: nrec = %d", nrec);
228 for (i = 1; i <= nlines; i++) {
233 if (!(type & ltype & (GV_LINE | GV_BOUNDARY)))
239 "Category of field %d not attached to the line %d -> line skipped",
245 if (fctype == DB_C_TYPE_INT) {
254 G_warning(_(
"Database record for line %d (cat = %d, "
255 "forward/both direction(s)) not found "
256 "(forward/both direction(s) of line skipped)"),
262 if (bctype == DB_C_TYPE_INT) {
273 G_warning(_(
"Database record for line %d (cat = %d, "
274 "backword direction) not found"
275 "(direction of line skipped)"), i, cat);
299 if (dofw && dcost != -1) {
301 G_debug(5,
"Add arc %d from %d to %d cost = %d", i, from, to,
306 Map->edge_fcosts[i] = dcost;
311 G_debug(5,
"bdcost = %f edge_bcosts = %f", bdcost,
312 Map->edge_bcosts[i]);
313 if (dobw && bdcost != -1) {
314 bcost = (
dglInt32_t) Map->cost_multip * bdcost;
315 G_debug(5,
"Add arc %d from %d to %d bcost = %d", -i, to, from,
320 Map->edge_bcosts[i] = bdcost;
326 if (afcol !=
NULL && skipped > 0)
327 G_debug(2,
"%d lines missing category of field %d skipped", skipped,
342 G_debug(2,
"Set nodes' costs");
350 G_fatal_error(_(
"Database connection not defined for layer %d"),
355 G_fatal_error(_(
"Unable to open database <%s> by driver <%s>"),
356 Fi->database, Fi->driver);
359 if (
db_get_column(driver, Fi->table, ncol, &Column) != DB_OK)
365 if (fctype != DB_C_TYPE_INT && fctype != DB_C_TYPE_DOUBLE)
366 G_fatal_error(_(
"Data type of column <%s> not supported (must be numeric)"),
373 G_debug(1,
"node costs: nrec = %d", nrec);
375 for (i = 1; i <= nnodes; i++) {
380 G_debug(2,
" node = %d nlines = %d", i, nlines);
383 for (j = 0; j < nlines; j++) {
385 G_debug(2,
" line (%d) = %d", j, line);
387 if (!(type & GV_POINT))
391 if (fctype == DB_C_TYPE_INT) {
402 G_warning(_(
"Database record for node %d (cat = %d) not found "
403 "(cost set to 0)"), i, cat);
411 "Category of field %d not attached to any points in node %d"
412 "(costs set to 0)", nfield, i);
420 G_debug(3,
"Set node's cost to %d", cost);
423 Map->node_costs[i] = dcost;
464 struct ilist *List,
double *cost)
466 int i, line, *pclip, cArc, nRet;
471 G_debug(3,
"Vect_net_shortest_path(): from = %d, to = %d", from, to);
493 (
dglInt32_t) to, clipper, pclip, &(Map->spCache));
505 (
dglInt32_t) to, clipper, pclip, &(Map->spCache));
517 *cost = PORT_DOUBLE_MAX;
526 for (i = 0; i < pSPReport->
cArc; i++) {
536 *cost = (double)pSPReport->
nDistance / Map->cost_multip;
538 *cost = (
double)nDistance / Map->cost_multip;
542 cArc = pSPReport->
cArc;
569 G_debug(5,
"Vect_net_get_line_cost(): line = %d, dir = %d", line,
572 if (direction == GV_FORWARD) {
579 if (Map->edge_fcosts[line] == -1) {
584 *cost = Map->edge_fcosts[line];
586 else if (direction == GV_BACKWARD) {
592 if (Map->edge_bcosts[line] == -1) {
597 *cost = Map->edge_bcosts[line];
598 G_debug(5,
"Vect_net_get_line_cost(): edge_bcosts = %f",
599 Map->edge_bcosts[line]);
602 G_fatal_error(_(
"Wrong line direction in Vect_net_get_line_cost()"));
619 G_debug(3,
"Vect_net_get_node_cost(): node = %d", node);
621 *cost = Map->node_costs[node];
623 G_debug(3,
" -> cost = %f", *cost);
647 double x,
double y,
double z,
648 int direction,
double maxdist,
649 int *node1,
int *node2,
int *ln,
double *costs1,
650 double *costs2,
struct line_pnts *Points1,
651 struct line_pnts *Points2,
double *distance)
653 int line, n1, n2, nnodes;
656 static struct line_pnts *Points =
NULL;
657 double cx, cy, cz, c1, c2;
661 G_debug(3,
"Vect_net_nearest_nodes() x = %f y = %f", x, y);
671 *costs1 = PORT_DOUBLE_MAX;
673 *costs2 = PORT_DOUBLE_MAX;
679 *distance = PORT_DOUBLE_MAX;
685 line =
Vect_find_line(Map, x, y, z, Map->graph_line_type, maxdist, 0, 0);
691 npoints = Points->n_points;
695 Vect_line_distance(Points, x, y, z, 0, &cx, &cy, &cz, distance,
NULL,
698 G_debug(4,
"line = %d n1 = %d n2 = %d segment = %d", line, n1, n2,
702 G_debug(4,
"cx = %f cy = %f first = %f %f last = %f %f", cx, cy,
703 Points->x[0], Points->y[0], Points->x[npoints - 1],
704 Points->y[npoints - 1]);
706 if (Points->x[0] == cx && Points->y[0] == cy) {
717 G_debug(3,
"first node nearest");
720 if (Points->x[npoints - 1] == cx && Points->y[npoints - 1] == cy) {
731 G_debug(3,
"last node nearest");
739 if (direction == GV_FORWARD) {
760 if (nnodes == 1 && c1 < 0) {
765 *costs1 = c2 * (length - along) / length;
771 if (direction == GV_FORWARD) {
774 for (i = segment; i < npoints; i++)
779 for (i = npoints - 1; i >= segment; i--)
795 *costs1 = c1 * along / length;
799 *costs2 = c2 * (length - along) / length;
805 if (direction == GV_FORWARD) {
808 for (i = segment - 1; i >= 0; i--)
813 for (i = 0; i < segment; i++)
825 if (direction == GV_FORWARD) {
828 for (i = segment; i < npoints; i++)
833 for (i = npoints - 1; i >= segment; i--)
866 double fx,
double fy,
double fz,
double tx,
867 double ty,
double tz,
double fmax,
double tmax,
868 double *costs,
struct line_pnts *Points,
869 struct ilist *List,
struct line_pnts *FPoints,
870 struct line_pnts *TPoints,
double *fdist,
874 costs, Points, List,
NULL, FPoints, TPoints, fdist, tdist );
898 double fx,
double fy,
double fz,
double tx,
899 double ty,
double tz,
double fmax,
double tmax,
900 double *costs,
struct line_pnts *Points,
901 struct ilist *List,
struct ilist *NodesList,
902 struct line_pnts *FPoints,
903 struct line_pnts *TPoints,
double *fdist,
906 int fnode[2], tnode[2];
907 double fcosts[2], tcosts[2], cur_cst;
908 int nfnodes, ntnodes, fline, tline;
909 static struct line_pnts *APoints, *SPoints, *fPoints[2], *tPoints[2];
910 static struct ilist *LList;
911 static int first = 1;
912 int reachable, shortcut;
913 int i, j,
fn = 0, tn = 0;
917 int from_point_node = 0;
918 int to_point_node = 0;
920 G_debug(3,
"Vect_net_shortest_path_coor()");
935 *costs = PORT_DOUBLE_MAX;
948 if (NodesList !=
NULL)
952 fnode[0] = fnode[1] = tnode[0] = tnode[1] = 0;
956 &(fnode[1]), &fline, &(fcosts[0]),
957 &(fcosts[1]), fPoints[0], fPoints[1], fdist);
961 if ( nfnodes == 1 && fPoints[0]->n_points < 3 ) {
962 from_point_node = fnode[0];
967 &(tnode[0]), &(tnode[1]), &tline, &(tcosts[0]),
968 &(tcosts[1]), tPoints[0], tPoints[1], tdist);
972 if ( ntnodes == 1 && tPoints[0]->n_points < 3 ) {
973 to_point_node = tnode[0];
977 G_debug(3,
"fline = %d tline = %d", fline, tline);
979 reachable = shortcut = 0;
980 cur_cst = PORT_DOUBLE_MAX;
987 if (fline == tline && (nfnodes > 1 || ntnodes > 1)) {
988 double len, flen, tlen, c, fseg, tseg;
989 double fcx, fcy, fcz, tcx, tcy, tcz;
1005 reachable = shortcut = 1;
1007 else if (flen < tlen) {
1010 cur_cst = c * (tlen - flen) / len;
1014 for (i = fseg; i < tseg; i++)
1021 reachable = shortcut = 1;
1027 cur_cst = c * (flen - tlen) / len;
1031 for (i = fseg - 1; i >= tseg; i--)
1038 reachable = shortcut = 1;
1044 for (i = 0; i < nfnodes; i++) {
1045 for (j = 0; j < ntnodes; j++) {
1049 G_debug(3,
"i = %d fnode = %d j = %d tnode = %d", i, fnode[i], j,
1057 cst = fcosts[i] + ncst + tcosts[j];
1058 if (reachable == 0 || cst < cur_cst) {
1068 G_debug(3,
"reachable = %d shortcut = %d cur_cst = %f", reachable,
1079 if (from_point_node > 0)
1082 if (to_point_node > 0)
1091 if (from_point_node > 0 && from_point_node != fnode[fn]) {
1101 G_debug(3,
"Number of lines %d", LList->n_values);
1109 for (i = 0; i < LList->n_values; i++) {
1112 line = LList->value[i];
1113 G_debug(3,
"i = %d line = %d", i, line);
1124 int node, node1, node2;
1146 if (to_point_node > 0 && to_point_node != tnode[tn]) {