>>Does anyone have a method of testing whether a point is in a circle (or
>>circle segment for that matter, actually any "polygon" that has a curve
>>at one or more face/'s) without using the windows REGION Api's.

I responded:
>The Win32 help file has something that might help you: do a search for
>"PtInRegion" and look at the article "Alternative to PtInRegion() for
>Hit-Testing."  It has sample code and some references to other materials.
>This is for a regular polygon, but might help you.

I looked closer at that article in win32.hlp.  Forget it: it is riddled with
bugs, both typing and conceptual.

----------
Subject:  Re: Point in Circle

Sean,

>Does anyone have a method of testing whether a point is in a circle (or
>circle segment for that matter, actually any "polygon" that has a curve
>at one or more face/'s) without using the windows REGION Api's.

Timothy Dixon explained how to test if a point is in a circle.  However, is
that really what you want?  The Windows API doesn't even have a function to
draw a circle (as far as I know), but rather to draw an ellipse.  A circle
is just an ellipse with equal axes.  Here's how to test for inclusion in an
ellipse.  This uses the classic formula for an ellipse,

  sqr(x-x0)/sqr(a) + sqr(y-y0)/sqr(b) = 1

If you use that formula and simplify to avoid floating point calculations,
point (x,y) is in the ellipse that is defined by the bounding rectangle from
point (x1,y1) to point (x2,y2) if and only if

 sqr((2*x-x1-x2)*(y2-y1)) + sqr((2*y-y1-y2)*(x2-x1)) <= sqr((x2-x1)*(y2-y1))

I'm not sure what you mean by a circle segment.  Windows has functions for
Arc, Chord and Pie which give different kinds of ellipse segments.  I have
done some work on testing for inclusion of a point in a general polygon, so
if you let me know just how the "curved segments" are defined for your
figure I'll try to help you.  The Win32 help file has something that might
help you: do a search for "PtInRegion" and look at the article "Alternative
to PtInRegion() for Hit-Testing."  It has sample code and some references to
other materials.  This is for a regular polygon, but might help you.  Note
that the article does not clarify that the given method assumes that you
define the interior of the polygon by the "Alternate" mode (see the article
on SetPolyFillMode in Win32.hlp for an explanation of fill modes).  You need
another method if you want "Winding" mode.  I have developed code that does
the same thing but works for either mode.  Note that the Win32.hlp code is
somewhat buggy and lacking in explanation.

Some additional comments:

1. If you aren't already clear on the difference between "Alternate" and
"Winding" mode, you better learn it.  That greatly affects your definition
of what is inside and what is outside a polygon.

2. If you use a routine to test the inclusion of a point in a polygon and
try to test it using Windows' regions or by looking at a point on a screen,
the test may not agree.  This is for several reasons.  When Windows draws a
polygon it of course uses pixels, and the pixels on the visible boundary of
the polygon do not exactly match the theoretical polygon.  Windows needs to
round pixel positions to a whole number of pixels.  This means that a point
that is near but outside the polygon may actually be inside it when both are
drawn on the screen.  Also, Windows does not always define a region in the
way you expect.  For example, when you define a rectangle in Windows the
lower and right borders that you give the routine are *not* included in the
rectangle that is drawn.

3.  A test for inclusion in a "polygon" with elliptical segments is
possible, but design of an efficient routine would depend on just how you
define the curved segments.  Since a normal line segment is defined by two
points (the endpoints), perhaps you could use three points to define a
circular segment: the endpoints and a point on the segment.  This would work
for a circular arc but isn't enough for an elliptical arc.

Let me know if you need more help on the issue.  I'm not an expert, but I am
an amateur mathematician and have looked at the issue somewhat in the past.
--------
Subject:  Re: Point in Circle

For circles only, you can find the distance between your point (x)
and the center of the circle (c) and see if that distance is <= the
radius of the circle.  Assuming of course that you know (or can
solve for) the center and radius of the circle.

> Heya All
>
> Does anyone have a method of testing whether a point is in a circle (or
> circle segment for that matter, actually any "polygon" that has a curve at
> one or more face/'s) without using the windows REGION Api's.
>
> Sean
>
 

Timothy Dixon   tdixon@fwi.com
  http://www2.fwi.com/~tdixon
 

----------
Subject:  Re: Point in Circle

Sean,

>Does anyone have a method of testing whether a point is in a circle (or
>circle segment for that matter, actually any "polygon" that has a curve
>at one or more face/'s) without using the windows REGION Api's.

Timothy Dixon explained how to test if a point is in a circle.  However, is
that really what you want?  The Windows API doesn't even have a function to
draw a circle (as far as I know), but rather to draw an ellipse.  A circle
is just an ellipse with equal axes.  Here's how to test for inclusion in an
ellipse.  This uses the classic formula for an ellipse,

  sqr(x-x0)/sqr(a) + sqr(y-y0)/sqr(b) = 1
If you use that formula and simplify to avoid floating point calculations,
point (x,y) is in the ellipse that is defined by the bounding rectangle from
point (x1,y1) to point (x2,y2) if and only if

 sqr((2*x-x1-x2)*(y2-y1)) + sqr((2*y-y1-y2)*(x2-x1)) <= sqr((x2-x1)*(y2-y1))

I'm not sure what you mean by a circle segment.  Windows has functions for
Arc, Chord and Pie which give different kinds of ellipse segments.  I have
done some work on testing for inclusion of a point in a general polygon, so
if you let me know just how the "curved segments" are defined for your
figure I'll try to help you.  The Win32 help file has something that might
help you: do a search for "PtInRegion" and look at the article "Alternative
to PtInRegion() for Hit-Testing."  It has sample code and some references to
other materials.  This is for a regular polygon, but might help you.  Note
that the article does not clarify that the given method assumes that you
define the interior of the polygon by the "Alternate" mode (see the article
on SetPolyFillMode in Win32.hlp for an explanation of fill modes).  You need
another method if you want "Winding" mode.  I have developed code that does
the same thing but works for either mode.

Some additional comments:

1. If you aren't already clear on the difference between "Alternate" and
"Winding" mode, you better learn it.  That greatly affects your definition
of what is inside and what is outside a polygon.

2. If you use a routine to test the inclusion of a point in a polygon and
try to test it using Windows' regions or by looking at a point on a screen,
the test may not agree.  This is for several reasons.  When Windows draws a
polygon it of course uses pixels, and the pixels on the visible boundary of
the polygon do not exactly match the theoretical polygon.  Windows needs to
round pixel positions to a whole number of pixels.  This means that a point
that is near but outside the polygon may actually be inside it when both are
drawn on the screen.  Also, Windows does not always define a region in the
way you expect.  For example, when you define a rectangle in Windows the
lower and right borders that you give the routine are *not* included in the
rectangle that is drawn.

3.  A test for inclusion in a "polygon" with elliptical segments is
possible, but design of an efficient routine would depend on just how you
define the curved segments.  Since a normal line segment is defined by two
points (the endpoints), perhaps you could use three points to define a
circular segment: the endpoints and a point on the segment.  This would work
for a circular arc but isn't enough for an elliptical arc.

Let me know if you need more help on the issue.  I'm not an expert, but I am
an amateur mathematician and have looked at the issue somewhat in the past.
----------