




An approach to a geometric problem
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 freehand 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
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 nonzero value otherwise. This partitions the points in your rectangular region into those which have zero winding numbers and nonzero 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" <k @mit.edu> wrote in message news:1180968605.327755.241450@q75g2000hsh.googlegroups.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 freehand 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
On Jun 4, 7:50 am, Tony <k@mit.edu> wrote:
> 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 freehand 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





