Computer related puzzles and questions

[Sip]

Since the math thing was so popular in the "other" forum, I thought maybe we can try the same thing but with computers! It looks like we have some people with software and programming knowledge so this should be fun

 

I'll start but feel free to post questions!

 

Point in Polygon

Suppose I give you a 2D polygon with n vertices. Let's say I give you all vertex coordinates (xi, yi) in counter-clockwise order where i is from 1 to n. Or if it makes it easier, you can assume that I give you the edges of the polygon specified by their end points. The question I am asking is that given a point (x,y), how can you determine if it is inside or outside the polygon?

 

So, tell me how you would write an algorithm to check to see if a point is inside the polygon or not. Note that the polygon can have very strange shapes (could be concave or convex). The only assumption you can make is that the edges of the polygon do not intersect each other ... so it's a "nice" polygon

[Guest Fadi]

Here is a part fo problem, there may be other answers shorter then this one...

 

I broke this polygone ages and make each others functions, and from the graphic of it we determine for each fonctions if it should be > or <, then we test this given x,y to every function and if we found at least one of these fonctions that dosent respect the [< or >], then we conclude that it is outside of this figure...

 

I know it is a long technic, and you will come with a short one

[Sip]

hmmmm I am not sure I am understanding your method. So you are saying that we can treat each line segment (edge) i as a "function" Fi. Then if the point (x,y) > Fi or < Fi then the point is inside the polygon.

 

Imagine a simple square. The point will be < 2 of the lines and > the other 2 lines according to that definition (if I am understanding correctly). However, a point outside the square, can also have such relationships ...

 

Can you explain more? Maybe the method works but I am not understanding it

[Guest Fadi]

Well, I have found a more general way.

 

Lets say that each ages that are on the right side of the polygone should include the points left side [<], on the other way each ages that are at the left side should also include every points on the right side [>], now the only 2 left that may be parallel with the x axes(or 1, or maybe there could be no ages parallel with x), the one at top of the polygone should include every points at the bottom, the bottom [<] side every points at the top, [>]

 

Now after taking all these fonctions and remark that the direction <,> is respected then we could conclude the point is inside, if there one and more that dosent respect these direction then we conclude it is outside...

 

I know my English suck, but what I propose make sens ;} Maybe if I draw it, it will be easier, or maybe explaining it in French

 

[ March 12, 2002, 02:40 PM: Message edited by: Domino ]

[Guest Fadi]

You know what ? I just have re-read myself, and I don't understand myself

 

Maybe I should draw it

[Guest Fadi]

BTW, could someone tell me why parentheses are blocked ? Is it because you guyès are afraid that some sort of programmations could be used to spamm that board ?

[Guest Fadi]

Sip so do you understand what I mean or should I draw it ? GOD DAMM ANSWER

[Sip]

You mean like this? () <> {} [] ... they seem to work ? I think < > and [ ] have special meanings at times.

 

Now to your method. I think I know what you are trying to say but I don't think it is too easy to implement (to write a program for it). There will be many special cases I think.

 

Something like:

 

I think the point x will be a problem for you. Just start deforming that figure (move end-points) and you will see that soon things like "left", "right", "up", "down" are not too easy to determine.

 

There is a clean and elegant solution as you suspected from the beginning

[Sip]

I was working on it ... it requires quite a bit of thinking to see if it will work or not.

[Guest Fadi]

O.K you got me on that one, then you have to analyse them one by one)the fonctions, and forget about top, left right...)... but since I hate programmations(the word hate is not hard enough), I have no idea of how to implament it

 

[ March 12, 2002, 05:51 PM: Message edited by: Domino ]

[Sip]

How can you hate programming? It's such a beautiful science! I actually mean algorithms ... not just simple programming.

 

So here's the answer:

 

Solution to point in Polygon

The way to do it is to draw an imaginary line from the point (x,y) to (+infinity,y). Now that you have this line, you just check to see with how many polygon edges it intersects with. Note, checking intersection of 2 lines is very easy given end points of the lines. If you have odd number of intersections, you are inside the polygon. If you have even number of intersections you are outside.

 

There is a special case where a polygon line is horizontal and lies on our imaginary line. That case is easy to handle in software so I won't explain details.

 

Does it make sense?

 

I know of about a million tricks like this and I find them very cool! One of the main reasons I stuck with computer science...

 

[ March 12, 2002, 06:12 PM: Message edited by: Sip ]

[Guest Fadi]

AYCH... O.K

 

One word: Cooooooooolllllllllll...

[Guest Fadi]

But still dosent change the fact that I HATE programmation.

[Sip]

I guess that means it's time for a new problem?

 

I don't have too much time right now since I actually have to design a final exam question for the class I am teaching in the next hour so here's a quicky:

 

Bounding Polygon Problem

Suppose I give you a bunch of points in the plane using their (x,y) coordinates. Tell me a way to find the points which when connected together, will form the polygon that includes ALL the points.

 

So, tell me a way to find the vertices of the polygon that surrounds all points.

[Guest Fadi]

From what I understand from your question, it seem to be not so difficult...but long. I may be wrong, but in paper I works

 

First of all you take the farer points from the center, then link them with eachothers exept for the last two that you left open, then each one of these two points you link them alone by those inside, you chose to link them by using the distance formula, the distance between the point should be the smalest between this point to the exterior fonction(the ones that you already linked themselves a fontion(each series of two points)), you do this from the two sides, and at the end you again the last two points, then the same thing you enter and use the distance formula untill you close and you will end up of covering all the points.

 

I bet due to my lack of English capacity, I have to explain it more, after you answer: "I havent understoud a s...t of what you told"

 

[ March 14, 2002, 03:11 PM: Message edited by: Domino ]

[Sip]

Ok Domino, I havent understoud a s...t of what you told

 

If you have seen the kinds of questions I ask, you should know that there is usually some clear, neat, and easy to describe way ... otherwise I wouldn't ask them here

 

If I understand th beginning of your algorithm, you connect points farthest from center ... how do you define this far from center? How many such points? There could potentially be many many points with random places.

[Harut]

will somebody say something already???!!!

[Guest Fadi]

http://network54.com/Realm/fgfg/333.JPG

 

Is this not a polygon ?

 

This is what I was telling you, you take all the points at the outside and link them exept for two of those chosen arbitrary, in order to find all the outside points, you take the minimum of possible points that will cover all the other points, and you do this untill you end it... from this way, there is many different possible polygons...

 

Am I mistaken ?

[Guest Fadi]

BTW, there is some mistakes on the above pic, because you want coordinates, so this was my point, you use the distant formula and chose the less possible points and the nearests with the outsides ligns by cutting them by fonctions...

[Guest Fadi]

I just read your profil... Get Out of my way you computer Freak

 

AAAAAAAaaaaaaaaaaaaaaaaaa... Another computer nerdo on my way.......... AAAAAAAAaaaaaaaaaaaaaaaaa.....

 

BTW, where is your answer ?

[Guest Fadi]

PhhhhSip... where is the answer

 

You post a puzzle, at least post after the answer that goes with it

[Sip]

Well, I am glad you are trying at least! I hate giving away answers since then the problem is not fun anymore ... also, have been very busy these past few days ...

 

Solution to Bounding Polygon Problem

This one is actually kind of fun! So you start with the point with the largest 'y' coordinate (highest point)... call this p_highest. Then, you calculate the angles formed by the horizontal line, and the line connecting this point to EVERY other point. Call the angle to point i, theta_i. For example:

 

Then the solution becomes elegant! At each step, you simply connect your current point to the point with the smallest theta. And repeat the process.

 

So the way it works is that you basically "wrap" a line around the points by calculating this angle tetha to each point and picking the smallest one as the next point (you start by the higheset point). This algorithm is also called the Gift Wrapping algorithm in some text books.

[Sip]

Oh, and if you want to see this thing in action, click on THIS LINK to my website. You can start clicking around to add points. Then choose "convex hull" to see this bounding polygon. You may want to deselect Voronoi Diagram first. The algorithm used in that applet is not the same as above, but the outcome is the same.

[MosJan]

Cool staf but what can i use this for ???

[Sip]

The most common use I can think of is computer graphics. Ever wonder how those FAST 3D graphics cards work? They have to be able to do 3d calculations and polygon math very very fast to be able to give you 60 frames per second in a game that has thousands of polygons in one scene! Now I know you play computer games Movses jan But if you are not a programmer, you probably will never use this stuff directly.

 

So one way to "shade" a polygon is to do scanline algorithm. You start from the left and move to the right pixel by pixel. As soon as you see an edge, you turn on your color and start filling in. As soon as you see the next edge, you turn off your color. Once a horizontal line (scan line) is complete, you go to the next line and repeat. This is the simplest way to FILL a complex polygon very quickly without much complicated math.