Hi, 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--A--X < first click
| | |
| B | <--new room
| | |
#-----Y-----#
^
second click
```

I need to detect the vertex V and the edges A and B. 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
| |
#-----#-----# |
| | | |
| | | | <--new room
| | | |
#-----#-----# |
| |
Y----------# < third click
^
fourth click
```

How should I approach this problem?