linecros.c

Go to the documentation of this file.
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 }

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1