Tracking the connection of vertices and determening when a polygon is made

Question

I'm trying to work on a game mechanic in c# that involves connecting vertices and forming polygons.

There can be any number of 5 - 30 vertices. Each vertice can be connected with a straight line(The lines cannot intersect). When the line closes a polygon the inside of the polygon is colored in a specific color. (You cannot close a polygon if there would be a point inside it during the closing)

For example two pictures below cannot happen:

However, this can:

What i am having trouble with is how to discern the polygon i have just closed and remembering it (in case i close a polygon that shares an edge with it). I can have multiple closed polygons until all lines that can be drawn from each vertice without breaching the intersect rule can be drawn.

I tried remembering lines that were drawn AB, ED, CD, CA etc.. and looking for a cycle, but when i close multiple polygons i need more information to know which polygon has already been closed. But I'm having difficulty figuring out how to do so.

For example (picture below), if the line n was drawn i want to find the polygon that was just made.

Does anyone have any idea how i might achieve this? Any idea, help, insight would be helpfull.

Answer 1

When a player trys to claim a new edge you can:

• check that the edge does not cross any of the existing claimed edges;
• perform a breadth-first search of the graph formed by the claimed edges (which are not already on the boundary of two polygons) to see if there is an existing path starting at one end of the new edge which reaches the other end of the new edge - in which case a polygon will be formed; and
• if a polygon has been formed:
  • check to see if there are any vertices inside the polygon - in which case the player cannot claim that edge.
  • Each edge has two sides. The interior of the formed polygon will be on one side of each edge along its boundary - you can track this and then any subsequent polygons which are also bounded by one (or more) of those edges must be on the other side of those edge(s) to be a valid selection within your game. If an edge has claimed polygons on both sides then it cannot be on the boundary of any subsequent polygons.

You may need to generate a convex hull around the points to exclude the exterior polygon so that when players are forming polygons they are restricted to the interior of the convex hull.

Answer 2

Possibly a bit simplistic, but you can store a Dictionary<Face,List<Vertex>> which you can interrogate with linq.

You can simplify it by adding the reverse lookup. Dictionary<Vertex, List<Faces>>

Scenario 1: Path touches edges which are part of the same face

To test a new path DC you get the 2 vertices, D and C and find any faces which contain both. Start with D in the List<Vertex> and create the path to C.

Now do the same with C -> D.

You now have 2 paths, D -> E -> C and C -> A -> B -> D both form valid faces using D -> C so now you have to enumerate all the vertices and eliminate any faces which contain an existing vertex.

Scenario 2: Path touches an edge which are not part of any face

This path is open.

Scenario 3: Path touches eges which are part of different faces

Face1: ABDEC Face2: AGF

Testing the path FC. F is part of Face2 C is part of Face1.

Find intersections: Face1.Face2 == A it's the only point in both lists, this time you get 2 sets of 2 paths.

FA
FGA

AC
ABDEC

To go from F to A, these paths multiply

FAC FGAC FABDEC FGABDEC

These faces can now be tested for validity.

It might be easier for this an more complex scenarios (3 faces touching, faces sharing edges) to also keep a graph of all connected edges, this would give you an easier way to detect possible paths between 2 vertices.

Note that ANY path containing 3 vertices forms a possible face which can be checked for validity