Wikipedia:Reference desk/Archives/Computing/2016 May 22

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.

May 22

Ban mobile devices from website

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)

You can't. You can do somethings which will work some of the time, but not all of the time. Even more so since there's no clear distinction between a tablet and a phone nowadays and resolutions, zoom levels etc are so variable. (I don't think that many people will call a 10" device a phone even though some of them can make phone calls over a mobile network. But some people will definitely call a 6.5" device a phone, probably even a 7". Yet there are also devices e.g. with no SIM card or mobile network support unlikely to be called phones in that size range.) Plus anything you can do will be trivial to circumvent. Except requiring a plugin like Silverlight or Flash not support or very poorly supported on phones but that will also affect most tablets. Also any advice we can give you runs a strong risk of unintentionally providing legal advice which we don't do here. You need to speak to whoever gave you the rights and ask them what they expect you to do. Nil Einne (talk) 23:47, 22 May 2016 (UTC)

It's possible, in a crude way, to look at a request's user-agent field, and imagine you understand what kind of device the visitor has. Someone might think they can distinguish "a computer" from "a phone". But, as Nil Einne notes, the practical boundary between a computer, a laptop, a subnotebook, a chromebook, a tablet, a phablet, a flagship phone, a mainstream screenphone, and all kinds of cheaper screen phones, is impossibly blurred. Add in the orthogonal dimensions of things like rasperry pis and related OpenELEC-type devices, smart TVs, game consoles, and hotel and car and aviation media devices, and "pc and tablet but not for mobile phones" becomes an ever more arbitrary, and meaningless, distinction. If someone is imposing a legal (contractual) distinction on you, they need to be much more specific about what that really means. -- Finlay McWalter··–·Talk 00:05, 23 May 2016 (UTC)

It's not perfect, but you could use the viewport of a device viewing your website to determine what type of device is being used. See [1] and [2]. Assuming anything below a certain screen size is a phone (what size? good question) and anything above is a tablet or computer, you could use CSS to display a notice to phone users (smaller screens, that is) that they must access the website using a tablet or computer (larger screen). But I agree with the others that you should get a more specific idea of what devices aren't allowed and why, in order to find the best option. clpo13_(talk) 00:13, 23 May 2016 (UTC)

Also, I think DPI and resolution play a big part of the viewport, so there's no guarantee you could filter solely by physical screen size. Feel free to correct me if I'm wrong. clpo13_(talk) 00:16, 23 May 2016 (UTC)

Somewhat terrifyingly, a Samsung Galaxy S7 phone has a 2560×1440 screen, much better than any TV or monitor I (a cheapskate, admittedly) own. DPI is, as you say, a somewhat better test. But it's still a daft test. Video rights (the OP's question) are usually apportioned based on access type (download vs streaming) or simply resolution - the S7 is better than HDTV and well into what current blu-ray provides. -- Finlay McWalter··–·Talk 00:30, 23 May 2016 (UTC)

This sounds like a borderline legal request. Presumably you have signed some sort of licensing agreement. The terms of that agreement should spell out what measures you are expected to take. If the agreement is unclear, you should talk to a lawyer. As noted above, technically there's really no airtight way to do it, since if people figure out what you're doing to filter devices (like looking at the User-Agent header sent for HTTP connections), they can try to circumvent it. To try to stop this, some countries outlaw attempting to circumvent access restriction measures, like in the U.S. DMCA, though enforcement tends to be, well, not very strict. --71.110.8.102 (talk) 03:27, 23 May 2016 (UTC)

Determine if 2 random walk point sets are within a threshold distance

Here's my code to implement my suggested method of solving the previous Ref Desk Q.

My assumptions:

• The two sets start 100 pixels away. I put the start points horizontal from each other at (500,500) and (500,600), but that shouldn't matter.

• Each random walk step has a 1/3 chance of increasing the X by 1, 1/3 of decreasing it by 1, and 1/3 of staying put. The same logic applies in the Y direction. So, the maximum step size = sqrt(2).

• I put 10,000 points in each set. So, that's 100 million checks by the brute force method. (My method can handle more, but the brute force approach can't.)

• A threshold distance of 10.

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> <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 = ' '; //Find the minimum distance (the hard way): text += " ================================= "; text += " FIND MIN DISTANCE, BY BRUTE FORCE : "; text += " ================================= "; 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 += " " + "Elapsed time = " + (time1 - time0) + " milliseconds" + " "; text += " " + "Min distance = " + Math.sqrt(minDistSquared) + " between points " + "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and " + "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + " "; text += " " + " " + " "; //Find if the minimum distance is below the threshhold (the hard way): text += " ======================================================= "; text += " FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY BRUTE FORCE : "; text += " ======================================================= "; 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 += " " + "Elapsed time = " + (time1 - time0) + " milliseconds" + " "; if (i < 99999999) { text += " " + "No distance below threshold of "+ thresh +" was found." + " "; } else { text += " " + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points " + "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and " + "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + " "; }; text += " " + " " + " "; //Find if the minimum distance is below the threshhold (the elegant way): text += " =========================================================== "; text += " FIND IF MIN DISTANCE IS BELOW THRESHOLD, BY ELEGANT METHOD : "; text += " =========================================================== "; 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 += " " + "Elapsed time = " + (time1 - time0) + " milliseconds" + " "; if (i < 99999999) { text += " " + "No distance below threshold of "+ thresh +" was found." + " "; } else { text += " " + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points " + "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and " + "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + " "; }; text += " "; 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.

Why don't you just draw a circle of radius x around each point, form two sets from the union of all the points in each group, and check if there is any overlap in the sets? 2001:630:12:2428:B4A3:2D78:5C78:CD33 (talk) 02:03, 22 May 2016 (UTC)

That's an interesting suggestion. It sounds inefficient, at least in the case of comparing 2 point sets with a large threshold. With my assumptions, that would mean calculating those circles for each of 20,000 points in my trial sets, and with a threshold of 10, each circle would have some 314 pixels in it. That would mean we would need to process some 6,280,000 pixels, but that would quickly jump to 628 million, if the threshold were increased to 100. However, if you had many sets of points to compare, and a small threshold, ideally 0, then creating such a "blob" for each might turn out to be the best method. It sounds a bit more involved to code, though, particularly dynamically allocating the size of the array for each blob (I'd take a first pass to build a min-max rectangle, then add the threshold as an offset on each side). Alternatively you could just allocate a fixed array that's sure to be bigger than you will ever need, but that's not very memory efficient.

Note that I was assuming you meant solid circles, but it's also possible to just draw the perimeters, and look for overlaps there. However, you would need to draw at least 1 of the set's circles at least 2 pixels wide, or they might overlap without having any perimeter pixels in common. Efficiently drawing the perimeter pixels would require using polar coords, or spherical, if we extend it into 3D voxels. StuRat (talk) 02:21, 22 May 2016 (UTC)

I don't understand how your optimization in case 3 can work. The arrays are not sorted, so how can you know what you're skipping when you jump ahead in the array? The items you're skipping may be ones that you care about. Also, you'll get better performance by just multiplying x*x rather than doing Math.pow(x,2), especially since it's in an inner loop. CodeTalker (talk) 15:35, 22 May 2016 (UTC)

1) I didn't know that it mattered how you square the number. Let me do some benchmarking and, if it is so, I will change it. Have a link that explains why it is better ?

2) Remember that both point sets are a random walk, meaning we can only move a small distance from each point to the next. See my 2nd assumption, where I said it can only walk a max of 1 in X and 1 in Y from the previous point. My code only relies on one of the two point sets being a random walk, but it works fine if they both are, too. (There may be a way to get better optimization if we require both sets to be random walks, but the coding would be more complex. I'd be interested in discussing this, if anyone wants to take it on.) StuRat (talk) 17:20, 22 May 2016 (UTC)

Since every browser has their own Javascript implementation it may vary depending on the browser, but usually Math.pow is implemented using a logarithm and exponential, which is much slower than a single multiply. Some browsers may be smart enough to convert the pow into a multiply, but the pow will never be faster. See the graph here [3]. CodeTalker (talk) 18:05, 22 May 2016 (UTC)

OK, thanks. StuRat (talk) 19:08, 22 May 2016 (UTC)

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 += " " + "Elapsed time = " + (time1 - time0) + " milliseconds" + " "; if (i < 99999999) { text += " " + "No distance below threshold of "+ thresh +" was found." + " "; } else { text += " " + "First distance below threshold of "+ thresh +" = " + Math.sqrt(minDistSquared) + " between points " + "(" + set1x[minDistI] + "," + set1y[minDistI] + ")" + " and " + "(" + set2x[minDistJ] + "," + set2y[minDistJ] + ")" + " "; };

You can go considerably faster in the typical case by using the values observed in the j-loop to accelerate the i-loop. The code sample above is a not-very-optimized example of how one can approach that. Dragons flight (talk) 20:07, 22 May 2016 (UTC)

Thanks. I tried it out, and it usually seems much quicker, but is occasionally slightly slower, and on rare occasions, it's wrong. Here's a couple cases that failed (the last 2 lines of each are your code):

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.

Dragons flight, if you can discuss the logic you intended, maybe we can find the bug in the code and fix it. StuRat (talk) 21:56, 22 May 2016 (UTC)

Eh, sorry. I think the newI line should have been:

   newI = i + Math.round(((min_approach - thresh)/maxStep)-0.5); // Here's the important line.

Dragons flight (talk) 11:47, 23 May 2016 (UTC)

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; } } } }

Try this. Dragons flight (talk) 12:43, 23 May 2016 (UTC)