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.

1 Answer

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.

• Hi @Joseph, you hit the spot with that "wrap around". I didn't think about a boolean operation, though I already use a clipper library... :) I should need to try with some ultra-degenerated case, but I think it could go works. Thank you. – suchoparek Jun 20 '15 at 14:49