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

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

Post by Scott R. Nels » Sat, 08 Oct 1994 02:20:31




> 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):
        circle_x, circle_y, circle_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)
        if point_distance > radius
                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???

Post by Stephen Joel Adels » Sat, 08 Oct 1994 02:45:32




|>
|> > 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):
|>   circle_x, circle_y, circle_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)
|>   if point_distance > radius
|>           it_is_outside
|>   else
|>           it_is_inside

Let Radius = circle_radius^2, and the square_root is unneccesary.

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

 
 
 

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

Post by Stuart Boo » Fri, 07 Oct 1994 22:18:54


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???

Post by Damian Conw » Sat, 08 Oct 1994 09:20:34




>> 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...

        PointInCircle(point, centre, radius)
        {
                delta.x  =  point.x - centre.y
                delta.y  =  point.y - centre.y

                return ( radius*radius <= delta.x*delta.x + delta.y*delta.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...

        PointInCircle(point, centre, radius)
        {
                delta.x  =  point.x - centre.y
                delta.y  =  point.y - centre.y

                if (delta.x > radius or delta.x < -radius or
                    delta.y > radius or delta.y < -radius)
                then return false

                return ( radius*radius <= delta.x*delta.x + delta.y*delta.y )
        }

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???

Post by Kazimir Kylhe » Sat, 08 Oct 1994 10:06:12





>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)
>    if point_distance > radius
>            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

        if point_distance > radius * radius

        [etc]

Now go back to debugging that Solaris crap! :)

 
 
 

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

Post by Feldman / Mark Jeffrey (I » Sat, 08 Oct 1994 15:55:42





>> 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):
>    circle_x, circle_y, circle_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)
>    if point_distance > radius
>            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???

Post by Mark Warburt » Sat, 08 Oct 1994 02:25:55


: 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.)

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


Ottawa, ON, CANADA

 
 
 

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

Post by Jonathan R Shewch » Sat, 08 Oct 1994 06:30:44


Stuart Booth asks

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)
>       if point_distance > radius
>               it_is_outside
>       else
>               it_is_inside

However, if speed is important, you obviously don't want to calculate a
square root.  Instead:

       x_length = circle_x - point_x
       y_length = circle_y - point_y
       point_distance_squared = x_length * x_length + y_length * y_length
       if point_distance_squared > (radius * radius)
               it_is_outside
       else
               it_is_inside

 
 
 

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

Post by Scott R. Nels » Sat, 08 Oct 1994 23:33:15





>>> 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???

Post by Casey Webst » Mon, 10 Oct 1994 03:13:17


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
                                //\

 
 
 

1. Determining whether a point is in a polygon

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
conversion.  and all these points made my head quite
fuzzy.

I wonder whether there is a good way to  determine whether
a point is in a polygon or not.

Thank you.

2. Texture coords outside [0, 1]

3. Determining whether two line segments intersect

4. OpenGL performance question

5. How to determine whether an angle lies between two others

6. Savage MX graphics has issues

7. determine whether triangles cover a cube?

8. Tahoma Font on Mac?

9. fast method for finding points of intersection between a line and a circle

10. How to determine whether a GIF is animated?

11. Whether a point is inside a regular polygon

12. Checking whether a point is above or below a plane

13. finding whether a point is inside a triangle