GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* 00002 **************************************************************************** 00003 * 00004 * MODULE: Vector library 00005 * 00006 * AUTHOR(S): Original author CERL, probably Dave Gerdes. 00007 * Update to GRASS 5.7 Radim Blazek. 00008 * 00009 * PURPOSE: Lower level functions for reading/writing/manipulating vectors. 00010 * 00011 * COPYRIGHT: (C) 2001 by the GRASS Development Team 00012 * 00013 * This program is free software under the GNU General Public 00014 * License (>=v2). Read the file COPYING that comes with GRASS 00015 * for details. 00016 * 00017 *****************************************************************************/ 00018 #include <stdio.h> 00019 00020 /*************************************************************** 00021 * test_for_intersection (ax1,ay1,ax2,ay2,bx1,by1,bx2,by2) 00022 * double ax1,ax2,ay1,ay2; 00023 * double bx1,bx2,by1,by2; 00024 * 00025 * returns 00026 * 0 no intersection at all 00027 * 1 the line segments intersect at only one point 00028 * -1 the line segments intersect at many points, i.e., overlapping 00029 * segments from the same line 00030 * 00031 * find_intersection (ax1,ay1,ax2,ay2,bx1,by1,bx2,by2,x,y) 00032 * double ax1,ax2,ay1,ay2; 00033 * double bx1,bx2,by1,by2; 00034 * double *x,*y; 00035 * 00036 * returns 00037 * 0 no intersection 00038 * 1 x,y set to (unique) intersection 00039 * -1 lines overlap, no unique intersection 00040 * 00041 * Based on the following: 00042 * 00043 * (ax2-ax1)r1 - (bx2-bx1)r2 = ax2 - ax1 00044 * (ay2-ay1)r1 - (by2-by1)r2 = ay2 - ay1 00045 * 00046 * Solving for r1 and r2, if r1 and r2 are between 0 and 1, 00047 * then line segments (ax1,ay1)(ax2,ay2) and (bx1,by1)(bx2,by2) 00048 * intersect 00049 ****************************************************************/ 00050 00051 #define D ((ax2-ax1)*(by1-by2) - (ay2-ay1)*(bx1-bx2)) 00052 00053 #define D1 ((bx1-ax1)*(by1-by2) - (by1-ay1)*(bx1-bx2)) 00054 00055 #define D2 ((ax2-ax1)*(by1-ay1) - (ay2-ay1)*(bx1-ax1)) 00056 00057 int 00058 dig_test_for_intersection(double ax1, double ay1, 00059 double ax2, double ay2, 00060 double bx1, double by1, double bx2, double by2) 00061 { 00062 register double d, d1, d2; 00063 double t; 00064 00065 d = D; 00066 d1 = D1; 00067 d2 = D2; 00068 00069 if (d > 0) 00070 return (d1 >= 0 && d2 >= 0 && d >= d1 && d >= d2); 00071 if (d < 0) 00072 return (d1 <= 0 && d2 <= 0 && d <= d1 && d <= d2); 00073 00074 /* lines are parallel */ 00075 if (d1 || d2) 00076 return 0; 00077 00078 /* segments are colinear. check for overlap */ 00079 if (ax1 > ax2) { 00080 t = ax1; 00081 ax1 = ax2; 00082 ax2 = t; 00083 } 00084 if (bx1 > bx2) { 00085 t = bx1; 00086 bx1 = bx2; 00087 bx2 = t; 00088 } 00089 if (ax1 > bx2) 00090 return 0; 00091 if (ax2 < bx1) 00092 return 0; 00093 00094 /* there is overlap */ 00095 00096 if (ax1 == bx2 || ax2 == bx1) 00097 return 1; /* endpoints only */ 00098 return -1; /* true overlap */ 00099 } 00100 00101 00102 int 00103 dig_find_intersection(double ax1, double ay1, 00104 double ax2, double ay2, 00105 double bx1, double by1, 00106 double bx2, double by2, double *x, double *y) 00107 { 00108 register double d, r1, r2; 00109 double t; 00110 00111 d = D; 00112 00113 if (d) { 00114 00115 r1 = D1 / d; 00116 r2 = D2 / d; 00117 if (r1 < 0 || r1 > 1 || r2 < 0 || r2 > 1) { 00118 return 0; 00119 } 00120 *x = ax1 + r1 * (ax2 - ax1); 00121 *y = ay1 + r1 * (ay2 - ay1); 00122 return 1; 00123 } 00124 00125 /* lines are parallel */ 00126 if (D1 || D2) { 00127 return 0; 00128 } 00129 00130 /* segments are colinear. check for overlap */ 00131 if (ax1 > ax2) { 00132 t = ax1; 00133 ax1 = ax2; 00134 ax2 = t; 00135 } 00136 if (bx1 > bx2) { 00137 t = bx1; 00138 bx1 = bx2; 00139 bx2 = t; 00140 } 00141 if (ax1 > bx2) 00142 return 0; 00143 if (ax2 < bx1) 00144 return 0; 00145 00146 /* there is overlap */ 00147 00148 if (ax1 == bx2) { 00149 *x = ax1; 00150 *y = ay1; 00151 return 1; /* endpoints only */ 00152 } 00153 if (ax2 == bx1) { 00154 *x = ax2; 00155 *y = ay2; 00156 return 1; /* endpoints only */ 00157 } 00158 return -1; /* overlap, no single intersection point */ 00159 }