3

My program has a List<Vector3> of unique points (A, B, C, ...) which are created each time a user draws a unique line (1, 2, 3, ...). Lines are stored in a List<int> where every two ints are the indices of each point to form a single line. No two lines can have the same two points, no points can occupy the same position, and stray lines are allowed.

DiagramDiagram

Points: {A, B, C, D, E} //Each letter represents a 2d or 3d position
Sides: {0,1,1,2,1,3,3,4,4,2} //(Each int is an index in Points, every pair is a side)

I am trying to find an efficient way of determining when a new line (Green, 5) closes a polygon with any number of sides. I have a way of doing this: iterating through each line connected to each side of the new line(and all subsequent lines) until they share a point (D).

Completed PolygonCompleted Polygon

My only problem here is that the more sides a polygon has, I need to do exponentially more checks (Every two additional sides on the polygon causes me to check one layer deeper on all attached sides).

Is there a way to reduce the number of checks I need to do in order to close the polygon?

Not exactly the same as Cycles in an Undirected Graph. This knows that at least one cycle is present and connected to a given side, and is looking for only the smallest cycle possible connected to that side. Other sides are irrelevant and it should avoid them.

Philip
  • 43
  • 4
  • What should happen when an edge is drawn between A and C? Should it create a triangle adjacent to the quadrilateral or a larger polygon where edge 2 is ignored? Can polygons overlap? – Stringfellow May 28 '18 at 15:36
  • A second polygon should be created (A, B, C) with the same rules as the first (C, B, D, E) – Philip May 28 '18 at 17:04
  • Possible duplicate of [Cycles in an Undirected Graph](https://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph), as it should be noted that your list is an undirected graph and polygons are cycles or loops within that graph. – Draco18s no longer trusts SE May 28 '18 at 17:36
  • Not exactly. This knows that at least one cycle is present and connected to a given side, and is looking for only the smallest cycle possible. – Philip May 28 '18 at 18:03

1 Answers1

1

It all depends on the level of optimization you need. For simple pictures (some what like < 10 - 100k lines) you can get away with running a BFS every time.

High level algorithm:

First you need something to store the graph using one of the Graph representation. Then whenever the user draws a line you take either of the two points and do a BFS on that point.

If you can reach the same point with your BFS and the path length is > 2 then you have a polygon.

The catch would be that since the graph is bidirectional you need to be careful when walking thru it. Do not re-visit nodes that you have already visited.

Steve
  • 11,696
  • 7
  • 43
  • 81
  • This is essentially what I was doing in the second diagram, although I didn't know what it was called. Basically I do a BFS from each side, with side E and C as the top layer of each. I go down one layer in each and check for matches, that would form a triangle. If nothing matches, I drop another layer in either side(C) and check for matches again, this would be a quad. If nothing matches there, I drop a layer in the opposite side(E) and check again. I was hoping something would be more efficient, but this is probably the fastest solution for now. – Philip May 28 '18 at 17:18
  • @Philip I think you understood it wrong. you only need to do BFS from ONE side. The goal is to find a circular path back to itself without repeating edge. BFS is O(n) where n is the number of edges(lines) so its a linear algorithm instead of exponential. – Steve May 28 '18 at 19:34