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?



Detect perimetral edges of a polygon
Your 3rd example indicates you permit the user to enter a polygon $P$ that overlaps with
previous polygons $R$, with the expectation that $P$ should "wrap around" $R$.
If you want this level of generality, then you need to implement Boolean subtraction
on [orthogonal polygons](https://en.wikipedia.org/wiki/Rectilinear_polygon). See the 
[Wikipedia article on Boolean polygon operations](https://en.wikipedia.org/wiki/Boolean_operations_on_polygons), or
see [my answer](https://mathoverflow.net/a/111323/6094) to the earlier question, 
"Subtract Rectangle from Polygon."


In graphics, these are called *clipping algorithms*; there are many algorithms
available. Your task is easier because you are only considering orthogonal polygons.
Likely sweeping over your polygons with a vertical line would lead to the simplest
algorithm.


Alternatively, you could restrict the level of input generality to avoid the need
for Boolean subtraction.


