I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the PointInPolygon algorithm. Let me illustrate the problem. I have this room.
#-----------#
| |
| |
| #-----#
| |
| |
| |
#-----#
Now I want to create another room by connecting two of the vertices like this:
#-----------#
| |
| |
| V--Ae--X < first click
| | |
| Be | <--new room
| | |
#-----Y-----#
^
second click
I need to detect the vertex V and the edges A and Be. I tried to implement the convex hull algorithm to find the external walls, but there are degenerated cases where those edges are interior walls... I even tried the Dijstra's algorithm to find the shortest path between X and Y, but again there are degenerated cases like this:
first click
v
X----------# < second click
| |
#-----#-V--e--#V |
| | | |
| | |e | <--new room
| | | |
#-----#-V--e--#V |
| |
Y----------# < third click
^
fourth click
I think the answer is in some graph algorithm (which I'm not really in). How should I approach this problem?