[Last Call] Learn how to a build a cloud-first strategyRegister Now

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
6
Medium Priority
?
399 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
  • 3
  • 2
6 Comments
 
LVL 13

Accepted Solution

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

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

by:sdeller
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
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

Independent Software Vendors: 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

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…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and reading files 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

830 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