Need clarification on what rectangle decomposition tutorial means by "cast a 2d ray"

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:

image

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)

image

So now my polygon looks like this.
image

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:

image

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:
image

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:
image

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?

Just wanted to bump as I’m still experiencing the issue. Can also elaborate if there’s any missing info

Raycasts would only work if you have some parts to hit, which it doesn’t look like you do. So I’d use the line intersection formula if I were you. Although you could use the fact that all edges are aligned to the axes to make a simpler version of line intersection.

1 Like

I’d say it is basically asking for the intersection with the bounding box. It is also implying to check for any intersections that would get in the way / collide first. There may be some existing 2D raycasting libraries out there but if not then it shouldn’t be too tricky to make a simple one yourself.

I don’t see the in built raycasting to be any good for this as you’d actual parts to do the raycasting.

1 Like

Late response but this was indeed what I did, also took into account the axis-parallel factor and now it “rectangulates” perfectly and doesn’t rely on advanced calculus formulas, thank you for that!

image

1 Like

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.