An approach to a geometric problem

[Tony]

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

 

[Dave Townsend]

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

 

[Naresh Rautela]

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

I am not sure if I understand your requirements completely.

How about doing something like this
*Represent each figure by an id
*Have a class that
stores the coordinates of the nodes
stores the ids of the figures that it intersects with
stores the intersecting coordinates
*With this whenever you are dealing with an object you know the
figures that it is intersecting with and the points of intersection.
Then you can deal with it accordingly