Timeline for How to check if a 2D point is in a polygon?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22, 2014 at 15:51 | comment | added | Daniel Lichtblau | Okay, thanks for the explanation. I will add that it is also critical, in polynomial irreducibility testing, to know if an exponent vector is or is not a vertex in the convex hull corresponding to a certain a Newton polytope. I can say that numerical convex hull methods have made such determination much more difficult than I would like. So there is at least one math algorithm where this does matter. | |
| Jan 22, 2014 at 8:45 | comment | added | Janus | A partitioning of a set S is a collection of disjoint subsets of S whose union is S mathworld.wolfram.com/SetPartition.html. The practical problem with partitioning (part of) the plane into polygons is to specify what happens to points on the edges and vertices: it's a lot of tedious details which are usually unimportant from a mathematical point of view (since the combined edges have 0 area), but still needs to be done right for some numerical algorithms to work. | |
| Jan 21, 2014 at 15:29 | comment | added | Daniel Lichtblau | I had a look at "Insignificance Galore" where it mentions the partitioning guarantee. But I still do not understand what it means. Is it for the case of multiple disconnected polygons? Self-intersecting? Or does it also have meaning in the case of one non-self-intersecting polygon. | |
| Jan 21, 2014 at 8:41 | comment | added | Janus | @DanielLichtblau: Yes, you are right of course that for a large polygon you want to do something hierarchical along the lines of your answer to get decent scaling. One reason I keep coming back to this implementation is the partitioning guarantee which is critical in much of what I do. | |
| Jan 20, 2014 at 22:53 | comment | added | Daniel Lichtblau | The speed will depend linearly on the number of vertices. That is often fine but could be a problem if there are both many vertices and many query points. | |
| Jan 20, 2014 at 21:13 | history | answered | Janus | CC BY-SA 3.0 |