76 static int cmp_cross(
const void *pa,
const void *pb);
77 static void add_cross(
int asegment,
double adistance,
int bsegment,
78 double bdistance,
double x,
double y);
79 static double dist2(
double x1,
double y1,
double x2,
double y2);
81 static int debug_level = -1;
84 static int ident(
double x1,
double y1,
double x2,
double y2,
double thresh);
86 static int cross_seg(
int id,
const struct RTree_Rect *rect,
void *arg);
87 static int find_cross(
int id,
const struct RTree_Rect *rect,
void *arg);
91 #define D ((ax2-ax1)*(by1-by2) - (ay2-ay1)*(bx1-bx2)) 92 #define D1 ((bx1-ax1)*(by1-by2) - (by1-ay1)*(bx1-bx2)) 93 #define D2 ((ax2-ax1)*(by1-ay1) - (ay2-ay1)*(bx1-ax1)) 112 double ay2,
double az2,
double bx1,
double by1,
113 double bz1,
double bx2,
double by2,
double bz2,
114 double *x1,
double *y1,
double *z1,
double *x2,
115 double *y2,
double *z2,
int with_z)
117 static int first_3d = 1;
118 double d, d1, d2, r1, dtol,
t;
124 G_debug(4,
"Vect_segment_intersection()");
125 G_debug(4,
" %.15g , %.15g - %.15g , %.15g", ax1, ay1, ax2, ay2);
126 G_debug(4,
" %.15g , %.15g - %.15g , %.15g", bx1, by1, bx2, by2);
129 if (with_z && first_3d) {
130 G_warning(
_(
"3D not supported by Vect_segment_intersection()"));
146 else if (bx2 == bx1) {
166 else if (ax2 == ax1) {
184 if (ax1 == bx1 && ay1 == by1 && ax2 == bx2 && ay2 == by2) {
185 G_debug(2,
" -> identical segments");
200 else if (bx1 == ax1) {
203 else if (bx2 == ax2) {
206 else if (by1 == ay1) {
240 G_debug(2,
"Vect_segment_intersection(): d = %f, d1 = %f, d2 = %f", d, d1,
244 if (ax1 == bx1 && ay1 == by1) {
249 if (ax1 == bx2 && ay1 == by2) {
254 if (ax2 == bx1 && ay2 == by1) {
259 if (ax2 == bx2 && ay2 == by2) {
268 if (fabs(d) > dtol) {
270 G_debug(2,
" -> not parallel/collinear: d1 = %f, d2 = %f", d1, d2);
272 if (d1 < 0 || d1 > d || d2 < 0 || d2 > d) {
274 G_debug(2,
" -> fp error, but intersection at end points %f, %f", *x1, *y1);
279 G_debug(2,
" -> no intersection");
286 if (d1 < d || d1 > 0 || d2 < d || d2 > 0) {
288 G_debug(2,
" -> fp error, but intersection at end points %f, %f", *x1, *y1);
293 G_debug(2,
" -> no intersection");
302 *x1 = ax1 + r1 * (ax2 - ax1);
303 *y1 = ay1 + r1 * (ay2 - ay1);
306 G_debug(2,
" -> intersection %f, %f", *x1, *y1);
311 G_debug(3,
" -> parallel/collinear");
316 G_debug(2,
"Segments are apparently parallel, but connected at end points -> collinear");
327 G_debug(2,
" -> collinear vertical");
328 if (ay1 > by2 || ay2 < by1) {
329 G_debug(2,
" -> no intersection");
335 G_debug(2,
" -> connected by end points");
343 G_debug(2,
" -> connected by end points");
352 G_debug(3,
" -> vertical overlap");
354 if (ay1 <= by1 && ay2 >= by2) {
355 G_debug(2,
" -> a contains b");
366 if (ay1 >= by1 && ay2 <= by2) {
367 G_debug(2,
" -> b contains a");
379 G_debug(2,
" -> partial overlap");
380 if (by1 > ay1 && by1 < ay2) {
391 if (by2 > ay1 && by2 < ay2) {
404 G_warning(
_(
"Vect_segment_intersection() ERROR (collinear vertical segments)"));
417 G_debug(2,
" -> collinear non vertical");
420 if ((bx1 > ax2) || (bx2 < ax1)) {
422 G_debug(2,
" -> no intersection");
427 G_debug(2,
" -> overlap/connected end points");
430 if (ax1 == bx2 && ay1 == by2) {
431 G_debug(2,
" -> connected by end points");
438 if (ax2 == bx1 && ay2 == by1) {
439 G_debug(2,
" -> connected by end points");
448 if (ax1 <= bx1 && ax2 >= bx2) {
449 G_debug(2,
" -> a contains b");
460 if (ax1 >= bx1 && ax2 <= bx2) {
461 G_debug(2,
" -> b contains a");
473 G_debug(2,
" -> partial overlap");
474 if (bx1 > ax1 && bx1 < ax2) {
485 if (bx2 > ax1 && bx2 < ax2) {
498 G_warning(
_(
"Vect_segment_intersection() ERROR (collinear non vertical segments)"));
520 static int a_cross = 0;
522 static CROSS *cross =
NULL;
523 static int *use_cross =
NULL;
525 static void add_cross(
int asegment,
double adistance,
int bsegment,
526 double bdistance,
double x,
double y)
528 if (n_cross == a_cross) {
532 (a_cross + 101) *
sizeof(CROSS));
535 (a_cross + 101) *
sizeof(
int));
540 " add new cross: aseg/dist = %d/%f bseg/dist = %d/%f, x = %f y = %f",
541 asegment, adistance, bsegment, bdistance,
x, y);
542 cross[n_cross].segment[0] = asegment;
543 cross[n_cross].distance[0] = adistance;
544 cross[n_cross].segment[1] = bsegment;
545 cross[n_cross].distance[1] = bdistance;
546 cross[n_cross].x =
x;
547 cross[n_cross].y = y;
551 static int cmp_cross(
const void *pa,
const void *pb)
553 CROSS *p1 = (CROSS *) pa;
554 CROSS *p2 = (CROSS *) pb;
556 if (p1->segment[current] < p2->segment[current])
558 if (p1->segment[current] > p2->segment[current])
561 if (p1->distance[current] < p2->distance[current])
563 if (p1->distance[current] > p2->distance[current])
568 static double dist2(
double x1,
double y1,
double x2,
double y2)
574 return (dx * dx + dy * dy);
579 static int ident(
double x1,
double y1,
double x2,
double y2,
double thresh)
585 if ((dx * dx + dy * dy) <= thresh * thresh)
596 static int cross_seg(
int id,
const struct RTree_Rect *rect,
void *arg)
598 double x1, y1, z1, x2, y2, z2;
607 APnts->
x[i + 1], APnts->
y[i + 1],
608 APnts->
z[i + 1], BPnts->
x[j], BPnts->
y[j],
609 BPnts->
z[j], BPnts->
x[j + 1],
610 BPnts->
y[j + 1], BPnts->
z[j + 1], &x1,
611 &y1, &z1, &x2, &y2, &z2, 0);
615 G_debug(2,
" -> %d x %d: intersection type = %d", i, j, ret);
617 G_debug(3,
" in %f, %f ", x1, y1);
618 add_cross(i, 0.0, j, 0.0, x1, y1);
620 else if (ret == 2 || ret == 3 || ret == 4 || ret == 5) {
625 G_debug(3,
" in %f, %f; %f, %f", x1, y1, x2, y2);
626 add_cross(i, 0.0, j, 0.0, x1, y1);
627 add_cross(i, 0.0, j, 0.0, x2, y2);
661 int *nalines,
int *nblines,
int with_z)
663 int i, j, k,
l, last_seg, seg, last;
665 double dist, curdist, last_x, last_y, last_z;
666 double x,
y, rethresh;
668 struct RTree *MyRTree;
670 int seg1, seg2, vert1, vert2;
672 static int rect_init = 0;
675 if (debug_level == -1) {
679 debug_level = atoi(dstr);
761 if (abbox.
N > ABox->
N)
763 if (abbox.
S < ABox->
S)
765 if (abbox.
E > ABox->
E)
767 if (abbox.
W < ABox->
W)
769 if (abbox.
T > ABox->
T)
771 if (abbox.
B < ABox->
B)
784 for (i = 0; i < BPoints->
n_points - 1; i++) {
785 if (BPoints->
x[i] <= BPoints->
x[i + 1]) {
794 if (BPoints->
y[i] <= BPoints->
y[i + 1]) {
803 if (BPoints->
z[i] <= BPoints->
z[i + 1]) {
825 for (i = 0; i < APoints->
n_points - 1; i++) {
826 if (APoints->
x[i] <= APoints->
x[i + 1]) {
835 if (APoints->
y[i] <= APoints->
y[i + 1]) {
843 if (APoints->
z[i] <= APoints->
z[i + 1]) {
866 G_debug(2,
"n_cross = %d", n_cross);
876 for (i = 0; i < n_cross; i++) {
879 seg = cross[i].segment[0];
881 dist2(cross[i].x, cross[i].y, APoints->
x[seg], APoints->
y[seg]);
885 cross[i].distance[0] = curdist;
889 dist2(cross[i].x, cross[i].y, APoints->
x[seg + 1],
890 APoints->
y[seg + 1]);
891 if (dist < curdist) {
893 x = APoints->
x[seg + 1];
894 y = APoints->
y[seg + 1];
898 seg = cross[i].segment[1];
900 dist2(cross[i].x, cross[i].y, BPoints->
x[seg], BPoints->
y[seg]);
901 cross[i].distance[1] = dist;
903 if (dist < curdist) {
909 dist = dist2(cross[i].x, cross[i].y, BPoints->
x[seg + 1], BPoints->
y[seg + 1]);
910 if (dist < curdist) {
912 x = BPoints->
x[seg + 1];
913 y = BPoints->
y[seg + 1];
915 if (curdist < rethresh * rethresh) {
920 seg = cross[i].segment[0];
921 cross[i].distance[0] =
922 dist2(APoints->
x[seg], APoints->
y[seg], cross[i].x, cross[i].y);
923 seg = cross[i].segment[1];
924 cross[i].distance[1] =
925 dist2(BPoints->
x[seg], BPoints->
y[seg], cross[i].x, cross[i].y);
930 for (l = 1; l < 3; l++) {
931 for (i = 0; i < n_cross; i++)
938 G_debug(2,
"Clean and create array for line A");
946 G_debug(2,
"Clean and create array for line B");
955 qsort((
void *)cross,
sizeof(
char) * n_cross,
sizeof(CROSS),
960 if (debug_level > 2) {
961 for (i = 0; i < n_cross; i++) {
963 " cross = %d seg1/dist1 = %d/%f seg2/dist2 = %d/%f x = %f y = %f",
964 i, cross[i].segment[current],
965 sqrt(cross[i].distance[current]),
966 cross[i].segment[second], sqrt(cross[i].distance[second]),
967 cross[i].x, cross[i].y);
972 for (i = 0; i < n_cross; i++) {
973 if (use_cross[i] == 1) {
977 if ((cross[i].segment[current] == 0 &&
978 cross[i].x == Points1->
x[0] &&
979 cross[i].y == Points1->
y[0]) ||
980 (cross[i].segment[current] == j - 1 &&
981 cross[i].x == Points1->
x[j] &&
982 cross[i].y == Points1->
y[j])) {
984 G_debug(3,
"cross %d deleted (first/last point)", i);
1000 for (i = 0; i < n_cross; i++) {
1001 if (use_cross[i] == 0)
1003 G_debug(3,
" is %d between colinear?", i);
1005 seg1 = cross[i].segment[current];
1006 seg2 = cross[i].segment[second];
1009 if (cross[i].x == Points1->
x[seg1] &&
1010 cross[i].y == Points1->
y[seg1]) {
1013 else if (cross[i].x == Points1->
x[seg1 + 1] &&
1014 cross[i].y == Points1->
y[seg1 + 1]) {
1018 G_debug(3,
" -> is not vertex on 1. line");
1025 if (cross[i].x == Points2->
x[seg2] &&
1026 cross[i].y == Points2->
y[seg2]) {
1029 else if (cross[i].x == Points2->
x[seg2 + 1] &&
1030 cross[i].y == Points2->
y[seg2 + 1]) {
1034 G_debug(3,
" -> is not vertex on 2. line");
1037 G_debug(3,
" seg1/vert1 = %d/%d seg2/ver2 = %d/%d", seg1,
1038 vert1, seg2, vert2);
1041 if (vert2 == 0 || vert2 == Points2->
n_points - 1) {
1042 G_debug(3,
" -> vertex 2 (%d) is first/last", vert2);
1047 if (!((Points1->
x[vert1 - 1] == Points2->
x[vert2 - 1] &&
1048 Points1->
y[vert1 - 1] == Points2->
y[vert2 - 1] &&
1049 Points1->
x[vert1 + 1] == Points2->
x[vert2 + 1] &&
1050 Points1->
y[vert1 + 1] == Points2->
y[vert2 + 1]) ||
1051 (Points1->
x[vert1 - 1] == Points2->
x[vert2 + 1] &&
1052 Points1->
y[vert1 - 1] == Points2->
y[vert2 + 1] &&
1053 Points1->
x[vert1 + 1] == Points2->
x[vert2 - 1] &&
1054 Points1->
y[vert1 + 1] == Points2->
y[vert2 - 1])
1057 G_debug(3,
" -> previous/next are not identical");
1063 G_debug(3,
" -> collinear -> remove");
1082 for (i = 0; i < n_cross; i++) {
1083 if (use_cross[i] == 0)
1089 seg = cross[i].segment[current];
1091 G_debug(3,
" duplicate ?: cross = %d seg = %d dist = %f", i,
1092 cross[i].segment[current], cross[i].distance[current]);
1093 if ((cross[i].segment[current] == cross[last].segment[current] &&
1094 cross[i].distance[current] == cross[last].distance[current])
1095 || (cross[i].segment[current] ==
1096 cross[last].segment[current] + 1 &&
1097 cross[i].distance[current] == 0 &&
1098 cross[i].x == cross[last].x &&
1099 cross[i].y == cross[last].y)) {
1100 G_debug(3,
" cross %d identical to last -> removed", i);
1111 G_debug(3,
" alive crosses:");
1112 for (i = 0; i < n_cross; i++) {
1113 if (use_cross[i] == 1) {
1120 if (n_alive_cross > 0) {
1122 use_cross[n_cross] = 1;
1124 cross[n_cross].x = Points->
x[j];
1125 cross[n_cross].y = Points->
y[j];
1126 cross[n_cross].segment[current] = Points->
n_points - 2;
1129 last_x = Points->
x[0];
1130 last_y = Points->
y[0];
1131 last_z = Points->
z[0];
1134 for (i = 0; i <= n_cross; i++) {
1135 seg = cross[i].segment[current];
1136 G_debug(2,
"%d seg = %d dist = %f", i, seg,
1137 cross[i].distance[current]);
1138 if (use_cross[i] == 0) {
1139 G_debug(3,
" removed -> next");
1147 G_debug(2,
" append last vert: %f %f", last_x, last_y);
1150 for (j = last_seg + 1; j <= seg; j++) {
1151 G_debug(2,
" segment j = %d", j);
1153 if ((j == last_seg + 1) && Points->
x[j] == last_x &&
1154 Points->
y[j] == last_y) {
1155 G_debug(2,
" -> skip (identical to last break)");
1160 G_debug(2,
" append first of seg: %f %f", Points->
x[j],
1165 last_x = cross[i].x;
1166 last_y = cross[i].y;
1169 if (Points->
z[last_seg] == Points->
z[last_seg + 1]) {
1170 last_z = Points->
z[last_seg + 1];
1172 else if (last_x == Points->
x[last_seg] &&
1173 last_y == Points->
y[last_seg]) {
1174 last_z = Points->
z[last_seg];
1176 else if (last_x == Points->
x[last_seg + 1] &&
1177 last_y == Points->
y[last_seg + 1]) {
1178 last_z = Points->
z[last_seg + 1];
1181 dist = dist2(Points->
x[last_seg],
1182 Points->
x[last_seg + 1],
1183 Points->
y[last_seg],
1184 Points->
y[last_seg + 1]);
1185 last_z = (Points->
z[last_seg] * sqrt(cross[i].distance[current]) +
1186 Points->
z[last_seg + 1] * (sqrt(dist) - sqrt(cross[i].distance[current]))) /
1192 G_debug(2,
" append cross / last point: %f %f", cross[i].x,
1197 G_debug(2,
" line is degenerate -> skipped");
1220 static struct line_pnts *APnts, *BPnts, *IPnts;
1222 static int cross_found;
1223 static int report_all;
1226 static int find_cross(
int id,
const struct RTree_Rect *rect,
void *arg)
1228 double x1, y1, z1, x2, y2, z2;
1237 APnts->
x[i + 1], APnts->
y[i + 1],
1238 APnts->
z[i + 1], BPnts->
x[j], BPnts->
y[j],
1239 BPnts->
z[j], BPnts->
x[j + 1],
1240 BPnts->
y[j + 1], BPnts->
z[j + 1], &x1,
1241 &y1, &z1, &x2, &y2, &z2, 0);
1249 G_warning(
_(
"Error while adding point to array. Out of memory"));
1255 G_warning(
_(
"Error while adding point to array. Out of memory"));
1257 G_warning(
_(
"Error while adding point to array. Out of memory"));
1274 double dist, rethresh;
1275 struct RTree *MyRTree;
1277 static int rect_init = 0;
1284 rethresh = 0.000001;
1296 if (APoints->
x[0] == BPoints->
x[0] && APoints->
y[0] == BPoints->
y[0]) {
1298 if (report_all && 0 >
1300 &APoints->
y[0],
NULL, 1))
1301 G_warning(
_(
"Error while adding point to array. Out of memory"));
1305 if (APoints->
z[0] == BPoints->
z[0]) {
1306 if (report_all && 0 >
1308 &APoints->
y[0], &APoints->
z[0],
1310 G_warning(
_(
"Error while adding point to array. Out of memory"));
1327 if (dist <= rethresh) {
1328 if (report_all && 0 >
1331 G_warning(
_(
"Error while adding point to array. Out of memory"));
1344 if (dist <= rethresh) {
1345 if (report_all && 0 >
1348 G_warning(
_(
"Error while adding point to array. Out of memory"));
1365 for (i = 0; i < BPoints->
n_points - 1; i++) {
1366 if (BPoints->
x[i] <= BPoints->
x[i + 1]) {
1375 if (BPoints->
y[i] <= BPoints->
y[i + 1]) {
1384 if (BPoints->
z[i] <= BPoints->
z[i + 1]) {
1399 for (i = 0; i < APoints->
n_points - 1; i++) {
1400 if (APoints->
x[i] <= APoints->
x[i + 1]) {
1409 if (APoints->
y[i] <= APoints->
y[i + 1]) {
1417 if (APoints->
z[i] <= APoints->
z[i + 1]) {
1428 if (!report_all && cross_found) {
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 Vect_line_get_intersections(struct line_pnts *APoints, struct line_pnts *BPoints, struct line_pnts *IPoints, int with_z)
Get 2 lines intersection points.
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
int n_points
Number of points.
int Vect_copy_xyz_to_pnts(struct line_pnts *, const double *, const double *, const double *, int)
Copy points from array to line_pnts structure.
int Vect_line_check_intersection(struct line_pnts *APoints, struct line_pnts *BPoints, int with_z)
Check if 2 lines intersect.
int Vect_line_intersection(struct line_pnts *APoints, struct line_pnts *BPoints, struct bound_box *ABox, struct bound_box *BBox, struct line_pnts ***ALines, struct line_pnts ***BLines, int *nalines, int *nblines, int with_z)
Intersect 2 lines.
int Vect_line_distance(const struct line_pnts *, double, double, double, int, double *, double *, double *, double *, double *, double *)
Calculate distance of point to line.
int line_check_intersection(struct line_pnts *APoints, struct line_pnts *BPoints, int with_z)
double * x
Array of X coordinates.
Feature geometry info - coordinates.
int Vect_segment_intersection(double ax1, double ay1, double az1, double ax2, double ay2, double az2, double bx1, double by1, double bz1, double bx2, double by2, double bz2, double *x1, double *y1, double *z1, double *x2, double *y2, double *z2, int with_z)
Check for intersect of 2 line segments.
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
double * y
Array of Y coordinates.
void G_warning(const char *,...) __attribute__((format(printf
double * z
Array of Z coordinates.
const char * G_getenv_nofatal(const char *)
Get environment variable.
int dig_line_degenerate(const struct line_pnts *)
int Vect_box_overlap(const struct bound_box *, const struct bound_box *)
Tests for overlap of two boxes.
void Vect_destroy_line_struct(struct line_pnts *)
Frees all memory associated with a line_pnts structure, including the structure itself.
int G_debug(int, const char *,...) __attribute__((format(printf
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
void Vect_reset_line(struct line_pnts *)
Reset line.