Timeline for How can I efficiently determine which side of a line segment is internal to the polygon?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2020 at 6:11 | comment | added | Ville Salo | "Pick the vertex with the highest $x$ value" is basically how every algorithm in computational geometry starts (at least the most basic algorithms, I never got many pages deep into the subject). | |
| Jun 27, 2010 at 15:20 | comment | added | Kevin Nuckolls | At first I thought that I'd have to go through the list of possibly millions of vertexes looking for the highest x value. Then return through the list again to do the actual labeling. A more efficient way would be to just go through the list of vertexes once labeling along the way, making an assumption as to which side was the initial "inside". Traversing the list we can also keep track of the highest x value. When we find it, if we find that our assumption was incorrect and that all the "inside" labels are actually "outside" labels, then we just flip the label for all of the labels. | |
| Jun 27, 2010 at 15:15 | vote | accept | Kevin Nuckolls | ||
| Jun 27, 2010 at 7:43 | vote | accept | Kevin Nuckolls | ||
| Jun 27, 2010 at 7:44 | |||||
| Jun 27, 2010 at 2:21 | history | answered | Anton Lukyanenko | CC BY-SA 2.5 |