From the sound of it, this problem can be solved by use of the "winding"

number.

The winding number is an integer value which indicates if a point is within

a closed curve or not.

A winding number of 0 means the point is outside the curve, a non-zero value

otherwise. This partitions

the points in your rectangular region into those which have zero winding

numbers and non-zero winding

numbers, those respectively being those outide the closed curve and those

outside.

You can compute the winding number easily for a the points in your problem

by dropping a vertical

line (downward) from each point, then counting the number of intersections

made by the (eclipse) curve

you have drawn, adding plus 1 for intersections from right to left, and

minus 1 for left to right.

dave

"Tony" <ki**@mit.eduwrote in message

news:11**********************@q75g2000hsh.googlegr oups.com...

Hello,

As a part of a personal project, I am attempting to write a computer

program that can solve the following problem:

Suppose I start with a finite piece of rectangle. Within this

rectangle, I draw free-hand some sort of a closed geometric figure

which I suppose would be represented internally by a sequence of

points. For concreteness, suppose I have drawn an ellipse within my

rectangle.

Then the closed loop that I have drawn splits geometrically the

rectangle into two distinct regions. What would be an approach to

instruct the computer that there are distinct regions?

The above question is somewhat vague, so let me describe the

application explicitly. I begin with a rectangular array of nodes. I

want to be able to draw an arbitrary closed loop over these points,

such that the nodes not contained in the loop will be deleted. While

it should be possible to achieve the above without addressing the more

difficult question of geometric region determination, I was interested

in the latter because I would like the flexibility of dealing with

complex types of regions, i.e. not only curvy boundaries but also

regions that may not be simply connected (for example, I would draw

two concentric circles and I want to be able to indicate that the

annular region is the region that I want to operate in).

As a side note, from a previous project I have a mechanism that, for a

given list of nodes in the coordinate plane, can quickly retrieve the

node near some input coordinate (x,y). Preferably I would like to

implement a solution involving this mechanism so that I don't have to

rewrite a large amount of code.

I am currently in the brainstorming stage and am trying to generate

ideas to tackle this problem. Any suggestions, or references to

solving geometric problems on the computer would be very appreciated!

(It's the first time I have attempted this type of problem.)

Thanks in advance,

-Tony Kim