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
104
105
106
107
108
109
110
111
112
113
114
|
/**
* @author Peter Kelley
* @author pgkelley4@gmail.com
*/
/**
* See if two line segments intersect. This uses the
* vector cross product approach described below:
* http://stackoverflow.com/a/565282/786339
*
* @param {Object} p point object with x and y coordinates
* representing the start of the 1st line.
* @param {Object} p2 point object with x and y coordinates
* representing the end of the 1st line.
* @param {Object} q point object with x and y coordinates
* representing the start of the 2nd line.
* @param {Object} q2 point object with x and y coordinates
* representing the end of the 2nd line.
*/
function doLineSegmentsIntersect(p, p2, q, q2) {
var r = subtractPoints(p2, p);
var s = subtractPoints(q2, q);
var uNumerator = crossProduct(subtractPoints(q, p), r);
var denominator = crossProduct(r, s);
if (uNumerator == 0 && denominator == 0) {
// They are coLlinear
// Do they touch? (Are any of the points equal?)
if (equalPoints(p, q) || equalPoints(p, q2) || equalPoints(p2, q) || equalPoints(p2, q2)) {
return true
}
// Do they overlap? (Are all the point differences in either direction the same sign)
return !allEqual(
(q.x - p.x < 0),
(q.x - p2.x < 0),
(q2.x - p.x < 0),
(q2.x - p2.x < 0)) ||
!allEqual(
(q.y - p.y < 0),
(q.y - p2.y < 0),
(q2.y - p.y < 0),
(q2.y - p2.y < 0));
}
if (denominator == 0) {
// lines are paralell
return false;
}
var u = uNumerator / denominator;
var t = crossProduct(subtractPoints(q, p), s) / denominator;
return (t >= 0) && (t <= 1) && (u >= 0) && (u <= 1);
}
/**
* Calculate the cross product of the two points.
*
* @param {Object} point1 point object with x and y coordinates
* @param {Object} point2 point object with x and y coordinates
*
* @return the cross product result as a float
*/
function crossProduct(point1, point2) {
return point1.x * point2.y - point1.y * point2.x;
}
/**
* Subtract the second point from the first.
*
* @param {Object} point1 point object with x and y coordinates
* @param {Object} point2 point object with x and y coordinates
*
* @return the subtraction result as a point object
*/
function subtractPoints(point1, point2) {
var result = {};
result.x = point1.x - point2.x;
result.y = point1.y - point2.y;
return result;
}
/**
* See if the points are equal.
*
* @param {Object} point1 point object with x and y coordinates
* @param {Object} point2 point object with x and y coordinates
*
* @return if the points are equal
*/
function equalPoints(point1, point2) {
return (point1.x == point2.x) && (point1.y == point2.y)
}
/**
* See if all arguments are equal.
*
* @param {...} args arguments that will be compared by '=='.
*
* @return if all arguments are equal
*/
function allEqual(args) {
var firstValue = arguments[0],
i;
for (i = 1; i < arguments.length; i += 1) {
if (arguments[i] != firstValue) {
return false;
}
}
return true;
}
|
