Timeline for How to check if a 2D point is in a polygon?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:35 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Aug 22, 2012 at 16:36 | comment | added | Daniel Lichtblau | @ddyer I actually do this stuff for a living... | |
| Aug 16, 2012 at 18:19 | comment | added | ddyer | sure, all those things are potential strategies. My point is that a conceptually elegant algorithm has lots of gritty details to be handled if you want to make it work reliably. | |
| Aug 16, 2012 at 14:39 | comment | added | Daniel Lichtblau | @ddyer In actual practice I would probably choose a random direction to approach from. I might also change the binning to use a random orientation rather than horizontal. I might also add a check for hitting a vertex exactly. Depends on how concerned I was about getting a wrong result in a "small" set of cases. | |
| Aug 15, 2012 at 23:22 | comment | added | ddyer | the trick in real-world use of this algorithm is the boundary cases - what do you do when the imaginary ray to infinity exactly crosses the intersection of two lines, or is exactly coincident with one of the line segments. | |
| Aug 15, 2012 at 18:47 | history | edited | KeithS | CC BY-SA 3.0 |
added 66 characters in body
|
| Aug 15, 2012 at 18:45 | comment | added | Daniel Lichtblau | This is the gist of what I had here. In that case preprocessing, which does take real time, makes the individual queries closer to constant time for "typical" polygons. | |
| Aug 14, 2012 at 16:00 | history | edited | KeithS | CC BY-SA 3.0 |
added 2 characters in body
|
| Aug 14, 2012 at 15:09 | history | edited | KeithS | CC BY-SA 3.0 |
added 456 characters in body
|
| Aug 14, 2012 at 15:04 | history | answered | KeithS | CC BY-SA 3.0 |