Number of holes in a polygon

Question

The Problem: Count the number of holes in a connected polygon. Connectivity of the polygon is guaranteed by the condition that every triangle in the input triangulation shares at least 1 side with another triangle and that there is only one such connected set of triangles.

Input is a list L of n points in the plane and a list T of 3-tuples with entries from 0...n-1. For each item in T the tuple (t_1,t_2,t_3) represents the three vertices (from the list L) of a triangle in the triangulation. Note that this is a triangulation in the sense of 'polygon triangulation', because of this there will never be two triangles in T that overlap. An additional stipulation is that you will not have to sanitize the input, L and T do not contain any repeats.

Example 1: If L = {{0,0},{1,0},{0,1},{1,2}} and T = {{0,1,2},{1,2,3}} then the polygon specified has a hole count of 0.

Example 2: If L = {{0,0},{1,0},{2,0},{2,1},{2,2},{1,2},{0,2},{0,1},{.5,.5},{1.5,.5},{1.5,1.5},{.5,1.5}} and T = {{5,6,11},{5,10,11},{4,5,10},{3,8,10},{2,3,9},{2,8,9},{1,2,8},{0,1,8},{0,8,11},{0,7,11},{6,7,11},{3,4,10}} then the polygon input should result in an output of 2.

The task is to write the shortest program (or function) that takes L and T as input and returns the number of holes. The 'winner' will be recognized as the entry with the least character count (tentative end date 1st of June).

Sample input formatting (note the 0 indexing):

0,0
1,0
0,1
1,2
0,1,2
1,2,3    

Answer 1

GolfScript (23 chars)

~.{2*2/~}%{$}%.&,@@+,-)

Assumes input format using GolfScript array notation and quoted (or integral) coordinates. E.g.

$ golfscript codegolf11738.gs <<<END
[["0" "0"] ["1" "0"] ["2" "0"] ["2" "1"] ["2" "2"] ["1" "2"] ["0" "2"] ["0" "1"] [".5" ".5"] ["1.5" ".5"] ["1.5" "1.5"] [".5" "1.5"]] [[5 6 11] [5 10 11] [4 5 10] [3 8 10] [2 3 9] [2 8 9] [1 2 8] [0 1 8] [0 8 11] [0 7 11] [6 7 11] [3 4 10]]
END
2

(Online equivalent)

or

$ golfscript codegolf11738.gs <<<END
[[0 0] [1 0] [0 1] [1 2]] [[0 1 2] [1 2 3]]
END
0

(Online equivalent)

Answer 2

Python, 71

What follows is a program (not a function) that calculates the desired number.

len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1

Example usage:

>>> L = ((0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,1),(.5,.5),(1.5,.5),(1.5,1.5),(.5,1.5))
>>> T = ((5,6,11),(5,10,11),(4,5,10),(3,8,10),(2,3,9),(2,8,9),(1,2,8),(0,1,8),(0,8,11),(0,7,11),(6,7,11),(3,4,10))
>>> len(set().union(*(map(frozenset,zip(t,t[1:]+t))for t in T)))-len(L+T)+1
2

Answer 3

APL, 36

{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}

The function takes L as its left argument and T as its right.

For example:

      L←(0 0)(1 0)(0 1)(1 2)
      T←(0 1 2)(1 2 3)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
0
      L←(0 0)(1 0)(2 0)(2 1)(2 2)(1 2)(0 2)(0 1)(.5 .5)(1.5 .5)(1.5 1.5)(.5 1.5)
      T←(5 6 11)(5 10 11)(4 5 10)(3 8 10)(2 3 9)(2 8 9)(1 2 8)(0 1 8)(0 8 11)(0 7 11)(6 7 11)(3 4 10)
      L{1+(⍴⊃∪/{{⍵[⍋⍵]}¨,/3 2⍴⍵,⍵}¨⍵)-⍴⍺,⍵}T
2

---

Explanation, going from right to left:

• ⍴⍺,⍵ concatenates the two input vectors and returns their length (V + F)
• Stepping inside the next block:
  • ¨⍵ applies the function on the left to every element of the right argument and returns the result
  • ⍵,⍵ returns the right argument concatenated with itself
  • 3 2⍴ shapes the vector argument into three pairs. In this case it pairs together the first and second, third and first, and second and third items of the vector.
  • ,/ joins the vector argument together
  • ⍵[⍋⍵] sorts the right argument
  • ∪/ filters out any duplicates
  • ⍴⊃ turns a nested scalar into a vector, and it returns the length of it.
  • The whole function returns the number of edges in the shape (E)
• 1 is self-explanatory (I hope...)

The whole function then returns 1+E-(V+F), or 1-(F+V-E).

Answer 4

Mathematica, 93 (not much golfed yet)

f[l_, t_] :=  Max@MorphologicalComponents[Erosion[Graphics[
                                                        GraphicsComplex[l, Polygon[t + 1]]], 1]] - 1

(Spaces added for clarity)

Testing:

f[{{0, 0}, {1, 0}, {0, 1}, {1, 2}}, {{0, 1, 2}, {1, 2, 3}}]
(*
 -> 0
*)

{l, t} = {{{0, 0}, {1,   0}, {2,    0}, {2,     1}, {2,    2}, {1, 2}, {0, 2}, 
           {0, 1}, {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}}, 

           {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3,  9}, 
            {2, 8,  9}, {1,  2,  8}, {0, 1,  8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}}};
f[l, t]
 (*
  -> 2
 *)

Answer 5

Mathematica 76 73 72 67 62

After much experimentation, I came to realize that the precise location of the vertices was of no concern, so I represented the problem with graphs. The essential invariants, the number of triangles, edges and vertices stayed invariant (provided line crossing was avoided).

There were two kinds of internal "triangles" in the graph: those were there was presumably a face, i.e. a "filled" triangle, and those where there were not. The number of internal faces did not have any relation to the edges or vertices. That meant that poking holes in fully "filled" graphs only reduced the number of faces. I played systematically with variations among triangles, keeping track of the faces, vertices and edges. Eventually I realized that the number of holes always was equal to 1 - #faces -#vertices + #edges. This turned out to be 1 minus the Euler characteristic (which I only had known about in the context of regular polyhedra (although the length of the edges was clearly of no importance.

The function below returns the number of holes when the vertices and triangles are input. Unlike my earlier submission, it does not rely on a scan of an image. You can think of it as 1 - Euler's characteristic, i.e. 1 - (F +V -E) whereF= #faces, V=#vertices, E=#edges. The function returns the number of holes, 1 - (F + V -E), given the actual faces (triangles) and vertices.

It can be easily shown that the removal of any triangle on the outside of the complex has no affect on the Euler characteristic, regardless of whether it shares one or 2 sides with other triangles.

Note: The lower case v will be used in place of the L from the original formulation; that is, it contains the vertices themselves (not V, the number of vertices)

f is used for the T from the original formulation; that is, it contains the triangles, represented as the ordered triple of vertex indices.

Code

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&

(Thanks to Mr. Wizard for shaving off 5 chars by eliminating the replacement rule.)

---

Example 1

v = {{0, 0}, {1, 0}, {0, 1}, {1, 2}}; f = {{0, 1, 2}, {1, 2, 3}};

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

0

Zero holes.

---

Example 2

v = {{0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}, {1, 2}, {0, 2}, {0, 1}, {.5, .5}, {1.5, .5}, {1.5, 1.5}, {.5, 1.5}}; f = {{5, 6, 11}, {5, 10, 11}, {4, 5, 10}, {3, 8, 10}, {2, 3, 9}, {2, 8, 9}, {1, 2, 8}, {0, 1, 8}, {0, 8, 11}, {0, 7, 11}, {6, 7, 11}, {3, 4, 10}};

z=Length;1-z@#2-z@#+z[Union@@(Sort/@{#|#2,#2|#3,#3|#}&@@@#2)]&[v, f]

2

Thus, 2 holes are in example 2.

Answer 6

Ruby, 239 characters (227 body)

def f t
e=t.flat_map{|x|x.permutation(2).to_a}.group_by{|x|x}.select{|_,x|x.one?}.keys
n=Hash[e]
(u,n=n,n.dup;e.map{|x|a,b=*x;n[a]=n[n[a]]=n[b]})until n==u
n.values.uniq.size+e.group_by(&:last).map{|_,x|x.size}.reduce(-1){|x,y|x+y/2-1}
end

note that I'm only considering the topology. I'm not using the vertex positions in any way.

caller (expects T in Mathematica or JSON format):

input = gets.chomp
input.gsub! "{", "["
input.gsub! "}", "]"
f eval(input)

Test:

f [[0,1,2],[1,2,3]]
#=> 0
f [[5, 6, 11], [5, 10, 11], [4, 5, 10], [3, 8, 10], [2, 3, 9], [2, 8, 9], [1, 2, 8], [0, 1, 8], [0, 8, 11], [0, 7, 11], [6, 7, 11], [3, 4, 10]]
#=> 2
f [[1,2,3],[3,4,5],[5,6,1],[2,3,4],[4,5,6],[6,1,2]]
#=> 1

Answer 7

Python, 107

I realized that taking the pairs directly was shorter than from itertools import* and typing combinations(). Yet I also noticed that my solution relied on the input triangular faces having their vertices listed in consistent order. Therefore the gains in character count are not that large.

f=lambda l,t:1-len(l+t)+len(set([tuple(sorted(m))for n in[[i[:2],i[1:],[i[0],i[2]]]for i in t]for m in n]))

Python, 115

Euler characteristic approach, the verbosity of itertools seems impossible to avoid. I wonder if it would be cheaper to use a more direct technique for making pairs of vertices.

from itertools import*
f=lambda l,t:1-len(l+t)+len(set([m for n in[list(combinations(i,2)) for i in t]for m in n]))

Usage example:

> f([[0,0],[1,0],[0,1],[1,2]],[[0,1,2],[1,2,3]])
> 0
> f([[0,0],[1,0],[2,0],[2,1],[2,2],[1,2],[0,2],[0,1],[.5,.5],[1.5,.5],[1.5,1.5],[.5,1.5]],[[5,6,11],[5,10,11],[4,5,10],[3,8,10],[2,3,9],[2,8,9],[1,2,8],[0,1,8],[0,8,11],[0,7,11],[6,7,11],[3,4,10]])
> 2