34 G_debug(3,
" Edge = %d NodeFrom = %d NodeTo = %d edge cost = %d",
39 if (from != From_node) {
48 G_debug(3,
" EdgeCost += %d (node)", (
int)cost);
54 G_debug(3,
" don't clip first node");
63 static int convert_dgl_shortest_path_result(
struct Map_info *Map,
71 for (i = 0; i < pSPReport->
cArc; i++) {
85 static int ttb_convert_dgl_shortest_path_result(
struct Map_info *Map,
90 int i, line_id,
type, tucfield_idx;
97 for (i = 0; i < pSPReport->
cArc; i++) {
106 if (line_ucat % 2 == 1)
107 line_ucat = ((line_ucat - 1) / -2);
109 line_ucat = (line_ucat) / 2;
113 (Map, tucfield_idx, abs(line_ucat),
GV_LINE, 0, &
type,
139 static int find_shortest_path(
struct Map_info *Map,
int from,
int to,
140 struct ilist *List,
double *cost,
int UseTtb,
143 int *pclip, cArc, nRet;
148 G_debug(3,
"find_shortest_path(): from = %d, to = %d", from, to);
190 clipper, pclip,
NULL);
208 ttb_convert_dgl_shortest_path_result(Map, pSPReport, tucfield,
211 convert_dgl_shortest_path_result(Map, pSPReport, List);
222 cArc = pSPReport->
cArc;
256 int tucfield,
struct ilist *List,
double *cost)
263 int i_line, line, type, cfound;
268 if (from_type == 0) {
278 for (i_line = 0; i_line < box_List->
n_values; i_line++) {
279 line = box_List->
id[i_line];
291 (
"Unable to find point with defined unique category for node <%d>."),
295 (
"There exists more than one point on node <%d> with unique category in field <%d>.\n" 296 "The unique category layer may not be valid."),
299 G_debug(2,
"from node = %d, unique cat = %d ", from, f);
307 G_debug(2,
"from edge unique cat = %d", from);
320 for (i_line = 0; i_line < box_List->
n_values; i_line++) {
321 line = box_List->
id[i_line];
332 (
"Unable to find point with defined unique category for node <%d>."),
336 (
"There exists more than one point on node <%d> with unique category in field <%d>.\n" 337 "The unique category layer may not be valid."),
340 G_debug(2,
"to node = %d, unique cat = %d ", to, t);
348 G_debug(2,
"to edge unique cat = %d", to);
354 return find_shortest_path(Map, f, t, List, cost, 1, tucfield);
377 struct ilist *List,
double *cost)
379 return find_shortest_path(Map, from, to, List, cost, 0, -1);
417 G_debug(5,
"Vect_net_get_line_cost(): line = %d, dir = %d", line,
448 G_debug(5,
"Vect_net_get_line_cost(): edge_bcosts = %f",
452 G_fatal_error(
_(
"Wrong line direction in Vect_net_get_line_cost()"));
469 G_debug(3,
"Vect_net_get_node_cost(): node = %d", node);
473 G_debug(3,
" -> cost = %f", *cost);
498 double x,
double y,
double z,
499 int direction,
double maxdist,
500 int *node1,
int *node2,
int *ln,
double *costs1,
501 double *costs2,
struct line_pnts *Points1,
502 struct line_pnts *Points2,
double *distance)
504 int line, n1, n2, nnodes;
508 double cx, cy, cz, c1, c2;
512 G_debug(3,
"Vect_net_nearest_nodes() x = %f y = %f", x, y);
546 Vect_line_distance(Points, x, y, z, 0, &cx, &cy, &cz, distance,
NULL,
549 G_debug(4,
"line = %d n1 = %d n2 = %d segment = %d", line, n1, n2,
553 G_debug(4,
"cx = %f cy = %f first = %f %f last = %f %f", cx, cy,
554 Points->
x[0], Points->
y[0], Points->
x[npoints - 1],
555 Points->
y[npoints - 1]);
557 if (Points->
x[0] == cx && Points->
y[0] == cy) {
568 G_debug(3,
"first node nearest");
571 if (Points->
x[npoints - 1] == cx && Points->
y[npoints - 1] == cy) {
582 G_debug(3,
"last node nearest");
611 if (nnodes == 1 && c1 < 0) {
616 *costs1 = c2 * (length - along) / length;
625 for (i = segment; i < npoints; i++)
630 for (i = npoints - 1; i >= segment; i--)
646 *costs1 = c1 * along / length;
650 *costs2 = c2 * (length - along) / length;
659 for (i = segment - 1; i >= 0; i--)
664 for (i = 0; i < segment; i++)
679 for (i = segment; i < npoints; i++)
684 for (i = npoints - 1; i >= segment; i--)
719 find_shortest_path_coor(
struct Map_info *Map,
720 double fx,
double fy,
double fz,
double tx,
721 double ty,
double tz,
double fmax,
double tmax,
722 int UseTtb,
int tucfield,
726 struct line_pnts *TPoints,
double *fdist,
729 int fnode[2], tnode[2];
730 double fcosts[2], tcosts[2], cur_cst;
731 int nfnodes, ntnodes, fline, tline;
732 static struct line_pnts *APoints, *SPoints, *fPoints[2], *tPoints[2];
733 static struct ilist *LList;
734 static int first = 1;
735 int reachable, shortcut;
736 int i, j, fn = 0, tn = 0;
740 int from_point_node = 0;
741 int to_point_node = 0;
743 G_debug(3,
"Vect_net_shortest_path_coor()");
771 if (NodesList !=
NULL)
775 fnode[0] = fnode[1] = tnode[0] = tnode[1] = 0;
779 &(fnode[1]), &fline, &(fcosts[0]),
780 &(fcosts[1]), fPoints[0], fPoints[1], fdist);
784 if (nfnodes == 1 && fPoints[0]->n_points < 3) {
785 from_point_node = fnode[0];
790 &(tnode[0]), &(tnode[1]), &tline, &(tcosts[0]),
791 &(tcosts[1]), tPoints[0], tPoints[1], tdist);
795 if (ntnodes == 1 && tPoints[0]->n_points < 3) {
796 to_point_node = tnode[0];
800 G_debug(3,
"fline = %d tline = %d", fline, tline);
802 reachable = shortcut = 0;
810 if (fline == tline && (nfnodes > 1 || ntnodes > 1)) {
811 double len, flen, tlen, c, fseg, tseg;
812 double fcx, fcy, fcz, tcx, tcy, tcz;
833 reachable = shortcut = 1;
835 else if (flen < tlen) {
838 cur_cst = c * (tlen - flen) / len;
842 for (i = fseg; i < tseg; i++)
849 reachable = shortcut = 1;
855 cur_cst = c * (flen - tlen) / len;
859 for (i = fseg - 1; i >= tseg; i--)
866 reachable = shortcut = 1;
872 for (i = 0; i < nfnodes; i++) {
873 for (j = 0; j < ntnodes; j++) {
877 G_debug(3,
"i = %d fnode = %d j = %d tnode = %d", i, fnode[i], j,
883 tucfield,
NULL, &ncst);
891 cst = fcosts[i] + ncst + tcosts[j];
892 if (reachable == 0 || cst < cur_cst) {
902 G_debug(3,
"reachable = %d shortcut = %d cur_cst = %f", reachable,
911 if (from_point_node > 0)
914 if (to_point_node > 0)
923 if (from_point_node > 0 && from_point_node != fnode[fn]) {
933 tucfield, LList,
NULL);
946 for (i = 0; i < LList->
n_values; i++) {
949 line = LList->
value[i];
950 G_debug(3,
"i = %d line = %d", i, line);
962 int node, node1, node2;
988 if (to_point_node > 0 && to_point_node != tnode[tn]) {
1024 double fx,
double fy,
double fz,
double tx,
1025 double ty,
double tz,
double fmax,
double tmax,
1026 double *costs,
struct line_pnts *Points,
1029 struct line_pnts *TPoints,
double *fdist,
1032 return find_shortest_path_coor(Map, fx, fy, fz, tx, ty, tz, fmax, tmax, 0,
1033 0, costs, Points, List, NodesList,
1034 FPoints, TPoints, fdist, tdist);
1059 double fx,
double fy,
double fz,
double tx,
1060 double ty,
double tz,
double fmax,
1061 double tmax,
int tucfield,
1062 double *costs,
struct line_pnts *Points,
1065 struct line_pnts *TPoints,
double *fdist,
1068 return find_shortest_path_coor(Map, fx, fy, fz, tx, ty, tz, fmax, tmax,
1069 1, tucfield, costs, Points, List,
1070 NodesList, FPoints, TPoints, fdist, tdist);
void Vect_destroy_boxlist(struct boxlist *)
Frees all memory associated with a struct boxlist, including the struct itself.
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.
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
int Vect_cidx_find_next(const struct Map_info *, int, int, int, int, int *, int *)
Find next line/area id for given category, start_index and type_mask.
int Vect_reset_list(struct ilist *)
Reset ilist structure.
int Vect_net_shortest_path(struct Map_info *Map, int from, int to, struct ilist *List, double *cost)
Find shortest path.
dglInt32_t dglNodeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnNode)
int n_points
Number of points.
dglInt32_t dglEdgeGet_Cost(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int n_values
Number of values in the list.
double * edge_fcosts
Forward costs used for graph.
int Vect_line_distance(const struct line_pnts *, double, double, double, int, double *, double *, double *, double *, double *, double *)
Calculate distance of point to line.
dglInt32_t * dglEdgeGet_Head(dglGraph_s *pGraph, dglInt32_t *pnEdge)
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
double Vect_line_length(const struct line_pnts *)
Calculate line length, 3D-length in case of 3D vector line.
double * edge_bcosts
backward costs used for graph
int n_values
Number of items in the list.
#define GV_POINT
Feature types used in memory on run time (may change)
int Vect_find_line(struct Map_info *, double, double, double, int, double, int, int)
Find the nearest line.
int Vect_get_node_coor(const struct Map_info *, int, double *, double *, double *)
Get node coordinates.
struct Graph_info dgraph
Graph info (built for network analysis)
double * x
Array of X coordinates.
Feature geometry info - coordinates.
int Vect_select_lines_by_box(struct Map_info *, const struct bound_box *, int, struct boxlist *)
Select lines with bounding boxes by box.
char * dglStrerror(dglGraph_s *pgraph)
dglGraph_s graph_s
Graph structure.
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
int Vect_net_get_line_cost(const struct Map_info *Map, int line, int direction, double *cost)
Returns in cost for given direction in *cost.
int Vect_net_shortest_path_coor(struct Map_info *Map, double fx, double fy, double fz, double tx, double ty, double tz, double fmax, double tmax, double *costs, struct line_pnts *Points, struct ilist *List, struct ilist *NodesList, struct line_pnts *FPoints, struct line_pnts *TPoints, double *fdist, double *tdist)
Find shortest path on network between 2 points given by coordinates.
int dglShortestDistance(dglGraph_s *pGraph, dglInt32_t *pnDistance, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
dglSPCache_s spCache
Shortest path cache.
int Vect_get_line_nodes(const struct Map_info *, int, int *, int *)
Get line nodes.
#define PORT_DOUBLE_MAX
Limits for portable types.
double * y
Array of Y coordinates.
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
List of bounding boxes with id.
void G_warning(const char *,...) __attribute__((format(printf
int cost_multip
Edge and node costs multiplicator.
int Vect_net_get_node_cost(const struct Map_info *Map, int node, double *cost)
Get cost of node.
dglInt32_t * dglNodeGet_Attr(dglGraph_s *pGraph, dglInt32_t *pnNode)
double * z
Array of Z coordinates.
int Vect_net_ttb_shortest_path_coor(struct Map_info *Map, double fx, double fy, double fz, double tx, double ty, double tz, double fmax, double tmax, int tucfield, double *costs, struct line_pnts *Points, struct ilist *List, struct ilist *NodesList, struct line_pnts *FPoints, struct line_pnts *TPoints, double *fdist, double *tdist)
Find shortest path on network with turntable between 2 points given by coordinates.
int * value
Array of values.
struct boxlist * Vect_new_boxlist(int)
Creates and initializes a struct boxlist.
int Vect_net_nearest_nodes(struct Map_info *Map, double x, double y, double z, int direction, double maxdist, int *node1, int *node2, int *ln, double *costs1, double *costs2, struct line_pnts *Points1, struct line_pnts *Points2, double *distance)
Find nearest node(s) on network.
double * node_costs
Node costs used for graph.
int Vect_cidx_get_field_index(const struct Map_info *, int)
Get layer index for given layer number.
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int Vect_net_ttb_shortest_path(struct Map_info *Map, int from, int from_type, int to, int to_type, int tucfield, struct ilist *List, double *cost)
Find shortest path on network.
dglGraph_s * Vect_net_get_graph(struct Map_info *Map)
Get graph structure.
int G_debug(int, const char *,...) __attribute__((format(printf
int line_type
Line type used to build the graph.
dglInt32_t dglEdgeGet_Id(dglGraph_s *pGraph, dglInt32_t *pnEdge)
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)
int Vect_cat_get(const struct line_cats *, int, int *)
Get first found category of given field.
int dglGet_NodeAttrSize(dglGraph_s *pgraph)
int dglShortestPath(dglGraph_s *pGraph, dglSPReport_s **ppReport, dglInt32_t nStart, dglInt32_t nDestination, dglSPClip_fn fnClip, void *pvClipArg, dglSPCache_s *pCache)
void Vect_reset_line(struct line_pnts *)
Reset line.