Timeline for Point in Polygon algorithm from the viewpoint of a robot
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 24, 2010 at 18:28 | comment | added | Mark Bennet | The 6.28 answer is easy to see for convex polygons as well as for a circle. It is less intuitive that it continues to apply in non-convex cases - indeed in the terms of the question, I think it is wrong (because I think it may be necessary to cross the fence to get the formula to work). Even for a sharply reentrant quadrilateral it seems to me that 6.28 is wrong. If the re-entrant part is less than 1m across it is easy to create an example with an outside path shorter than the boundary (you don't go into the reentrant bit). The inside path is still shorter than the outside path, though. | |
| Dec 24, 2010 at 18:22 | comment | added | Mark Bennet | If the set is convex then from inside you can see the whole boundary, and from outside the boundary lies to one side of you. If you are allowed to see then if you can see the whole boundary you are inside it, and if it lies to one side of you, then you are outside (this doesn't work just for convex domains). | |
| Dec 24, 2010 at 17:59 | comment | added | Kevin Buzzard | @Igor: what if the fence is a circle with radius much smaller than 1 metre? ;-) | |
| Dec 24, 2010 at 17:58 | comment | added | Kevin Buzzard | @ohadsc: hint: try it with a circle! | |
| Dec 24, 2010 at 17:43 | comment | added | ohadsc |
And it seems W_i is the quermassintegrale (appearing in Kubota's formula)... Well I don't really have to understand it all they way but I'm just wondering, how did you come up with 6.28 if you didn't have the formula in front of you ?
|
|
| Dec 24, 2010 at 17:38 | comment | added | ohadsc |
Well i think n is the same one from E_n which is the convex set, does that help ?
|
|
| Dec 24, 2010 at 17:36 | comment | added | Igor Rivin | I don't have it in front of me, but I assume that n is the normal vector... | |
| Dec 24, 2010 at 17:36 | comment | added | ohadsc |
Just a quick question - What are n and W_i in the formula ?
|
|
| Dec 24, 2010 at 17:29 | vote | accept | ohadsc | ||
| Dec 24, 2010 at 17:28 | comment | added | Igor Rivin | A lot of the book is on google books (go to books.google.com, search for Santalo, you will find it, then search for Steiner. The original version of the result is for convex sets, but this is easy to extend by additivity. The original proof of the "Chern-Gauss-Bonnet" formula by Allendorfer and Weil used exactly this method -- you might want to look at that paper (published in the 1940s). | |
| Dec 24, 2010 at 17:20 | comment | added | ohadsc | Thanks ! Any chance for a link I can read without getting the book ? | |
| Dec 24, 2010 at 17:17 | history | answered | Igor Rivin | CC BY-SA 2.5 |