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
344 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 167 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 32

Expert Comment

by:phoffric
Comment Utility
@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
Comment Utility
@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
Comment Utility
@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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
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…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

763 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

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now