Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# 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

Posted on 2011-02-22
Medium Priority
395 Views
Is it sufficient to check if x2 + y2 <= r2?
(x2 -> x squared)

Can I optimize this function?
0
Question by:dshrenik
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 2

LVL 13

Accepted Solution

Superdave earned 668 total points
ID: 34957031
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

LVL 32

Assisted Solution

phoffric earned 668 total points
ID: 34957346
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

LVL 1

Assisted Solution

sdeller earned 664 total points
ID: 34964746
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

LVL 32

Expert Comment

ID: 34966470
@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

LVL 1

Expert Comment

ID: 34970811
@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

LVL 32

Expert Comment

ID: 34973167
@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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
###### Suggested Courses
Course of the Month9 days, 17 hours left to enroll