Mathematics desk | ||
---|---|---|
< January 24 | << Dec | January | Feb >> | January 26 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I dont like math it is not too helpful but on the same token I want to work for NASA! —Preceding unsigned comment added by Kop the man ( talk • contribs) 03:01, 25 January 2008 (UTC) Can some one please at least help me like math? —Preceding unsigned comment added by Kop the man ( talk • contribs) 03:07, 25 January 2008 (UTC)
I am trying to understand Stochastic matrix.
The article has an example of the cat and mouse:
1. You have a timer and a row of five adjacent boxes.
2. The cat is in the first box.
3. The mouse is in the fifth box.
4. The cat and the mouse both jump to a random adjacent box when the timer advances.
5. If the cat is in the second box and the mouse in the fourth one, the probability is one fourth that the cat will be in the first box and the mouse in the fifth after the timer advances.
So in the above example the article generates some jargon:
The before state with the cat in the second box and the mouse in the fourth box is State 3. The after state with the cat in the first box and the mouse in the fifth box is State 2. The probability of transitioning, given that the system is in State 3, to State 2, is the entry found in row 3, column 2, of P, which is 1/4. From State 3 the system can go into each of States 1, 2, 4 and 5, and these four possible transitions all have equal probability. From State 1 the system can only transition to States 3 and 5, because the cat must move to the second box; depending on whether the mouse goes right or left it survives (State 3) or is eaten (State 5). -- Lambiam 09:16, 25 January 2008 (UTC)
Can you elaborate, please? I don't understand where State 1 is in your explanation? -- Obsolete.fax ( talk) 13:07, 26 January 2008 (UTC)
I am currently implementing a GIS system and in this process I have encountered a few problems from computational geometry that may be interesting. Here is the first one.
I have a simple polygon with a few million vertices and some tenthousand points. I want to know for each point whether it is inside or outside the polygon. This is the Point in polygon problem.
So far, I am doing a bounding box intersection, which cuts away most of the points. After that I do a full test using raycasting on the remaining points. Naturally, each test takes quite some time for such a large polygon. I am looking for some additional method to instantly classify most of the points, so that only a tiny fraction of the original points have to go through the full raycasting test.
The tricky algorithms that I have found so far (grids and similar) seem to require too much preprocessing (remember, millions of vertices but only thousands of points). I was thinking about computing a maximum inscribing box, but some of the polygons are oddly shaped and would yield useless boxes.
What I really want is to find a way to compute a polygon that reasonably resembles the form of the original polygon with only a few dozen points, but remains completely inside the original polygon. Any ideas? Thorbadil ( talk) 20:28, 25 January 2008 (UTC)
Why do you want to do this? i.e. what's the bigger picture? And if the points are on a regular grid (say 100x100 = 10,000 points), isn't it actually rather easy (well, as easy as solving the point in polygon problem 100 times) with some record keeping along the way? Pdbailey ( talk) 21:55, 25 January 2008 (UTC)
I solved the Point in polygon problem some years ago in connection with determining which ambulance station was responsible for a specific adress. The region of each ambulance station was a polygon specified by the coordinates of its vertices. I used the winding number algorithm. Your problem is that the polygon is too complicated for this solution to be fast. However, describe your complicated polygon as the common limit of a decreasing finite sequence of simpler outer polygons, and an increasing finite sequence of simpler inner polygons. Most points is outside one of the outer polygons, or inside one of the inner polygons, and then you are done. Only when the point is very close to the limit polygon do you have to compute the complicated case. Am I clear? Bo Jacoby ( talk) 14:00, 27 January 2008 (UTC).
Dear Wikipedians:
What is the inverse function of ?
In other words, is it possible to find an explicit expression for ?
If not, why not?
Thanks.
76.68.9.132 ( talk) 23:04, 25 January 2008 (UTC)
Mathematics desk | ||
---|---|---|
< January 24 | << Dec | January | Feb >> | January 26 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I dont like math it is not too helpful but on the same token I want to work for NASA! —Preceding unsigned comment added by Kop the man ( talk • contribs) 03:01, 25 January 2008 (UTC) Can some one please at least help me like math? —Preceding unsigned comment added by Kop the man ( talk • contribs) 03:07, 25 January 2008 (UTC)
I am trying to understand Stochastic matrix.
The article has an example of the cat and mouse:
1. You have a timer and a row of five adjacent boxes.
2. The cat is in the first box.
3. The mouse is in the fifth box.
4. The cat and the mouse both jump to a random adjacent box when the timer advances.
5. If the cat is in the second box and the mouse in the fourth one, the probability is one fourth that the cat will be in the first box and the mouse in the fifth after the timer advances.
So in the above example the article generates some jargon:
The before state with the cat in the second box and the mouse in the fourth box is State 3. The after state with the cat in the first box and the mouse in the fifth box is State 2. The probability of transitioning, given that the system is in State 3, to State 2, is the entry found in row 3, column 2, of P, which is 1/4. From State 3 the system can go into each of States 1, 2, 4 and 5, and these four possible transitions all have equal probability. From State 1 the system can only transition to States 3 and 5, because the cat must move to the second box; depending on whether the mouse goes right or left it survives (State 3) or is eaten (State 5). -- Lambiam 09:16, 25 January 2008 (UTC)
Can you elaborate, please? I don't understand where State 1 is in your explanation? -- Obsolete.fax ( talk) 13:07, 26 January 2008 (UTC)
I am currently implementing a GIS system and in this process I have encountered a few problems from computational geometry that may be interesting. Here is the first one.
I have a simple polygon with a few million vertices and some tenthousand points. I want to know for each point whether it is inside or outside the polygon. This is the Point in polygon problem.
So far, I am doing a bounding box intersection, which cuts away most of the points. After that I do a full test using raycasting on the remaining points. Naturally, each test takes quite some time for such a large polygon. I am looking for some additional method to instantly classify most of the points, so that only a tiny fraction of the original points have to go through the full raycasting test.
The tricky algorithms that I have found so far (grids and similar) seem to require too much preprocessing (remember, millions of vertices but only thousands of points). I was thinking about computing a maximum inscribing box, but some of the polygons are oddly shaped and would yield useless boxes.
What I really want is to find a way to compute a polygon that reasonably resembles the form of the original polygon with only a few dozen points, but remains completely inside the original polygon. Any ideas? Thorbadil ( talk) 20:28, 25 January 2008 (UTC)
Why do you want to do this? i.e. what's the bigger picture? And if the points are on a regular grid (say 100x100 = 10,000 points), isn't it actually rather easy (well, as easy as solving the point in polygon problem 100 times) with some record keeping along the way? Pdbailey ( talk) 21:55, 25 January 2008 (UTC)
I solved the Point in polygon problem some years ago in connection with determining which ambulance station was responsible for a specific adress. The region of each ambulance station was a polygon specified by the coordinates of its vertices. I used the winding number algorithm. Your problem is that the polygon is too complicated for this solution to be fast. However, describe your complicated polygon as the common limit of a decreasing finite sequence of simpler outer polygons, and an increasing finite sequence of simpler inner polygons. Most points is outside one of the outer polygons, or inside one of the inner polygons, and then you are done. Only when the point is very close to the limit polygon do you have to compute the complicated case. Am I clear? Bo Jacoby ( talk) 14:00, 27 January 2008 (UTC).
Dear Wikipedians:
What is the inverse function of ?
In other words, is it possible to find an explicit expression for ?
If not, why not?
Thanks.
76.68.9.132 ( talk) 23:04, 25 January 2008 (UTC)