{"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_post_was_ever_published":false,"_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}},"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":2581,"url":"https:\/\/chewett.co.uk\/blog\/2581\/pokemon-go-api-pokemon-evolutions-api\/","url_meta":{"origin":2168,"position":5},"title":"Pokemon Go API – Pokemon Evolutions API","author":"Chewett","date":"July 25, 2020","format":false,"excerpt":"This post talks about the latest API I have added to PoGoAPI.net, the Pokemon Evolutions API. What the Pokemon Evolutions API can be used for Some Pokemon can evolve into a stronger form by feeding them candy or meeting certain conditions. Once these conditions have been met you can press\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\/2020\/07\/pogo_api_evolution_posticon.jpg?fit=1200%2C628&ssl=1&resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/07\/pogo_api_evolution_posticon.jpg?fit=1200%2C628&ssl=1&resize=350%2C200 1x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/07\/pogo_api_evolution_posticon.jpg?fit=1200%2C628&ssl=1&resize=525%2C300 1.5x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/07\/pogo_api_evolution_posticon.jpg?fit=1200%2C628&ssl=1&resize=700%2C400 2x, https:\/\/i0.wp.com\/chewett.co.uk\/blog\/wp-content\/uploads\/2020\/07\/pogo_api_evolution_posticon.jpg?fit=1200%2C628&ssl=1&resize=1050%2C600 3x"},"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}]}}