Polygon Detection for Bay Selection and Vertical/Horizontal Line Drawing

[svishal03]

1. I have a problem like this:

I. As you see (in the attachment) each of the closed polygons (as in the attachment) is called a BAY

II. The logic I need is:
The user of my program will select a bay (with a mouse).
And after selection he would want the program to draw some vertical (or horizontal) lines in a bay at some spacing as shown in the attached figure:
My question/problem is:
a) How the program will detect a bay?
b) How to draw theese vertical/horizontal lines as in the attachment in the bay?

Please help

 

[chiro]

1. I have a problem like this:

I. As you see (in the attachment) each of the closed polygons (as in the attachment) is called a BAY

II. The logic I need is:
The user of my program will select a bay (with a mouse).
And after selection he would want the program to draw some vertical (or horizontal) lines in a bay at some spacing as shown in the attached figure:
My question/problem is:
a) How the program will detect a bay?
b) How to draw theese vertical/horizontal lines as in the attachment in the bay?

Please help

Hey there you probably should have posted this in the computer forum but anyway.

Detecting a bay is not too hard.

For doing this you need a spatial structure for each "bay" which is basically a set of inequalities. The union of these inequalities classify the space.

To check which bay you're in you simply test all of the inequalities and if you satisfy the set of all inequalities for a particular bay, then that's the bay that the user is picking.

You could speed this up by having some other higher spatial data structure like a quad-tree for example but I won't go into that.

So just to recap, create a structure that contains every inequality for one bay. Then for each structure put it in some kind of array or linked list. When you want to find the bay, then do what I said above: check every inequality and if all inequalities in one particular "bay" are satisfied then that's your bay that the user has picked.

Ok now for the second one.

The best way I can think of off the top of my head is to do the following:

1) Pick two edges that are adjacent.
2) Take the cross product of those two sides
3) Ortho-normalize the system
4) Use you're orthonormalized vectors in the xy plane for direction.

Using those new basis vectors, choose one and move orthogonally in one direction and specify a line that has moved orthogonally in so many units.

For each line solve for the inequality constraints of your bay so that they remain inside the bay.

When your new line is out of bounds of the bays spatial region, create no more lines.

Good luck!

 

[svishal03]

Thanks a lot for the reply.

I have described my problem more clearly in the attached file (with diagrams) in case if I was not clear.

You said:

Detecting a bay is not too hard.

For doing this you need a spatial structure for each "bay" which is basically a set of inequalities. The union of these inequalities classify the space.


To make it clear, the user has not defined any bay explicitely.As in the figure, he has drawn some lines horizontal and vertical and each closed polygon is a bay.

My questions are (corresponding to what you stated- the one in italic above)

A) Since, the bay is not explicitely user defined, how to define set of inequalities (in the program) for each bay?
B) What are these inequalities?

Thanks again and awaiting your reply!

 

[chiro]

Thanks a lot for the reply.

I have described my problem more clearly in the attached file (with diagrams) in case if I was not clear.

You said:

Detecting a bay is not too hard.

For doing this you need a spatial structure for each "bay" which is basically a set of inequalities. The union of these inequalities classify the space.


To make it clear, the user has not defined any bay explicitely.As in the figure, he has drawn some lines horizontal and vertical and each closed polygon is a bay.

My questions are (corresponding to what you stated- the one in italic above)

A) Since, the bay is not explicitely user defined, how to define set of inequalities (in the program) for each bay?
B) What are these inequalities?

Thanks again and awaiting your reply!

Your inequalities will be based on normal cartesian geometry.

I'll give an example. Say you had a "bay" that was triangular (I know they are not but if you understand the example you can extend it to any 2D shape).

Lets say its bounded by the x and y axis, and its in the top-right quadrant. Let's say it has vertices at (0,0) (1,0) and (0,1). The lines you will have are

x >= 0, y >= 0 and (x + y <= 1). If you graph these equations either by hand or with a computer math package you will see that the shaded region is a triangle.

Thats basically the idea. All your shapes will simply be linear inequalities and if you know how to calculate the formula for a line (ie ay + bx = c) then you can simply check to see if a bay has all inequalities. So again using the triangle example let's say the mouse pointer is at 1/4,1/4 on the screen. To test if the pointer is in the bay we run through three tests:

good = 1
if (x < 0) then good = 0
if (y < 0) then good = 0
if (1/4 + 1/4 > 1) then good = 0

You can see that the variable good will equal 1 since it passes every test. Basically you have to write an algorithm that has a set of tests for each bay and then check every rule.

If the bays are generated at certain points (i'm assuming they are convex) where the points are the vertices of the bay, you can simply use the points to calculate the required lines and thus the inequalities.

If you're looking for a general algorithm given a set of points, the best I can think of is to use a 2D convex hull, and then use the definition of the hull to define the inequalities. The reason why the hull is so useful is that by its definition you will always be able to figure out the right inequality that bounds the area.

For example say with the triangle if we had (x + y) >= 1 then we'd be screwed.

If you have questions about anything I've said feel free to ask away

 

[svishal03]

Thanks again for your reply!

Actually, I said, we do not have an explicit definition of a bay in the program (input).

All, I have is:

1) A series of lines for which I have the equations.That is, I have the lines and their corresponding equations.

I do not know which lines bound a bay?

So, the question is how to define a bay? When I say define a bay, I mean how do I get:

BAY 1: Lines it is bounded by?
BAY 2: Lines it is bounded by?

Once I have BAY 1, BAY 2,------each with the lines it is bounded by, I can use the logic you suggest to detect a bay.

Am I missing any of your point?

Can you make it clear for me?

Please help

 

[chiro]

Thanks again for your reply!

Actually, I said, we do not have an explicit definition of a bay in the program (input).

All, I have is:

1) A series of lines for which I have the equations.That is, I have the lines and their corresponding equations.

I do not know which lines bound a bay?

So, the question is how to define a bay? When I say define a bay, I mean how do I get:

BAY 1: Lines it is bounded by?
BAY 2: Lines it is bounded by?

Once I have BAY 1, BAY 2,------each with the lines it is bounded by, I can use the logic you suggest to detect a bay.

Am I missing any of your point?

Can you make it clear for me?

Please help

Yes once you have the inequalities you basically use them to test the bay.

I don't get it though, where are you getting the bay from? It has to come from somewhere. Are you generating it based off other data or is the user generating it?

But assuming you have the lines that bound the bay for BAY1, BAY2, etc then yes just use the logic I presented in the previous post to find which bay is selected.

 

[svishal03]

Actually, the user of the program is just drawing those lines indicated in the figure.He is not explicitely specifying any polygon as a 'bay'.

It is expected that once the user clicks in any point inside the polygon, the bay should be recognised and the lines between the bay drawn.

How to recognise the bay? That is, given a series of lines how to assign bays?

Once bays are assigned , we can then use your logic.

Can you hep again?

 

[chiro]

Actually, the user of the program is just drawing those lines indicated in the figure.He is not explicitely specifying any polygon as a 'bay'.

It is expected that once the user clicks in any point inside the polygon, the bay should be recognised and the lines between the bay drawn.

How to recognise the bay? That is, given a series of lines how to assign bays?

Once bays are assigned , we can then use your logic.

Can you hep again?

Based on what you have said here is what I recommend for you do to:

1) Let the user click on the screen to assign the point to a bay.
2) When the user has selected more than 2 points that are not collinear (ie all lie on the same line) do the following:
2b) Calculate the 2D form of the convex hull.
2c) Draw the hull on the screen
3) If user is happy with the shape (ie the bay) and user presses another button then save the hull information and go back to the user doing whatever

Now for user selecting bay:

If user presses button for selecting bay:

1) For each bay do a dot product test with the convex hull of each bay
2) If convex hull detects point inside bay then select bay (highlight) and do whatever

Now I know I said to use equations of lines and basically you will be doing that but first let me explain what the convex hull is.

A convex hull is an algorithm that creates a convex polytype in whatever dimension you are working in.

In 2 dimensions the algorithm is not too bad and given that you understand the algorithm you can implement in many dimensions.

If you know the difference between concave and convex polygons, you should have an idea of what it does: basically you give it a set of points and the hull outputs the biggest convex polygon with those points.

Since the user supplies points for the bay, every time they update the point list you can recalculate the hull on the fly and update the screen with the new bay.

Now the convex hull actually generates the line equations because the hull lists all the points in a counterclockwise order.

Basically you use this order and calculate a normal vector that points "outwards" and use this normal vector and a point to calculate whether the user is selecting a point in the bay.

The way it works is that you'll have a normal (a,b) and a distance c where (ax + by - c) < 0 if the point is on the negative half-space: if every "line-segment" gives you a negative result in calculating (ax + by - c), then the point is inside the hull and therefore inside the bay.

Its getting late so I'll help you later, but I would research the convex hull algorithm in two dimensions. If you have any questions I'll do my best to answer them.

 

[svishal03]

Hi,

Thanks for the reply.I am researching the Convcex hull algorithm as you advised.

Just to re-state:

1) The user will just draw those lines in the figure.These may be horizontal,vertical or inclined lines.

As you see in the figure, the lines form bays.

Now the user is not explicitely defining a bay.

The program must gather the information from the lines and store bays.

NExt:

2) If the user clciks on a BAY, we should detect a bay and draw vertical lines as stated by the user.

For 1, you have advised convex hull

2 is simple as you explained in the first few posts.

 

[chiro]

Hi,

Thanks for the reply.I am researching the Convcex hull algorithm as you advised.

Just to re-state:

1) The user will just draw those lines in the figure.These may be horizontal,vertical or inclined lines.

As you see in the figure, the lines form bays.

Now the user is not explicitely defining a bay.

The program must gather the information from the lines and store bays.

NExt:

2) If the user clciks on a BAY, we should detect a bay and draw vertical lines as stated by the user.

For 1, you have advised convex hull

2 is simple as you explained in the first few posts.

The convex hull is a general algorithm: it will figure out the polygon definition for any side and in the 2D case, that means any line with any direction at any position.

With regards to bay selection, the dot product for euclidean space is the general way (like how the convex hull is the general way) to determine what side a point is on with respect to a linear object (in 2D case this is a line, 3D is a plane and so on).

Basically you will use the dot product to find out whether a point is on the "inside" of a line and if its on the "inside" of every line in the hull, it is inside the bay.

With this said, if you understand the convex hull and the dot product you should be ok in writing the code.

Any other questions feel free and I'll do my best to answer them

 

[svishal03]

Actually convex hull is getting a polygon from a set of points.But I want to construct/identify bays from a set of lines as explained above and in attachments.

I don't think convext hull is my solution.

Even if I don't have lines and use convex hull to get polygons from the points (through which lines are drawn), I will get a polygon from the whole set of points.

What if I want to construct/detect only rectangular bays? Is it posisble?

Vishal

 

[chiro]

Actually convex hull is getting a polygon from a set of points.But I want to construct/identify bays from a set of lines as explained above and in attachments.

I don't think convext hull is my solution.

Even if I don't have lines and use convex hull to get polygons from the points (through which lines are drawn), I will get a polygon from the whole set of points.

What if I want to construct/detect only rectangular bays? Is it posisble?

Vishal

The reason that I use convex hull is because the detection mechanism for selecting a bay is the same regardless of the orientation and shape of the bay.

If you want to use lines then use the lines and feed the end points of the lines into the hull algorithm.

Like I said, the hull algorithm was suggested mainly for providing a detection mechanism for the user clicking a bay.