So for reference I’m using this tutorial
Basically, I am looking to make an algorithm that decomposes rectilinear polygons into rectangles (finding minimum decomposition isn’t a concern), it’s generally going okay but I’ve run into an issue with the linked algorithm. I believe the issue is because it states to cast a 2D ray from one point to another to find if a point is valid but I’m not too sure.
Basically I have this polygon whose vertices are placed in counter-clockwise direction:
The linked post states to eliminate points b and c that are adjacent to some reflex vertices should they meet the following conditions:
1- The next vertex (b) is not a reflex vertex
2- The angle between angle abc, where a is the chosen reflex vertex and b and c are the next vertices, is 90 degrees and repeat until only 4 vertices remain.
The script does that fine for the first iteration, it chooses the red reflex vertex, and eliminates the 2 topmost vertices (crossed out in blue)
So now my polygon looks like this.
The problem now arises from the fact that the next reflex vertex that is chosen is the following, and thus again the two topmost vertices are eliminated:
My polygon now looks like this, however now the two pink vertices exist because the algorithm tried to make a point between the reflex vertex and the left-upper vertex:
The reason it happened was because there was supposed to be a ray that was cast between the reflex vertex and the edge to the left, circled in pink:
So that leads me now to post this question, my question is, what did that linked post mean by a 2d ray? I’m thinking it means either checking the intersection through a line intersection formula or casting a real ray in 3d space but I’m not sure which would be the most efficient. Any ideas?