# Detect perimetral edges of a polygon [closed]

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?

## closed as off-topic by Chris Godsil, j.c., Johannes Hahn, Joonas Ilmavirta, John PardonJun 20 '15 at 16:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question does not appear to be about research level mathematics within the scope defined in the help center." – Chris Godsil, Johannes Hahn, John Pardon
If this question can be reworded to fit the rules in the help center, please edit the question.

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."