Detect perimetral edges of a polygon [closed]

Question

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?

Answer 1

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. See the Wikipedia article on Boolean polygon operations, or see my answer 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.