{"id":2168,"date":"2019-04-27T13:00:33","date_gmt":"2019-04-27T12:00:33","guid":{"rendered":"https:\/\/chewett.co.uk\/blog\/?p=2168"},"modified":"2019-04-28T22:59:58","modified_gmt":"2019-04-28T21:59:58","slug":"improving-closeness-algorithm-by-precomputing-r","status":"publish","type":"post","link":"https:\/\/chewett.co.uk\/blog\/2168\/improving-closeness-algorithm-by-precomputing-r\/","title":{"rendered":"Improving Closeness algorithm by precomputing R"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

This post is a continuation of a previous post where I talked about how you can check if two points are closer than a distance<\/a>. This improves it by adding the possibility to precompute R.<\/p>\n\n\n\n\n\n\n\n

Why precompute R<\/h2>\n\n\n\n

As discussed in the previous post one of the slowest parts of working out if two points are closer than R is squaring R. For many cases you have a constant R which means R squared is also a constant.<\/p>\n\n\n\n

For cases where you are performing collision detection you will have a fixed distance that two objects will collide. This means that if we precompute the distance squared we save time we we only have to do it once rather than N times. Where N is the number of times the algorithm is called.<\/p>\n\n\n\n

Changing our function to accept R squared<\/h2>\n\n\n\n

Our current function is reproduced below.<\/p>\n\n\n

\nfunction arePointsCloserThanR(x1, y1, x2, y2, r) {\n    \/\/Shortcut for the maths. This creates a box region where we know anything\n    \/\/ that lies outside the box definitely isn't closer than R. If this\n    \/\/is true then return false and we don't have to do complex (slow) maths.\n    if(Math.abs(x1 - x2) > r || Math.abs(y1 - y2) > r) {\n        return false;\n    }\n \n    \/\/We need to do maths, Lets cheat and square R instead of a slower sqrt\n    var rSquared = Math.pow(r, 2);\n \n    \/\/If R Squared is bigger then the two distances squared, then return\n    \/\/ true as the points are closer\n    return rSquared > (Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2));\n}\n<\/pre><\/div>\n\n\n
We can add a sixth parameter to the call which can be used to pass in the precomputed value. This then changes our function to be the following.<\/p>\n\n\n
\nfunction arePointsCloserThanR2(x1, y1, x2, y2, r, r2) {\n    \/\/Shortcut for the maths. This creates a box region where we know anything\n    \/\/ that lies outside the box definitely isn't closer than R. If this\n    \/\/is true then return false and we don't have to do complex (slow) maths.\n    if(Math.abs(x1 - x2) > r || Math.abs(y1 - y2) > r) {\n        return false;\n    }\n \n    \/\/We need to do maths, Lets cheat and square R instead of a slower sqrt\n    var rSquared = r2 || Math.pow(r, 2);\n \n    \/\/If R Squared is bigger then the two distances squared, then return\n    \/\/ true as the points are closer\n    return rSquared > (Math.pow(x1 - x2, 2) + Math.pow((y1 - y2), 2));\n}\n<\/pre><\/div>\n\n\n
Above in JavaScript if the sixth parameter is not passed in it will be undefined. So our line to calculate R squared becomes.<\/p>\n\n\n
\nvar rSquared = r2 || Math.pow(r, 2);\n<\/pre><\/div>\n\n\n
This will use the value of r2<\/code> as rSquared<\/code> if it  has been passed in, or do the computation inline. This allows us to optionally pass in the value of R squared, with little change to the function.<\/p>\n\n\n\n
Summary<\/h2>\n\n\n\n
By providing an option to pass in the value of R squared this can be precomputed and passed in.<\/p>\n\n\n\n
By doing this for anything that is repeatedly used as R you can improve the speed of the function by a decent factor.<\/p>\n\n\n\n
If the distance checking function is slow and you repeatedly use a fixed R it is recommended to implement this additional function parameter and precompute R squared.<\/p>\n","protected":false},"excerpt":{"rendered":"
This post is a continuation of a previous post where I talked about how you can check if two points are closer than a distance. This improves it by adding the possibility to precompute R.<\/p>\n","protected":false},"author":1,"featured_media":2173,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[98],"tags":[339,229,219,338],"class_list":["post-2168","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-software","tag-2d-points","tag-d3-js","tag-data-visualisation","tag-distance"],"wppr_data":{"cwp_meta_box_check":"No"},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/04\/improving_closeness_algo.jpg?fit=800%2C800&ssl=1","jetpack_shortlink":"https:\/\/wp.me\/p2toWX-yY","jetpack_sharing_enabled":true,"jetpack-related-posts":[{"id":2102,"url":"https:\/\/chewett.co.uk\/blog\/2102\/checking-if-two-points-are-closer-than-a-distance\/","url_meta":{"origin":2168,"position":0},"title":"Checking if two points are closer than a distance","author":"Chewett","date":"April 3, 2019","format":false,"excerpt":"This blog post talks about how you can quickly check if two point are closer than a specific distance. How to calculate the distance between two points To calculate the distance between two points you can use Pythagoras Theorem. This states that for a right angled triangle you can find\u2026","rel":"","context":"In "Software"","block_context":{"text":"Software","link":"https:\/\/chewett.co.uk\/blog\/category\/software\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/03\/two_points_closer_distance-1.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/03\/two_points_closer_distance-1.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/03\/two_points_closer_distance-1.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/03\/two_points_closer_distance-1.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":1759,"url":"https:\/\/chewett.co.uk\/blog\/1759\/pokemon-go-api-buddy-candy-distances\/","url_meta":{"origin":2168,"position":1},"title":"Pokemon Go API – Buddy Candy Distances","author":"Chewett","date":"November 28, 2018","format":false,"excerpt":"This post talks about the newest Pokemon Go API, the Buddy Candy Distances API at\u00a0pogoapi.net. Pokemon Buddy Candy Distances When you make a Pokemon your buddy, after a certain distance walked with them you will get 1 candy from them. This distance depends on the specific Pokemon. The current buddy\u2026","rel":"","context":"In "Software"","block_context":{"text":"Software","link":"https:\/\/chewett.co.uk\/blog\/category\/software\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/pogo_api_buddy_distances.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/pogo_api_buddy_distances.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/pogo_api_buddy_distances.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/pogo_api_buddy_distances.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":1476,"url":"https:\/\/chewett.co.uk\/blog\/1476\/using-the-dht22-temperature-sensor-with-a-wemos-d1-mini-esp8266\/","url_meta":{"origin":2168,"position":2},"title":"Using the DHT22 Temperature Sensor with a WeMos D1 Mini (ESP8266)","author":"Chewett","date":"September 22, 2018","format":false,"excerpt":"In this blog post I talk about the additional steps needed to use the DHT22 temperature sensor with a WeMos D1 Mini (ESP8266) with the Arduino IDE. Differences from running a DHT22 on an Arduino There are two major differences to bear in mind when using the DHT22 on a\u2026","rel":"","context":"In "Electronics"","block_context":{"text":"Electronics","link":"https:\/\/chewett.co.uk\/blog\/category\/electronics\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/09\/dht22_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/09\/dht22_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/09\/dht22_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/09\/dht22_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":1412,"url":"https:\/\/chewett.co.uk\/blog\/1412\/using-the-ds18b20-temperature-sensor-with-a-wemos-d1-mini-esp8266\/","url_meta":{"origin":2168,"position":3},"title":"Using the DS18B20 Temperature Sensor with a WeMos D1 Mini (ESP8266)","author":"Chewett","date":"November 21, 2018","format":false,"excerpt":"In this blog post I talk about the additional steps needed to use the DS18B20 onewire temperature sensor with a WeMos D1 Mini (ESP8266) using the Arduino IDE. Important differences compared to using the DS18B20 on an Arduino There is one major difference to bear in mind when using the\u2026","rel":"","context":"In "Electronics"","block_context":{"text":"Electronics","link":"https:\/\/chewett.co.uk\/blog\/category\/electronics\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/wd18b20_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/wd18b20_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/wd18b20_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/11\/wd18b20_on_wemos_d1_mini.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":2294,"url":"https:\/\/chewett.co.uk\/blog\/2294\/implementing-the-perforce-helix-in-d3-js\/","url_meta":{"origin":2168,"position":4},"title":"Implementing the Perforce Helix in D3.js","author":"Chewett","date":"July 27, 2019","format":false,"excerpt":"This blog post talks about the steps I took to implement the Perforce helix in D3.js. What is the Perforce Helix? Perforce is a company that makes a version control system of the same name. One of their main products has been recently renamed Perforce Helix Core. Lately on their\u2026","rel":"","context":"In "Software"","block_context":{"text":"Software","link":"https:\/\/chewett.co.uk\/blog\/category\/software\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/d3_perforce_helix-2.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/d3_perforce_helix-2.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/d3_perforce_helix-2.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2019\/07\/d3_perforce_helix-2.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]},{"id":1166,"url":"https:\/\/chewett.co.uk\/blog\/1166\/better-positioning-of-text-using-measuretext-with-html5-canvas\/","url_meta":{"origin":2168,"position":5},"title":"Better positioning of text using measureText with HTML5 Canvas","author":"Chewett","date":"May 5, 2018","format":false,"excerpt":"In this tutorial I am extending the previous animation example by better positioning the text using measureText with the HTML5 canvas. The problem with positioning text When positioning\u00a0text you will sometimes want to know the width and height so that you can centre it on the canvas. However this isn't\u2026","rel":"","context":"In "Software"","block_context":{"text":"Software","link":"https:\/\/chewett.co.uk\/blog\/category\/software\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/05\/measure_text_html5_canvas.jpg?fit=800%2C800&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/05\/measure_text_html5_canvas.jpg?fit=800%2C800&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/05\/measure_text_html5_canvas.jpg?fit=800%2C800&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2018\/05\/measure_text_html5_canvas.jpg?fit=800%2C800&ssl=1&resize=700%2C400 2x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2168","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/comments?post=2168"}],"version-history":[{"count":1,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2168\/revisions"}],"predecessor-version":[{"id":2175,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/posts\/2168\/revisions\/2175"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/media\/2173"}],"wp:attachment":[{"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/media?parent=2168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/categories?post=2168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/chewett.co.uk\/blog\/wp-json\/wp\/v2\/tags?post=2168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}