3
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathan Reed
    Jun 26, 2016 at 19:41
  • $\begingroup$ 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 $\endgroup$
    – J.Doe
    Jun 26, 2016 at 19:45
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathan Reed
    Jun 26, 2016 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathan Reed
    Jun 26, 2016 at 23:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Nathan Reed
    Jun 26, 2016 at 23:36

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Is that even faster then doing a quick broad phase AABB check? $\endgroup$
    – J.Doe
    Jun 26, 2016 at 23:00
  • $\begingroup$ 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. $\endgroup$
    – trichoplax is on Codidact now
    Jun 26, 2016 at 23:10
  • $\begingroup$ 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. $\endgroup$
    – trichoplax is on Codidact now
    Jun 26, 2016 at 23:12
  • $\begingroup$ 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. $\endgroup$
    – trichoplax is on Codidact now
    Jun 26, 2016 at 23:16
  • 2
    $\begingroup$ 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! $\endgroup$
    – J.Doe
    Jun 26, 2016 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.