GRASS Programmer's Manual  6.5.svn(2014)-r66266
linecros.c
Go to the documentation of this file.
1 /*
2  ****************************************************************************
3  *
4  * MODULE: Vector library
5  *
6  * AUTHOR(S): Original author CERL, probably Dave Gerdes.
7  * Update to GRASS 5.7 Radim Blazek.
8  *
9  * PURPOSE: Lower level functions for reading/writing/manipulating vectors.
10  *
11  * COPYRIGHT: (C) 2001 by the GRASS Development Team
12  *
13  * This program is free software under the GNU General Public
14  * License (>=v2). Read the file COPYING that comes with GRASS
15  * for details.
16  *
17  *****************************************************************************/
18 #include <stdio.h>
19
20 /***************************************************************
21 * test_for_intersection (ax1,ay1,ax2,ay2,bx1,by1,bx2,by2)
22 * double ax1,ax2,ay1,ay2;
23 * double bx1,bx2,by1,by2;
24 *
25 * returns
26 * 0 no intersection at all
27 * 1 the line segments intersect at only one point
28 * -1 the line segments intersect at many points, i.e., overlapping
29 * segments from the same line
30 *
31 * find_intersection (ax1,ay1,ax2,ay2,bx1,by1,bx2,by2,x,y)
32 * double ax1,ax2,ay1,ay2;
33 * double bx1,bx2,by1,by2;
34 * double *x,*y;
35 *
36 * returns
37 * 0 no intersection
38 * 1 x,y set to (unique) intersection
39 * -1 lines overlap, no unique intersection
40 *
41 * Based on the following:
42 *
43 * (ax2-ax1)r1 - (bx2-bx1)r2 = ax2 - ax1
44 * (ay2-ay1)r1 - (by2-by1)r2 = ay2 - ay1
45 *
46 * Solving for r1 and r2, if r1 and r2 are between 0 and 1,
47 * then line segments (ax1,ay1)(ax2,ay2) and (bx1,by1)(bx2,by2)
48 * intersect
49 ****************************************************************/
50
51 #define D ((ax2-ax1)*(by1-by2) - (ay2-ay1)*(bx1-bx2))
52
53 #define D1 ((bx1-ax1)*(by1-by2) - (by1-ay1)*(bx1-bx2))
54
55 #define D2 ((ax2-ax1)*(by1-ay1) - (ay2-ay1)*(bx1-ax1))
56
57 int
58 dig_test_for_intersection(double ax1, double ay1,
59  double ax2, double ay2,
60  double bx1, double by1, double bx2, double by2)
61 {
62  register double d, d1, d2;
63  double t;
64
65  d = D;
66  d1 = D1;
67  d2 = D2;
68
69  if (d > 0)
70  return (d1 >= 0 && d2 >= 0 && d >= d1 && d >= d2);
71  if (d < 0)
72  return (d1 <= 0 && d2 <= 0 && d <= d1 && d <= d2);
73
74  /* lines are parallel */
75  if (d1 || d2)
76  return 0;
77
78  /* segments are colinear. check for overlap */
79  if (ax1 > ax2) {
80  t = ax1;
81  ax1 = ax2;
82  ax2 = t;
83  }
84  if (bx1 > bx2) {
85  t = bx1;
86  bx1 = bx2;
87  bx2 = t;
88  }
89  if (ax1 > bx2)
90  return 0;
91  if (ax2 < bx1)
92  return 0;
93
94  /* there is overlap */
95
96  if (ax1 == bx2 || ax2 == bx1)
97  return 1; /* endpoints only */
98  return -1; /* true overlap */
99 }
100
101
102 int
103 dig_find_intersection(double ax1, double ay1,
104  double ax2, double ay2,
105  double bx1, double by1,
106  double bx2, double by2, double *x, double *y)
107 {
108  register double d, r1, r2;
109  double t;
110
111  d = D;
112
113  if (d) {
114
115  r1 = D1 / d;
116  r2 = D2 / d;
117  if (r1 < 0 || r1 > 1 || r2 < 0 || r2 > 1) {
118  return 0;
119  }
120  *x = ax1 + r1 * (ax2 - ax1);
121  *y = ay1 + r1 * (ay2 - ay1);
122  return 1;
123  }
124
125  /* lines are parallel */
126  if (D1 || D2) {
127  return 0;
128  }
129
130  /* segments are colinear. check for overlap */
131  if (ax1 > ax2) {
132  t = ax1;
133  ax1 = ax2;
134  ax2 = t;
135  }
136  if (bx1 > bx2) {
137  t = bx1;
138  bx1 = bx2;
139  bx2 = t;
140  }
141  if (ax1 > bx2)
142  return 0;
143  if (ax2 < bx1)
144  return 0;
145
146  /* there is overlap */
147
148  if (ax1 == bx2) {
149  *x = ax1;
150  *y = ay1;
151  return 1; /* endpoints only */
152  }
153  if (ax2 == bx1) {
154  *x = ax2;
155  *y = ay2;
156  return 1; /* endpoints only */
157  }
158  return -1; /* overlap, no single intersection point */
159 }
int dig_find_intersection(double ax1, double ay1, double ax2, double ay2, double bx1, double by1, double bx2, double by2, double *x, double *y)
Definition: linecros.c:103
#define D2
Definition: linecros.c:55
int y
Definition: plot.c:34
#define D
Definition: linecros.c:51
int dig_test_for_intersection(double ax1, double ay1, double ax2, double ay2, double bx1, double by1, double bx2, double by2)
Definition: linecros.c:58
#define D1
Definition: linecros.c:53