473,320 Members | 1,820 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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

Jun 4 '07 #1
2 1513
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

Jun 4 '07 #2
On Jun 4, 7:50 am, Tony <k...@mit.eduwrote:
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
Jun 4 '07 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Rom | last post by:
I need to create a utility that presents the user with a "canvas" and allows them to add geometric shapes, including lines and circles. These must be drag-able (that is, once they're on the canvas,...
7
by: Chinook | last post by:
OO approach to decision sequence? --------------------------------- In a recent thread (Cause for using objects?), Chris Smith replied with (in part): > If your table of photo data has...
0
by: Jeff D. Hamann | last post by:
Sorry for the seemingly novice posting, but I could find a solution for this on the web so far... I've been developing a database using postgresql (and loving it) and have started running into...
16
by: Robert Zurer | last post by:
Can anyone suggest the best book or part of a book on this subject. I'm looking for an in-depth treatment with examples in C# TIA Robert Zurer robert@zurer.com
1
by: Henriksen, Jonas F | last post by:
Hi, I cant seem to figure out how to use the geometric shapes in postgres: my query goes like this: select lat, lon from toperation where point'(lat,lon)' @ polygon'((50,...
0
by: Jeff D. Hamann | last post by:
Sorry for the seemingly novice posting, but I could find a solution for this on the web so far... I've been developing a database using postgresql (and loving it) and have started running into...
4
by: Kevin | last post by:
I tried writing a program to get the first few terms of a geometric progression.After the execution, I got -858993460 before the start of the series.i have used int for all variables. what...
9
by: MyInfoStation | last post by:
Hi all, I am a newbie to Python and would like to genereate some numbers according to geometric distribution. However, the Python Random package seems do not have implemented functionality. I am...
1
by: Rui Carvalho | last post by:
Dear All, Can someone tell me how I (in Netbeans) can select one rectangle (and move it) and then select other and move that one. To underestand the problem imagine a form where you have two...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.