Post Closed as "Not suitable for this site" by Chris Godsil, j.c., Johannes Hahn, Joonas Ilmavirta, John Pardon

occurred Jun 20, 2015 at 16:30

Changed tags

Link

edited Jun 20, 2015 at 14:58

suchoparek

3
2

added 1 character in body

Source Link

edited Jun 20, 2015 at 11:52

suchoparek

3
2

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--Ae--X < first click
|     |     |
|     Be     | <--new room
|     |     |
#-----Y-----#
      ^
second click

I need to detect the vertex V and the edges A and Be. 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?

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

I think the answer is in some graph algorithm (which I'm not really in). How should I approach this problem?

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?

Source Link

asked Jun 20, 2015 at 11:46

suchoparek

3
2

Detect perimetral edges of a polygon

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

I think the answer is in some graph algorithm (which I'm not really in). How should I approach this problem?

graph-theory polygons

Stack Exchange Network

Return to Question

Detect perimetral edges of a polygon