<p>Before focusing on optimising the individual process of moving a point, consider how many points are being processed this way. This is likely to give a much more significant speed up if it hasn't yet been addressed.</p>

<p>For example, if every point on the screen is being tested against every circle, then most of the points are being checked needlessly.</p>

<p>If instead you divide the screen into a grid, with each grid cell keeping a list of all points currently within it, then each circle only needs to be checked against the points that appear in the grid cells which that circle overlaps. This allows checking a few tens of points, instead of hundreds or thousands.</p>

<p>This is a much bigger speed up than you can hope to achieve by optimising the circumference calculation, and after this you may find that further optimisation is not needed.</p>

CC BY-SA 3.0
2016-06-26T23:00:37.050Z
Is that even faster then doing a quick broad phase AABB check?
J.Doe
CC BY-SA 3.0
2016-06-26T23:10:09.330Z
If you do a bounding box check on each point, then that fast check is still being done on all 1000 points, for each circle. With a grid acceleration structure, if a circle only overlaps grid cells containing 30 points, none of the points outside those grid cells get checked at all, as they are not relevant.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T23:12:47.687Z
You will see the best speed up from a grid if the points are evenly spread over the screen. If the circles force all the points into a small area of the screen then the speed up will be less significant, and then you might need to look for other optimisations.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T23:16:39.597Z
A rough guide to whether this is the right answer is to observe the change of speed in your current implementation. Does it slow down (1) in proportion to the total number of points, or (2) in proportion to the number of points needing to be moved? (1) suggests you need an acceleration structure (such as a grid), while (2) suggests you need to optimise the movement of the points to the circumference. This answer is a best guess without seeing the code or the app running, so it may not be what you need.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T23:19:37.483Z
Also see Nathan Reed's comment on the question. I trust Nathan's intuition far more than my own.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T23:42:51.710Z
Ok I tried out broad phase, and grid phase.  Turns out the best one was doing a AABB check before anything else. Reading all of your comments (thankyou so much) has helped me make sense of why. The radius is growing, and points group up quickly. Thank much!
J.Doe
CC BY-SA 3.0
2016-06-26T22:53:24.400Z
2016-06-26T22:53:24.400Z
trichoplax is on Codidact now
<p>My goal is to take a point that is inside of a circle with a given radius and put it on the circumference.</p>

<p>Recently I have been normalizing the vector between the point and the center of the circle then multiplying that by the radius.  However I need (if possible) a less computationally expensive method because the distance formula is expensive.</p>

<p>Another thought I had was to use "atan2" to get the angle between the two points and then use sine and cosine multiplied by the radius to get the point on the circumference.</p>

<p>Which method do you think would be faster for the computer to process? Can you think of a faster method.</p>

<p><strong>Details about the simulation</strong>
This is an ios application written in swift.</p>

<p>Basically there are a bunch of particles moving around randomly. And the user is putting down fingers. Each finger is a circle with a radius that grows as time goes on. The part that is inneficent is that if the dot is ever inside of any of the circles (attached to touchscreen touches) that it goes on the circumference of the circle.</p>

CC BY-SA 3.0
2016-06-26T19:41:12.927Z
Normalizing is almost certainly faster than doing anything with trigonometry: a square root and a few adds and multiplies should be cheaper to evaluate than a sequence of trigonometric functions. I'm surprised to hear that normalizing is too expensive, as this should be quite fast on modern CPUs. Can you say more about the context of this problem? How have you determined that the normalization is causing a performance issue?
Nathan Reed
CC BY-SA 3.0
2016-06-26T19:45:40.577Z
The problem is their are tons of points that this needs to be done for. Anywhere from 400-1500 points have this done about every frame
J.Doe
CC BY-SA 3.0
2016-06-26T20:07:23.617Z
OK. 400-1500 points is a fair number, but not _that_ many; it should only take microseconds to normalize them if it's coded efficiently in a native-compiling language like C++. What language/framework/engine/etc are you using? How are you implementing the normalization process?
Nathan Reed
CC BY-SA 3.0
2016-06-26T20:09:11.737Z
Is the radius a variable or a constant?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T20:20:08.580Z
I added some details about the simulation above.
J.Doe
CC BY-SA 3.0
2016-06-26T20:21:56.127Z
The radius is variable. Right now I first check if it's in the circle using the squared distance. Then after that I subtract the center from the point and decide that by the sqrt of the distance squared. That is then multiplied by the radius.
J.Doe
CC BY-SA 3.0
2016-06-26T21:37:08.937Z
If you have existing code then it might help to edit it into the question so we can see it. There may be potential optimisations that are not obvious from the question wording.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T21:39:15.400Z
For example, from your last comment I would suggest storing the radius squared and comparing that to the distance squared if many points are compared against the same radius, but I wouldn't have thought to mention that just from the question wording.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T21:40:53.640Z
It would also help to know how often the point is inside the circle. If there are enough points that are outside the circle then it may be worth including a fast test that excludes points outside a bounding square.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T22:27:36.783Z
Does your current implementation use an acceleration structure such as a grid? If not that would be your answer (for a huge speed up). Let me know and I'll write something up if that's the case.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-06-26T23:04:47.543Z
BTW, although an acceleration structure may be helpful, I still think that even brute-force testing 1500 points against each of 10 circles (for instance) is not a huge amount of calculation, even on a mobile device. I would look into making sure it's coded efficiently, i.e. not having unnecessary function calls or pointer indirections, and possibly using SIMD for the calculations, before going to the trouble of implementing an acceleration structure.
Nathan Reed
CC BY-SA 3.0
2016-06-26T23:30:57.657Z
@NathanReed so as of now I am using a static math library of my own design that has functions like add subtract and multiply. It creates a new point struct and returns it. Would it be faster to now use the static class?
J.Doe
CC BY-SA 3.0
2016-06-26T23:36:51.247Z
@J.Doe Ideally you would look at the generated code (assembly language) to see how it's coming out. Compilers can often optimize away small function calls by inlining, and can keep small structs in registers, etc. I don't develop for Swift or iOS so I can't tell you in detail about that platform, but a quick google did turn up [this article on viewing disassembly in Swift](https://medium.com/swift-programming/secret-of-swift-performance-fcc5d2a437a8#.6e33qpynu).
Nathan Reed
CC BY-SA 3.0
2016-06-26T23:43:25.710Z
@NathanReed Looking at assembly code is a bit beyond my knowledge so far, I think I will just try and replace the static methods before the final build. Thanks!
J.Doe
<mathematics>
Fastest way to put a point on the circumference of a circle
J.Doe
# Fastest way to put a point on the circumference of a circle

(Asked by: username_0 on 2016-06-26)

My goal is to take a point that is inside of a circle with a given radius and put it on the circumference.

Recently I have been normalizing the vector between the point and the center of the circle then multiplying that by the radius. However I need (if possible) a less computationally expensive method because the distance formula is expensive.

Another thought I had was to use "atan2" to get the angle between the two points and then use sine and cosine multiplied by the radius to get the point on the circumference.

Which method do you think would be faster for the computer to process? Can you think of a faster method.

**Details about the simulation**
This is an ios application written in swift.

Basically there are a bunch of particles moving around randomly. And the user is putting down fingers. Each finger is a circle with a radius that grows as time goes on. The part that is inneficent is that if the dot is ever inside of any of the circles (attached to touchscreen touches) that it goes on the circumference of the circle.

**Tags:** mathematics

> **Comments:**
> **username_1**: Normalizing is almost certainly faster than doing anything with trigonometry: a square root and a few adds and multiplies should be cheaper to evaluate than a sequence of trigonometric functions. I'm surprised to hear that normalizing is too expensive, as this should be quite fast on modern CPUs. Can you say more about the context of this problem? How have you determined that the normalization is causing a performance issue?  
> **username_0**: The problem is their are tons of points that this needs to be done for. Anywhere from 400-1500 points have this done about every frame  
> **username_1**: OK. 400-1500 points is a fair number, but not _that_ many; it should only take microseconds to normalize them if it's coded efficiently in a native-compiling language like C++. What language/framework/engine/etc are you using? How are you implementing the normalization process?  
> **username_2**: Is the radius a variable or a constant?  
> **username_0**: I added some details about the simulation above.  
> **username_0**: The radius is variable. Right now I first check if it's in the circle using the squared distance. Then after that I subtract the center from the point and decide that by the sqrt of the distance squared. That is then multiplied by the radius.  
> **username_2**: If you have existing code then it might help to edit it into the question so we can see it. There may be potential optimisations that are not obvious from the question wording.  
> **username_2**: For example, from your last comment I would suggest storing the radius squared and comparing that to the distance squared if many points are compared against the same radius, but I wouldn't have thought to mention that just from the question wording.  
> **username_2**: It would also help to know how often the point is inside the circle. If there are enough points that are outside the circle then it may be worth including a fast test that excludes points outside a bounding square.  
> **username_2**: Does your current implementation use an acceleration structure such as a grid? If not that would be your answer (for a huge speed up). Let me know and I'll write something up if that's the case.  
> **username_1**: BTW, although an acceleration structure may be helpful, I still think that even brute-force testing 1500 points against each of 10 circles (for instance) is not a huge amount of calculation, even on a mobile device. I would look into making sure it's coded efficiently, i.e. not having unnecessary function calls or pointer indirections, and possibly using SIMD for the calculations, before going to the trouble of implementing an acceleration structure.  
> **username_0**: @username_1 so as of now I am using a static math library of my own design that has functions like add subtract and multiply. It creates a new point struct and returns it. Would it be faster to now use the static class?  
> **username_1**: @username_0 Ideally you would look at the generated code (assembly language) to see how it's coming out. Compilers can often optimize away small function calls by inlining, and can keep small structs in registers, etc. I don't develop for Swift or iOS so I can't tell you in detail about that platform, but a quick google did turn up [this article on viewing disassembly in Swift](https://medium.com/swift-programming/secret-of-swift-performance-fcc5d2a437a8#.6e33qpynu).  
> **username_0**: @username_1 Looking at assembly code is a bit beyond my knowledge so far, I think I will just try and replace the static methods before the final build. Thanks!  

---

## 1 answers

### Answer by username_2 on 2016-06-26. Score: 2 | Accepted answer

Before focusing on optimising the individual process of moving a point, consider how many points are being processed this way. This is likely to give a much more significant speed up if it hasn't yet been addressed.

For example, if every point on the screen is being tested against every circle, then most of the points are being checked needlessly.

If instead you divide the screen into a grid, with each grid cell keeping a list of all points currently within it, then each circle only needs to be checked against the points that appear in the grid cells which that circle overlaps. This allows checking a few tens of points, instead of hundreds or thousands.

This is a much bigger speed up than you can hope to achieve by optimising the circumference calculation, and after this you may find that further optimisation is not needed.

> **Comments:**
> **username_0**: Is that even faster then doing a quick broad phase AABB check?  
> **username_2**: If you do a bounding box check on each point, then that fast check is still being done on all 1000 points, for each circle. With a grid acceleration structure, if a circle only overlaps grid cells containing 30 points, none of the points outside those grid cells get checked at all, as they are not relevant.  
> **username_2**: You will see the best speed up from a grid if the points are evenly spread over the screen. If the circles force all the points into a small area of the screen then the speed up will be less significant, and then you might need to look for other optimisations.  
> **username_2**: A rough guide to whether this is the right answer is to observe the change of speed in your current implementation. Does it slow down (1) in proportion to the total number of points, or (2) in proportion to the number of points needing to be moved? (1) suggests you need an acceleration structure (such as a grid), while (2) suggests you need to optimise the movement of the points to the circumference. This answer is a best guess without seeing the code or the app running, so it may not be what you need.  
> **username_2**: Also see username_1 username_1's comment on the question. I trust username_1's intuition far more than my own.  
> **username_0**: Ok I tried out broad phase, and grid phase.  Turns out the best one was doing a AABB check before anything else. Reading all of your comments (thankyou so much) has helped me make sense of why. The radius is growing, and points group up quickly. Thank much!  

---

