So you basicly want to know which edges of the polygon are intersected by given line, right?
This is just quite simple handling of a few linear equations representing the edges (inequations, to be more precise). You already have a great implementation of the inside
operation, which also does that. The common denominator of all these algorithms is to compare at which side of the line [x1, y1]
- [x2, y2]
the point [x, y]
lies:
compare = function (a, b) { // classical compare function, returns -1, 0, 1
return a < b ? -1 : (a == b ? 0 : 1);
}
...
_lineSide: function (x, y, x1, y1, x2, y2) {
return compare(x - x1, (x2 - x1) * (y - y1) / (y2 - y1));
}
This function will return -1 if [x, y]
lies on one side of the line [x1, y1]
- [x2, y2]
, 1 for the other side and 0 if it lies exactly on the line. It is not important here which side is which one, just to separate them. This will however not work when y2 - y1
is zero or close to zero. In that case you have to x-y flip the situation:
lineSide: function (x, y, x1, y1, x2, y2) {
var eps = 1e-20; // some very small number
if (Math.abs(y2 - y1) > eps) // this way we avoid division by small number
return _lineSide(x, y, x1, y1, x2, y2);
else if (Math.abs(x2 - x1) > eps) // flip the situation for horizontal lines
return _lineSide(y, x, y1, x1, y2, x2);
else // edge has close-to-zero length!
throw new this.zeroLengthLineException()
},
zeroLengthLineException: function () {},
Now to test if the two lines [x1, y1]
- [x2, y2]
and [x3, y3]
- [x4, y4]
intersect is very easy. Just look if [x1, y1]
and [x2, y2]
lie on the opposite side of [x3, y3]
- [x4, y4]
, and if [x3, y3]
and [x4, y4]
lie on the opposite side of [x1, y1]
- [x2, y2]
. If yes, then the lines intersect!
// proper: true/false (default false) - if we want proper intersection, i.e. just
// touching doesn't count
linesIntersect: function (x1, y1, x2, y2, x3, y3, x4, y4, proper) {
var min_diff = proper ? 2 : 1;
return Math.abs(this.lineSide(x1, y1, x3, y3, x4, y4) -
this.lineSide(x2, y2, x3, y3, x4, y4)) >= min_diff
&& Math.abs(this.lineSide(x3, y3, x1, y1, x2, y2) -
this.lineSide(x4, y4, x1, y1, x2, y2)) >= min_diff;
},
Final solution - http://jsfiddle.net/gLTpT/7/
Now, the final solution is easy: just check the intersection of given line with all of the polygon edges by calling linesIntersect
in loop: