• C

# Given a circle (point + radius) and point, write a function that returns true if the point is in the circle, and false if it's not. Also, we discussed ways we could optimize the function

Is it sufficient to check if x2 + y2 <= r2?
(x2 -> x squared)

Can I optimize this function?
###### Who is Participating?

Commented:
It would be (x-xr)2 + (y-yr)2 <= r2 where (xr,yr) is the center of the circle.  It might not be centered on (0,0).

Possibly multiplying the numbers by themselves instead of "squaring" might be considered an optimization, depending on how a computer language might implement squaring.  Your using squaring instead of taking square roots is already a major optimization over a really naive way you could have done it.

0

Commented:
Consider a square bounding box around the circle. If the point is not in the square, then it is not in the circle. This is an approach used when you have many points, most of which are not in the circle.

Note that there is no squaring in this initial filter test. In the filter test, there are two conditions, one to test the x interval, and one to the y interval. If the first test fails (as often is the case), then the 2nd test need not be performed.
0

Commented:
First note that optimization of a computation depends on the cost of each computation, which depends on the processor and what processing units are available.  On an Array Processor I worked on, there was one multiply and one add per cycle, so if a computation could be resolved to fewer steps involving one add and one multiply, then it was optimized.  On that processor, that sometimes meant converting an expression to have more mutiplies so it had less adds.

In siome processors, it is the case that multiply is more expensive than an add.  So the following two "optimizations" which have no multiplies might actually result in a faster algorithm:
1. Determine if the poiint cannot be in he circle by checking if abs(x-xr) >r or y-yr > r, either of which is suffidient to know the point is outside outside the box that just fits outside the circle and thus is outside the circle.
2. Determine if the point is definitely inside the circle by checking if (abs(x-xr)+abs(y-yr)) <= r.  If it is, then the point is inside the diamond square that just fits within the circle and thus is in the circle.  Other linear checks are possible, but the arithmetic involves multiplications, so you might as well
In any event, if 1 does not indicate the point is outside the circle and 2 does not indicate it is inside the circle, then you still must must check
3. (x-xr)2 + (y-yr)2 <= r2.
to determine if the point really is inside or outside the circle.

Note that on many processors the size of code can impact speed (due to caching and to instruction loading) and futher tests may be sub-optimal, so computing 1, 2 and then if necessary 3 could actually be slower except perhaps for points that are excluded by the first test in 1.
0

Commented:
@sdeller,
>>  Determine if the poiint cannot be in he circle by checking if abs(x-xr) >r or y-yr > r, either of which is suffidient to know the point is outside outside the box that just fits outside the circle and thus is outside the circle.

When referring to another post, it is expected that you refer to the author of that post and the post itself, as in:

As phoffric noted in http:#34957346 - "Consider a square bounding box around the circle. If the point is not in the square, then it is not in the circle." Here are the formula for doing this:
abs(x-xr) >r or y-yr > r, either of which is sufficient to know the point is outside outside the box that just fits outside the circle and thus is outside the circle.

Likewise, for your 3rd item you should reference Superdave's first post.

In fact, since you did not add anything to points 1 and 3 that were not already said, then you need not repeat them - just refer to the posts.

Now, I did not give the formulas because it is possible that this is an academic assignment, and was waiting for feedback from the author if he had trouble implementing them; and then may have asked the question about whether the question is for academic purposes.
0

Commented:
@phoffric
point taken -- I am new to posting here.  Wanted to be helpful by laying out the full algorithm.
I thought the restatement of items 1 and 3 was obvious, with 1 giving more detail and 3 makiing it clear that the actual test alwasy had to be done.
0

Commented:
@sdeller,
No problem. Good to have another poster.

So many EE policies - hard to read all of them. You can read the section Read previous posts before commenting

When in doubt about the academic nature of the question (which includes self-study), feel free to ask the author.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.