| 175 | */ |
| 176 | |
| 177 | int msIntersectSegments(pointObj *a, pointObj *b, pointObj *c, pointObj *d) { /* from comp.graphics.alogorithms FAQ */ |
| 178 | |
| 179 | double r, s; |
| 180 | double denominator, numerator; |
| 181 | |
| 182 | numerator = ((a->y-c->y)*(d->x-c->x) - (a->x-c->x)*(d->y-c->y)); |
| 183 | denominator = ((b->x-a->x)*(d->y-c->y) - (b->y-a->y)*(d->x-c->x)); |
| 184 | |
| 185 | if((denominator == 0) && (numerator == 0)) { /* lines are coincident, intersection is a line segement if it exists */ |
| 186 | if(a->y == c->y) { /* coincident horizontally, check x's */ |
| 187 | if(((a->x >= MS_MIN(c->x,d->x)) && (a->x <= MS_MAX(c->x,d->x))) || ((b->x >= MS_MIN(c->x,d->x)) && (b->x <= MS_MAX(c->x,d->x)))) |
| 188 | return(MS_TRUE); |
| 189 | else |
| 190 | return(MS_FALSE); |
| 191 | } else { /* test for y's will work fine for remaining cases */ |
| 192 | if(((a->y >= MS_MIN(c->y,d->y)) && (a->y <= MS_MAX(c->y,d->y))) || ((b->y >= MS_MIN(c->y,d->y)) && (b->y <= MS_MAX(c->y,d->y)))) |
| 193 | return(MS_TRUE); |
| 194 | else |
| 195 | return(MS_FALSE); |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | if(denominator == 0) /* lines are parallel, can't intersect */ |
| 200 | return(MS_FALSE); |
| 201 | |
| 202 | r = numerator/denominator; |
| 203 | |
| 204 | if((r<0) || (r>1)) |
| 205 | return(MS_FALSE); /* no intersection */ |
| 206 | |
| 207 | numerator = ((a->y-c->y)*(b->x-a->x) - (a->x-c->x)*(b->y-a->y)); |
| 208 | s = numerator/denominator; |
| 209 | |
| 210 | if((s<0) || (s>1)) |
| 211 | return(MS_FALSE); /* no intersection */ |
| 212 | |
| 213 | return(MS_TRUE); |
| 214 | } |
| 215 | |
| 216 | /* |
| 217 | ** Instead of using ring orientation we count the number of parts the |
no outgoing calls
no test coverage detected