## FAST way to determine whether a point is in a circle???

### FAST way to determine whether a point is in a circle???

> What is the recommended way of determining whether or not a point is within
> the dimensions of a circle?

> I'm currently at home and don't have access to the usual texts on matters such
> as this!!!

I don't know if this is a serious question or not.  Assuming that it
is serious, I'm wondering if you bothered to think about it for a few
minutes.  If you have the circle center and radius, you just need to
determine if the distance from the center to the point is greater than
the radius.  I would expect most *age children could figure this out
in a few minutes (I'm going to ask my children to solve this later this
evening to find out for sure).  In any case, here is pseudo-code to do
the job:

Given a circle definition (center and radius):

And a point definition:
point_x, point_y

Determine if the point is outside the circle:
x_length = circle_x - point_x
y_length = circle_y - point_y
point_distance = square_root(x_length * x_length + y_length * y_length)
it_is_outside
else
it_is_inside

---

Sun Microsystems

"Proofread carefully to see if you any words out."

### FAST way to determine whether a point is in a circle???

|>
|> > What is the recommended way of determining whether or not a point is within
|> > the dimensions of a circle?
|>
|> Given a circle definition (center and radius):
|>
|> And a point definition:
|>   point_x, point_y
|>
|> Determine if the point is outside the circle:
|>   x_length = circle_x - point_x
|>   y_length = circle_y - point_y
|>   point_distance = square_root(x_length * x_length + y_length * y_length)
|>           it_is_outside
|>   else
|>           it_is_inside

- Steve
--
"...an ENTIRE DAY spent grooming."

### FAST way to determine whether a point is in a circle???

Hello,

What is the recommended way of determining whether or not a point is within
the dimensions of a circle?

I'm currently at home and don't have access to the usual texts on matters such
as this!!!

Stuart.

--
Stuart Booth

### FAST way to determine whether a point is in a circle???

>> What is the recommended way of determining whether or not a point is within
>> the dimensions of a circle?
>I don't know if this is a serious question or not.  Assuming that it
>is serious, I'm wondering if you bothered to think about it for a few
>minutes.

[pseudo-code deleted]

Um. It seems like a few more minutes thought might be in order if the title is
"FAST way..." :-)
Square roots are relatively expensive, and in this case quite unnecessary...

{
delta.x  =  point.x - centre.y
delta.y  =  point.y - centre.y

}

If it's likely that a significant proportion of your points are going to lie
well outside the circle (more than about 1.5 radii from the centre) then the
following version (which pretests an obvious case to avoid multiplication) will
run faster still...

{
delta.x  =  point.x - centre.y
delta.y  =  point.y - centre.y

then return false

}

damian
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

where: Dept. Computer Science        phone: +61-3-565-5184
Monash University               fax: +61-3-565-5146
Clayton 3168                  quote: "A pessimist is never disappointed."
AUSTRALIA

### FAST way to determine whether a point is in a circle???

>the radius.  I would expect most *age children could figure this out
>in a few minutes (I'm going to ask my children to solve this later this
>evening to find out for sure).  In any case, here is pseudo-code to do
>the job:

>    point_distance = square_root(x_length * x_length + y_length * y_length)
>            it_is_outside
>    else
>            it_is_inside

>---

>Sun Microsystems

>"Proofread carefully to see if you any words out."

I would also expect most *age children to figure out that you don't
need the square root operation; you can base your comparison on the
squares of the distances.

point_distance = x_length * x_length + y_length * y_length

[etc]

Now go back to debugging that Solaris crap! :)

### FAST way to determine whether a point is in a circle???

>> What is the recommended way of determining whether or not a point is within
>> the dimensions of a circle?

>> I'm currently at home and don't have access to the usual texts on matters such
>> as this!!!

>I don't know if this is a serious question or not.  Assuming that it
>is serious, I'm wondering if you bothered to think about it for a few
>minutes.  If you have the circle center and radius, you just need to
>determine if the distance from the center to the point is greater than
>the radius.  I would expect most *age children could figure this out
>in a few minutes (I'm going to ask my children to solve this later this
>evening to find out for sure).  In any case, here is pseudo-code to do
>the job:

Now now Scott, let's not get TOO high and mighty. I know people who are
brilliant programmers but don't know a thing when it comes to basic math
like this.

Quote:>Given a circle definition (center and radius):

>And a point definition:
>    point_x, point_y

>Determine if the point is outside the circle:
>    x_length = circle_x - point_x
>    y_length = circle_y - point_y
>    point_distance = square_root(x_length * x_length + y_length * y_length)
>            it_is_outside
>    else
>            it_is_inside

I believe he was asking for a FAST method, which also indicates that he
may already know how to do this and simply wants to find out if there are
any faster ways. The square root in the algorithm above is horrendously
slow and could cause errors for points close to the circle itself. A much
faster and more accurate method is:

xlength = circle_x - point_x
ylength = circle_y - point_y

if (xlength * xlength + ylength * ylength) < (radius * radius) then
it_is_inside
else
it_is_not_inside

Note that if the two terms above are equal then the point is on the
circle.

Mark

--------------------------------------------------------------------------
Mark Feldman                               \\_==_o    Skydivers do

--------------------------------------------------------------------------

### FAST way to determine whether a point is in a circle???

: What is the recommended way of determining whether or not a point is within
: the dimensions of a circle?

I would guess it is the following:

Point (X,Y)
Test circle of radius squared = R2, centred at (CX,CY)

DX = X - CX
DY = Y - DY

if( DX*DX + DY*DY > R2 )
point is outside circle
else
point is inside circle
endif

That's 2 subtractions, one addition, and two multiplies per check.
(One more multiplication if you have to calculate the squared radius
on the fly.)

--
-----------------------------------------------------------------------

### FAST way to determine whether a point is in a circle???

Quote:> What is the recommended way of determining whether or not a point is within
> the dimensions of a circle?

How is the circle defined?  The answer is different if you know the center
and the radius than it is if you only know three points the circle passes
through.  If you do have the center and radius, Scott Nelson recommends

Quote:>       x_length = circle_x - point_x
>       y_length = circle_y - point_y
>       point_distance = square_root(x_length * x_length + y_length * y_length)
>               it_is_outside
>       else
>               it_is_inside

However, if speed is important, you obviously don't want to calculate a

x_length = circle_x - point_x
y_length = circle_y - point_y
point_distance_squared = x_length * x_length + y_length * y_length
it_is_outside
else
it_is_inside

### FAST way to determine whether a point is in a circle???

>>> What is the recommended way of determining whether or not a point is within
>>> the dimensions of a circle?

>>I don't know if this is a serious question or not.  Assuming that it
>>is serious, I'm wondering if you bothered to think about it for a few
>>minutes.

>    [pseudo-code deleted]

>Um. It seems like a few more minutes thought might be in order if the title is
>"FAST way..." :-)
>Square roots are relatively expensive, and in this case quite unnecessary...

As I'm sitting here eating my humble pie, it has been made clear to me
by many people that I missed a very obvious keyword here.  Yes, I am
very aware that an extra multiply is cheaper than a square root on all
computer architectures I've ever seen.  I hope you will all forgive me
for a hasty response.

I also hope that Stuart Booth got the answer he was looking for
somewhere in this discussion.

---

Sun Microsystems

"Sin in haste, repent at leisure"

### FAST way to determine whether a point is in a circle???

When it is unlikely that the point is in the circle (such as a mouse hit
test against a small circle or other non-rectangular object) I find that
it is much quicker to do a pre-check of the point to determine if it is
in the shape's bounding rectangle, and only do the actual circle check
if it first passes this quick test.  This only requires a few
comparisons which is generally much quicker than the multiplies
necessary to check if it is actually in the circle.

\\/
_I_                           (o o)                            _I_

|   |                                                          |   |
|   |  Dave (Casey) Webster            IBM Software Solutions  |   |

|___|                            _                             |___|

I                            (o o)                             I
//\

I have set of triangulated faces (faces have only 3 points)

And a vector.

Is there a fast algorithm that would determine whether
the intersection point of the vector and the plane
created by the face is in side the polygon created by
the 3 points in the face?

I suppose that I have to determine, using the 3 vertices,
the equation of the plane and then determine the intersection
point of the vertex in the plane, then determine whether
the point is in the polygon inside the 3 vertices.

This is in the faq upto the vertex in the plane, but when
deciding whether a point is in the polygon or not is only
presented in 2D form, where I am stuck in the middle of the