linecros.c

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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5