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--e--X < first click | | | | e | <--new room | | | #-----Y-----# ^ second click
I need to detect the vertex V and the edges e. 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?