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
6
387 Views
Last Modified: 2012-05-11
Is it sufficient to check if x2 + y2 <= r2?
(x2 -> x squared)

Can I optimize this function?
0
Comment
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
  • Learn & ask questions
  • 3
  • 2
6 Comments
 
LVL 13

Accepted Solution

by:
Superdave earned 167 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

by:phoffric
phoffric earned 167 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

by:sdeller
sdeller earned 166 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 32

Expert Comment

by:phoffric
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

by:sdeller
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.
Did not think about this being some academic posting -- will be more vague in the future :-).
0
 
LVL 32

Expert Comment

by:phoffric
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
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…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

696 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question