0
$\begingroup$

In a 2 dimensional plane [given that I know the vertices of the start and end of a number of connected lines], how can I calculate the faces [enclosed by those lines](and there respective vertices) from the lines in the plane?

A slightly less crude diagram (only slightly)

In this example I am looking to identify (mathematically not visually) faces 1, 2 and 3 in the form:

Face 1: [J, H, F, B]

Face 2: [A, J, B]

Face 3: [B, F, E, C]

Doing this in software, I first discard the edges that are not connected to another edge then start traversing around the remaining edges but it seems there must be an efficient way to do this.

Ed

$\endgroup$
  • $\begingroup$ What do you mean by faces? Since in 2D there are no faces. $\endgroup$ – Irregular User May 31 '16 at 14:35
  • 2
    $\begingroup$ Can you give us an example of the input and output? Is the input a set of lines? (perhaps given by equations fof the form $Ax + By + C = 0$)? $\endgroup$ – John Hughes May 31 '16 at 14:37
  • $\begingroup$ @JohnHughes Yes, sorry I've included a diagram and update the question to be more clear. $\endgroup$ – Ed Bishop Jun 1 '16 at 8:43
  • $\begingroup$ By "lines" you seem to mean "line segments, identified by their endpoints". In your drawing, how would the segment extending downward (perhaps infinitely down?) from the lower-left corner of face 1 be identified? $\endgroup$ – John Hughes Jun 1 '16 at 11:42
  • $\begingroup$ Also, suppose I have a square with vertices ABCD, and center E. As input, I provide AB, BC, CD, DE, but also include AE. Should the output for the (only) "face" be $A-B-C-D-A-E-A$? $\endgroup$ – John Hughes Jun 1 '16 at 11:43
1
$\begingroup$

I’m going to call the inputs to the program vertices and segments. The vertices are numbered, and represent points in the plane, so that

1: (0, 3)
2: (1.1, 5.2)
3: (2, 4)

represents first a vertex named “1”, whose $x$-coordinate is $0$ and whose $y$-coordinate is $3$, then a vertex named “2” whose $x$-coordinate is $1.1$ and whose $y$-coordinate is $5.2$, and so on.

So the vertices form an array $v$ of $xy$-pairs.

The “segments” are described by pairs (I’ll use brackets for these to distinguish them from coordinate pairs) of vertex-indexes, so that an edge between the first two vertices above is described either as $[1, 2]$ or as $[2, 1]$. I’ll actually distinguish between these two, calling any such ordered pair of vertex indices a “dart” (because that’s the term that folks who do planar graphs use). So for any segment, there are two different “darts” corresponding to that segment, one in each “direction”.

I’m going to assume you can do some things in whatever programming language you’re using, things like

  • For a vertex $A$, find a list of all vertices $X$ such that $[A,X]$ or $[X, A]$ is an input segment,

  • For an segment $s$ for which you know one end, $A$, find the other end.

  • For a dart $[i, j]$, compute the vector $u_{ij}$ that’s gotten by subtracting the coordinates of $v[i]$ from $v[j]$. So associated to the dart $[1, 2]$ in the example above is the vector $$ (1.1, 5.2) - (0, 3) = (1.1, 2.2). $$ I’m going to be sloppy and use parentheses to denote both points and vectors.

  • Keep a record of items in a set that have been “touched”; I’d generally use a hash map for this, hashing each item in the set to value 0, and when it gets “touched”, re-hashing it to value “1”, but you might use an array or many other possible structures to do this. We’ll be keeping track of which darts have been “touched”.

  • For any nonzero vector $(u, v)$, compute the angle from the positive $x$-axis counterclockwise to this vector. In most programming languages, this can be done by writing $$ t = atan2(v, u) $$; $t$ is then an angle between -180 and 180 degrees, or $-\pi$ and $\pi$ radians. Frankly, it doesn’t matter which one it is for our purposes.

OK, here’s what you need to do:

SETUP:

  1. Start with an empty list of darts, $Q$.

  2. For each input segment, compute the two darts associated to that segment and place these two darts in the list $Q$. In your example, (using letters instead of numbers, because that’s what you did) the dart list looks like (reading from the upper left, more or less, and skipping the brackets and commas):

AB, BA, BC. CB, CD, DC, JB, BJ, JH, HJ, BF, FB, CE, EC, FE, EF, …, FG, GF.

  1. For each vertex, form a list of all darts in the dart-list that originate at that vertex, i.e., for vertex index $i$, find all darts of the form $[i, z]$, where $z$ is any index. Call this the “star” of vertex $i$. The star of index $B$ in your example would contain $BA, BC, BJ, BF$, in no particular order.

  2. For each vertex, for each dart in the star of that vertex, compute the vector associated to that dart, and then find its angle from the $x$-axis; then sort the darts in the star by increasing angle. In your example, the star of vertex $F$ would consist of the darts $[F, H], [F, G], [F, E], [F, B]$ after sorting.

We’ll sometimes talk about the “next” dart in a star, meaning the one after it in the ordered list, with the rule that the “next” dart after the last dart is the first one, so that in our example, the next dart after $[F, G]$ is $[F, E]$, but the next dart after $[F, B]$ is $[F, H]$. So "next" means “next one around reading counterclockwise”. From now on, I’ll assume that the star of each vertex is ordered like this. Note that if the star of a vertex contains only one dart, $u$, then the "next" dart after $u$ is just $u$.

  1. Mark each dart in the dart-list $Q$ as “untouched”.

The main algorithm:

Foreach dart d in the dart list Q; set polygon = empty list if dart d is marked, do nothing otherwise: while d is unmarked: mark the dart d add the dart d = [i, j] to the polygon in the star for vertex j, the dart [j,i] appears somewhere; set d to the the next dart in the star after that one end while output polygon end foreach

For instance, in your example,the first dart in the dart-list $Q$ might start be $JB$. We set the polygon $$ to be empty. Now we enter the loop. We mark the dart $JB$, and add it to the polygon.

We go to vertex $B$ and look at its dart-list $(BJ, BF, BC, BA)$, and find the dart after $BJ$, namely $BF$. We set $d$ to $BF$. We mark $BF$, add it to the polygon (which is now $JB, BF$).

We now go to vertex $F$ and look at its dart-list $(FH, FG, FE, FB)$ and the dart following $FB$ is $FH$. We set $d$ to $FH$. We mark $FH$, add it to the polygon (which is now $JB, BF, FH$).

We go to vertex $H$ and look at its dart-list $(HI, HF, HJ)$, and find the dart after $HF$, namely $HJ$. We set $d$ to $HJ$. We mark $HJ$, and add it to the polygon (which is now $JB, BF, FH, HJ$).

Finally, we go to vertex $J$ and look at its dart-list $(JH, JB, JA)$ and find that after $JH$ comes $JB$…which is marked, so we exit the while-loop, and output the polygon.

We output $JB, BF, FH, HJ$, and move on to the next dart in the dart-list.

If that next dart were, say, $FH$, we’d do nothing with it, because it’s already been marked. But if it were $BC$, we’d do the sort of thing we did above, and eventually output the polygon $BC, CE, EF, FB$.

And then maybe we’d output $$AB, BJ, JA.

But what happens when we get to a dart like, say, $EC$? If you trace through the algorithm as I’ve done above, you’ll see that we output

$EC, CD, DC, CB, BA, JH, HI, IH, HF, FG, GF, FE$

which is the “big outside polygon”, with all the “spur” edges included.

Assuming you can find a given dart within a given star in constant time — you can do this by storing the darts of a star in a dictionary, in which the “value” for each dart is the “next” dart, during the setup phase, all of this takes time that’s linear in the number of segments in the input.

Of course, when you’re done, you have to get rid of things like the $HI, IH$ in the polygon lists. Fortunately, you can do this by representing the polygon as a stack. You push each new dart onto the stack UNLESS the stack’s nonempty and the top of the stack is the opposite dart, in which case you pop off the top of the stack. With that approach, all “spurs” just disappear during the processing phase. :)

$\endgroup$
  • $\begingroup$ I can't thank you enough for spending the time to write such an in depth, clear and well presented answer. If there's any way I can buy you a beer please let me know! $\endgroup$ – Ed Bishop Jun 2 '16 at 17:42
  • $\begingroup$ It was my pleasure. Perhaps you can provide a similarly detailed answer on something YOU know about for another person. $\endgroup$ – John Hughes Jun 3 '16 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.