# Algorithm of judging click area

In the last article, we solved the problem of quadrilateral with rotation angle, which took a day to figure out the algorithm. But it's only limited to quadrilateral.
The original God has written the algorithm for a long time, which can solve the problem of n-polygon click area judgment.
Before using this algorithm, first of all, the x-axis of the first point of the polygon should be guaranteed to be the minimum value, that is to say, the coordinates of each point of the polygon should be sorted to find the point with the minimum x, put it in the first point, and the other points should be rotated in turn.

Rotation method:

``````function sort(ele) {
var min = 0,
arr = [],
len = ele.length;
for(var n = 0; n < len; n++){
if(ele[n][0] < ele[min][0]){
min = n
}
}
if(min != 0){
for(var x = min; x < ele.length; x++){
arr.push(ele[x]);
}
for(var y = 0; y < min; y++){
arr.push(ele[y]);
}
return arr
}
return ele;
}
var bbox = [[4],[1],[2],[3]];
sort(bbox)//[[1],[2],[3],[4]]``````

Determine whether the click area is within the polygon range:

``````navi_utils.pointInPolygon = function (pos, polygon) {
var inside = false;
var polygonSize = polygon.length;
var val1, val2;
for(var i = 0; i < polygonSize; i++){
var p1 = polygon[(i +  polygonSize)%polygonSize];
var p2 = polygon[(i + 1 + polygonSize)%polygonSize];
if(pos[1] < p2[1]){
if(pos[1] >= p1[1]){
val1 = (pos[1] - p1[1]) * (p2[0] - p1[0]);
val2 = (pos[0] - p1[0]) * (p2[1] - p1[1]);
if(val1 > val2){
inside = ! inside;
}
}
}else if( pos[1] < p1[1]){
val1 = (pos[1] - p1[1]) * (p2[0] - p1[0]);
val2 = (pos[0] - p1[0]) * (p2[1] - p1[1]);
if(val1 < val2){
inside = ! inside;
}
}
}
return inside;
};``````

Keywords: Javascript

Added by Dada78 on Sat, 07 Dec 2019 00:12:05 +0200