I have to write a script, which can decide, if a point P is inside a polygon-like groundplan like in the picture, or if it is outside. Problem is, that there can be nodes of the “polygon” inside the “polygon” and there might also be nodes with just one edge. In addition, there even might be a second “polygon” that is not closed at all. I am totally lost and have no idea how to handle all the specific situations, that go beyond “there is a convex polygon => do a raycasting algorithm”.
It would already help to know how to split this ground plan in closed triangles.
Thanks for any help.
The picture above is the topview of a room. Lines are walls and nodes are corners of the room. In my case the user can draw his own groundplan, so it is possible, that the game hase to handle a structure like this in the picture. Now I want the furniture, which can be draged and droped, to only be moveable within the borders of a closed room. So I have to decide, wether the mouse points to a point inside or outside the room.
To sort out needless wall segments is an idea, I already had, too. But I don’t know how to prove, that a wall segment is needless.
If an edge have only one segment(wall) connected then it can be removed since this for sure not part of a graph circle. Just iterate over all the edges and edges connected to the removed edges
You mean the raycasting, right? If I set the mouse in the middle left of the pic and cast a ray to the right, then it will intersect with the “needless” wall segment in the middle. So I have an odd number of intersections, which means for the algorithm, that the point is INSIDE the polygon, which it is not actually.
The raycasting algorithm will also fail with the first sample, where two rooms next to each other are sharing the same wall. If I put the mouse in the left room and cast a ray to the right, it will intersect with the shared wall and the outer right wall. I get an even number of intersections, which means the point must be OUTSIDE, but I put it into the left room.
So raycasting is not working at all, until I can eliminate walls inside a room as well as walls outside a room. By writing this I think it is necessary to find a concave hull.
I think you need to check if an edge is part of a circle graph.
Let v1 and v2 be the 2 vertex of the edge then the edge is part of a circle only if there is a path from v1 to v2 in the original graph without the edge being considered.
