1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include "Line.h"
#include <math.h>
bool Line::contains(const Vertex &v) const {
if(v1.getX() == v2.getX() && v1.getY() == v2.getY()) {
if(v1.getX() == v.getX() && v1.getY() == v.getY())
return true;
else
return false;
}
if(v1.getX() == v2.getX()) {
if(v1.getX() != v.getX())
return false;
else if(v.getY() >= fmin(v1.getY(), v2.getY()) && v.getY() <= fmax(v1.getY(), v2.getY()))
return true;
else
return false;
}
if(v1.getY() == v2.getY()) {
if(v1.getY() != v.getY())
return false;
else if(v.getX() >= fmin(v1.getX(), v2.getX()) && v.getX() <= fmax(v1.getX(), v2.getX()))
return true;
else
return false;
}
if((v.getX()-v1.getX())/(v2.getX()-v1.getX()) - (v.getY()-v1.getY())/(v2.getY()-v1.getY()) == 0)
return true;
else
return false;
}
int Line::intersects(const Line &l, Vertex *v) const {
double xa1 = v1.getX(), ya1 = v1.getY();
double xa2 = v2.getX(), ya2 = v2.getY();
double xb1 = l.v1.getX(), yb1 = l.v1.getY();
double xb2 = l.v2.getX(), yb2 = l.v2.getY();
double temp;
int switched = 0;
Vertex v2;
if(!v) v = &v2;
if(xa1 == xa2 && ya1 == ya2) return INTERSECTION_ERROR;
if(xb1 == xb2 && yb1 == yb2) return INTERSECTION_ERROR;
if(xa1 == xa2 || xb1 == xb2) {
temp = xa1; xa1 = ya1; ya1 = temp;
temp = xa2; xa2 = ya2; ya2 = temp;
temp = xb1; xb1 = yb1; yb1 = temp;
temp = xb2; xb2 = yb2; yb2 = temp;
switched = 1;
}
if(xa1 == xa2 && xb1 == xb2)
return (xa1 == xb1) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE;
if(xa1 == xa2) {
v->setX(xa1);
v->setY(yb1);
}
else if(xb1 == xb2) {
v->setX(xb1);
v->setY(ya1);
}
else {
double ma = (ya2-ya1)/(xa2-xa1);
double mb = (yb2-yb1)/(xb2-xb1);
double ba = ya1 - ma*xa1;
double bb = yb1 - mb*xb1;
if(ma == mb) return (ba == bb) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE;
v->setX((bb-ba)/(ma-mb));
v->setY(ma*v->getX() + ba);
}
if(switched) {
temp = v->getX(); v->setX(v->getY()); v->setY(temp);
//switch back everything for segment tests
temp = xa1; xa1 = ya1; ya1 = temp;
temp = xa2; xa2 = ya2; ya2 = temp;
temp = xb1; xb1 = yb1; yb1 = temp;
temp = xb2; xb2 = yb2; yb2 = temp;
}
if(v->getX() < fmin(xa1,xa2) || v->getX() > fmax(xa1, xa2) || v->getY() < fmin(ya1,ya2) || v->getY() > fmax(ya1, ya2)) {
if(v->getX() < fmin(xb1,xb2) || v->getX() > fmax(xb1, xb2) || v->getY() < fmin(yb1,yb2) || v->getY() > fmax(yb1, yb2))
return INTERSECTION_LINE_LINE;
else
return INTERSECTION_LINE_SEGMENT;
}
else if(v->getX() < fmin(xb1,xb2) || v->getX() > fmax(xb1, xb2) || v->getY() < fmin(yb1,yb2) || v->getY() > fmax(yb1, yb2))
return INTERSECTION_SEGMENT_LINE;
else
return INTERSECTION_SEGMENT_SEGMENT;
}
|
