| Computing desk | ||
|---|---|---|
| < May 21 | << Apr | May | Jun >> | May 23 > |
| Welcome to the Wikipedia Computing Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I run a movie website i got rights for pc and tablet but not for mobile phones how do you block mobiel phones but not tablets from acesssing website — Preceding unsigned comment added by AalatShitoleClanMember (talk • contribs) 00:30, 22 May 2016 (UTC)
Here's my code to implement my suggested method of solving the previous Ref Desk Q.
My assumptions:
I show 3 methods, with benchmarking in place to compare the speeds of each:
1) The brute force method of finding the min distance between every point in each set.
2) Same as above, but bails out when any distance less than the threshold is encountered. As you might expect, this takes just about as long as the first method, when there is no point below that threshold, but is somewhat faster if there is.
3) My method does the same as above, except that it has an extra bit of logic to skip forward to the next point which could possibly be in the threshold range of the other set. For example, if the current point in set 2 is 100 from the current pt in set 1, and the threshold we are looking for is a distance of 10 or less, then we can skip forward 90/sqrt(2) points. If that next point is still 50 away, we can jump forward another 40/sqrt(2), etc.
My method is consistently fastest, but how much faster depends on the assumptions and particular trial. I found it ranged from 15 times faster to 10,000 times faster, in my trials. Go ahead and cut and paste it and do your own trials, perhaps changing some of the assumption params.
I'd also like to see benchmarking for the Delaunay triangulation method mentioned by BenRG, so we can compare. StuRat (talk) 01:57, 22 May 2016 (UTC)
| My JavaScript code |
|---|
| The following discussion has been closed. Please do not modify it. |
<!DOCTYPE html>
<html>
<body>
<p id="demo"></p>
<script>
var set1x, set1y;
set1x = [500]; // Starting point X coord for set 1.
set1y = [500]; // Starting point Y coord for set 1.
for (i = 1; i < 10000; i++) { // Number of points in set 1.
set1x[i] = set1x[i-1] + Math.round(3*Math.random()-1.5); // Each pt randomly walks +1, 0, or -1
set1y[i] = set1y[i-1] + Math.round(3*Math.random()-1.5); // in each direction.
}
var set1x, set1y;
set2x = [500]; // Starting point X coord for set 2.
set2y = [600]; // Starting point Y coord for set 2.
for (i = 1; i < 10000; i++) { // Number of points in set 2.
set2x[i] = set2x[i-1] + Math.round(3*Math.random()-1.5); // Each pt randomly walks +1, 0, or -1
set2y[i] = set2y[i-1] + Math.round(3*Math.random()-1.5); // in each direction.
}
maxStep = Math.sqrt(2.0); // Max distance each walk step can move from previous pt.
thresh = 10; // Minimum distance threshold for a "match".
text = '<ul style="list-style-type:none">';
//Find the minimum distance (the hard way):
text += "<li>=================================</li>";
text += "<li>FIND MIN DISTANCE, BY BRUTE FORCE :</li>";
text += "<li>=================================</li>";
len1 = set1x.length;
len2 = set2x.length;
var time0 = performance.now();
minDistSquared = 999999999;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
distSquared = Math.pow((set1x[i] - set2x[j]),2)
+ Math.pow((set1y[i] - set2y[j]),2);
if (distSquared < minDistSquared) {
minDistI = i;
minDistJ = j;
minDistSquared = distSquared;
}
}
}
var time1 = performance.now();
text += "<li>" + "Elapsed time = " + (time1 - time0) + " milliseconds" + "</li>";
text += "<li>" + "Min distance = " + Math.sqrt(minDistSquared) + " between points "
+ "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and "
+ "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + "</li>";
text += "<li>" + " " + "</li>";
//Find if the minimum distance is below the threshhold (the hard way):
text += "<li>=======================================================</li>";
text += "<li>FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE :</li>";
text += "<li>=======================================================</li>";
len1 = set1x.length;
len2 = set2x.length;
var time0 = performance.now();
minDistSquared = thresh*thresh;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
distSquared = Math.pow((set1x[i] - set2x[j]),2)
+ Math.pow((set1y[i] - set2y[j]),2);
if (distSquared <= minDistSquared) {
minDistI = i;
minDistJ = j;
minDistSquared = distSquared;
i = 99999999; // Bail out of both loops by setting arbitrarily large loop values.
j = 99999999;
}
}
}
var time1 = performance.now();
text += "<li>" + "Elapsed time = " + (time1 - time0) + " milliseconds" + "</li>";
if (i < 99999999) {
text += "<li>" + "No distance below threshold of "+ thresh +" was found." + "</li>";
}
else {
text += "<li>" + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points "
+ "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and "
+ "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + "</li>";
};
text += "<li>" + " " + "</li>";
//Find if the minimum distance is below the threshhold (the elegant way):
text += "<li>===========================================================</li>";
text += "<li>FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD :</li>";
text += "<li>===========================================================</li>";
len1 = set1x.length;
len2 = set2x.length;
var time0 = performance.now();
minDistSquared = thresh*thresh;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
distSquared = Math.pow((set1x[i] - set2x[j]),2)
+ Math.pow((set1y[i] - set2y[j]),2);
if (distSquared <= minDistSquared) {
minDistI = i;
minDistJ = j;
minDistSquared = distSquared;
i = 99999999; // Bail out of both loops by setting arbitrarily large loop values.
j = 99999999;
}
else {
newJ = j + Math.round(((Math.sqrt(distSquared)-thresh)/maxStep)-0.5); // Here's the important line.
if (newJ > j) {j = newJ}; // We skip ahead until the next j (set 2 pt) that could possibly
// be within the threshold range of the current i (set 1 pt).
}
}
}
var time1 = performance.now();
text += "<li>" + "Elapsed time = " + (time1 - time0) + " milliseconds" + "</li>";
if (i < 99999999) {
text += "<li>" + "No distance below threshold of "+ thresh +" was found." + "</li>";
}
else {
text += "<li>" + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points "
+ "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and "
+ "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + "</li>";
};
text += "</ul>";
document.getElementById("demo").innerHTML = text;
</script>
</body>
</html>
|
| Here's a run with a min distance below the threshold. |
|---|
| The following discussion has been closed. Please do not modify it. |
================================= FIND MIN DISTANCE, BY BRUTE FORCE : ================================= Elapsed time = 2691.255 milliseconds Min distance = 0 between points (476,576) and (476,576) ======================================================= FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE : ======================================================= Elapsed time = 363.1350000000002 milliseconds First distance below threshold of 10 = 9.848857801796104 between points (469,567) and (473,576) =========================================================== FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD : =========================================================== Elapsed time = 41.59999999999991 milliseconds First distance below threshold of 10 = 9.848857801796104 between points (469,567) and (473,576) |
| Here's a run with no match. |
|---|
| The following discussion has been closed. Please do not modify it. |
================================= FIND MIN DISTANCE, BY BRUTE FORCE : ================================= Elapsed time = 1354.275 milliseconds Min distance = 69.6419413859206 between points (530,514) and (505,579) ======================================================= FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE : ======================================================= Elapsed time = 1274.64 milliseconds No distance below threshold of 10 was found. =========================================================== FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD : =========================================================== Elapsed time = 54.590000000000146 milliseconds No distance below threshold of 10 was found. |
| Modified version to accelerate both loops |
|---|
| The following discussion has been closed. Please do not modify it. |
len1 = set1x.length;
len2 = set2x.length;
var time0 = performance.now();
var min_approach = 0;
var last_approach = 0;
var newI = 0;
var possible_approach = 0;
minDistSquared = thresh*thresh;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
distSquared = Math.pow((set1x[i] - set2x[j]),2)
+ Math.pow((set1y[i] - set2y[j]),2);
if (j == 0) {
min_approach = Math.sqrt( distSquared );
} else {
possible_approach = 1.5*Math.sqrt(distSquared) -
0.5*Math.sqrt(last_approach);
if( possible_approach < min_approach ) {
min_approach = possible_approach;
}
}
if (distSquared <= minDistSquared) {
minDistI = i;
minDistJ = j;
minDistSquared = distSquared;
i = 99999999; // Bail out of both loops by setting arbitrarily large loop values.
j = 99999999;
}
else {
newJ = j + Math.round(((Math.sqrt(distSquared)-thresh)/maxStep)-0.5); // Here's the important line.
if (newJ > j) {
j = newJ;
} // We skip ahead until the next j (set 2 pt) that could possibly
// be within the threshold range of the current i (set 1 pt).
last_approach = distSquared;
}
}
newI = i + Math.round((min_approach/maxStep)-0.5); // Here's the important line.
if (newI > i) {
i = newI;
}
}
var time1 = performance.now();
text += "<li>" + "Elapsed time = " + (time1 - time0) + " milliseconds" + "</li>";
if (i < 99999999) {
text += "<li>" + "No distance below threshold of "+ thresh +" was found." + "</li>";
}
else {
text += "<li>" + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points "
+ "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and "
+ "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + "</li>";
};
|
| Failed run 1. |
|---|
| The following discussion has been closed. Please do not modify it. |
================================= FIND MIN DISTANCE, BY BRUTE FORCE : ================================= Elapsed time = 761.73 milliseconds Min distance = 9.219544457292887 between points (510,502) and (512,511) ======================================================= FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE : ======================================================= Elapsed time = 67.47000000000003 milliseconds First distance below threshold of 10 = 9.219544457292887 between points (510,502) and (512,511) =========================================================== FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD : =========================================================== Elapsed time = 10.260000000000105 milliseconds First distance below threshold of 10 = 9.219544457292887 between points (510,502) and (512,511) Elapsed time = 6.7549999999999955 milliseconds No distance below threshold of 10 was found. |
| Failed run 2. |
|---|
| The following discussion has been closed. Please do not modify it. |
================================= FIND MIN DISTANCE, BY BRUTE FORCE : ================================= Elapsed time = 397.87500000000006 milliseconds Min distance = 9.486832980505138 between points (500,520) and (503,529) ======================================================= FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE : ======================================================= Elapsed time = 119.93499999999995 milliseconds First distance below threshold of 10 = 9.848857801796104 between points (499,520) and (503,529) =========================================================== FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD : =========================================================== Elapsed time = 26.25 milliseconds First distance below threshold of 10 = 9.848857801796104 between points (499,520) and (503,529) Elapsed time = 1.580000000000041 milliseconds No distance below threshold of 10 was found. |
newI = i + Math.round(((min_approach - thresh)/maxStep)-0.5); // Here's the important line.
| Fixed and somewhat optimized version |
|---|
| The following discussion has been closed. Please do not modify it. |
len1 = set1x.length;
len2 = set2x.length;
var time0 = performance.now();
var min_approach = 0;
var last_approach = 0;
var newI = 0;
var possible_approach = 0;
var min_x, max_x, min_y, max_y;
if( set1x[0] > set2x[0] ) {
min_x = Math.min.apply( null, set1x );
max_x = Math.max.apply( null, set2x );
} else if( set1x[0] < set2x[0] ) {
min_x = Math.min.apply( null, set2x );
max_x = Math.max.apply( null, set1x );
} else {
max_x = 0;
min_x = 0;
}
i = 0;
if( max_x + thresh >= min_x ) {
if( set1y[0] > set2y[0] ) {
min_y = Math.min.apply( null, set1y );
max_y = Math.max.apply( null, set2y );
} else if( set1y[0] < set2y[0] ) {
min_y = Math.min.apply( null, set2y );
max_y = Math.max.apply( null, set1y );
} else {
max_y = 0;
min_y = 0;
}
if( max_y + thresh >= min_y )
{
minDistSquared = thresh*thresh;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
distSquared = Math.pow((set1x[i] - set2x[j]),2)
+ Math.pow((set1y[i] - set2y[j]),2);
if (distSquared <= minDistSquared) {
minDistI = i;
minDistJ = j;
minDistSquared = distSquared;
i = 99999999; // Bail out of both loops by setting arbitrarily large loop values.
j = 99999999;
} else {
dist = Math.sqrt(distSquared);
if (j == 0) {
min_approach = dist;
} else {
possible_approach = 1.5*dist - 0.5*last_approach;
if( possible_approach < min_approach ) {
min_approach = possible_approach;
}
}
newJ = j + Math.round(((dist-thresh)/maxStep)-0.5); // Here's the important line.
if (newJ > j) {
j = newJ;
} // We skip ahead until the next j (set 2 pt) that could possibly
// be within the threshold range of the current i (set 1 pt).
last_approach = dist;
}
}
newI = i + Math.round(((min_approach - thresh)/maxStep)-0.5); // Here's the important line.
if (newI > i) {
i = newI;
}
}
}
}
|