11
\$\begingroup\$

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.

Figure 1

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.

Figure 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    
\$\endgroup\$
  • 1
    \$\begingroup\$ "Connectivity of the polygon is guaranteed by the condition that every triangle in the input triangulation shares at least 1 side with another triangle." -- no. That's not a sufficient condition. Take, for example, T=1,2,3/1,2,4/5,6,7/5,6,8. Every triangle shares an edge with another triangle, but the triangulation is disconnected \$\endgroup\$ – John Dvorak May 19 '13 at 6:40
  • \$\begingroup\$ May we assume the input represents a valid partial triangulation (no two triangles overlap and no triangle is present twice) and the triangulation is connected? \$\endgroup\$ – John Dvorak May 19 '13 at 6:43
  • \$\begingroup\$ Note that the number of holes is not the genus of the shape. Every subset of plane has a genus of 0. "The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected" \$\endgroup\$ – John Dvorak May 19 '13 at 6:47
  • \$\begingroup\$ May we also assume the input is edge-connected in the sense it is not possible to remove a finite set of points to render the shape disconnected? (ex: T=1,2,3/1,4,5 is connected but not edge-connected) \$\endgroup\$ – John Dvorak May 19 '13 at 6:55
  • 2
    \$\begingroup\$ I'm not sure why this business about end dates has started cropping up recently. You're allowed to change the accepted answer, so there's no need to set an end date. It's reasonable to have a mental idea that you'll wait a week before selecting an answer in order not to scare people into thinking that the first answer is unbeatable, but as long as you're active on the site you can change the selected answer if someone posts a better one. Relevant meta discussions include meta.codegolf.stackexchange.com/q/542/194 and meta.codegolf.stackexchange.com/q/193/194 \$\endgroup\$ – Peter Taylor May 21 '13 at 9:20
5
\$\begingroup\$

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)

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ +1 for using the splat, using frozenset instead of sorting, zip (can't say I've ever used it before, need to acquaint myself.) \$\endgroup\$ – Kaya May 21 '13 at 5:21
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Pretty much exactly what my GolfScript solution does. I'm surprised it's so much longer than GolfScript. \$\endgroup\$ – Peter Taylor May 22 '13 at 9:06
  • \$\begingroup\$ @PeterTaylor I was surprised your GolfScript solution was so much shorter! (But then again, it is GolfScript) \$\endgroup\$ – Volatility May 22 '13 at 9:11
2
\$\begingroup\$

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
 *)
\$\endgroup\$
  • \$\begingroup\$ Doesn't this rely on the triangles or holes having certain minimal size (the argument to Erosion)? \$\endgroup\$ – John Dvorak May 19 '13 at 18:29
  • \$\begingroup\$ @JanDvorak Perhaps I'm wrong, but I think that unless you use infinite precision arithmetic, any solution will work until you reach a certain minimal size (you'll have to decide if three points are aligned or not). It's just that in this kind of solution the problem is explicitly stated. \$\endgroup\$ – Dr. belisarius May 19 '13 at 19:45
  • \$\begingroup\$ if you use the topological approach, you don't have to. If there are three points collinear then you require a zero-area triangle there - otherwise you have a hole. \$\endgroup\$ – John Dvorak May 19 '13 at 19:48
  • \$\begingroup\$ @belisarius. Here's the answer I received from Wolfram Technical Support about the discrepancy between our results: "Hello - Thank you for your email. I have confirmed that your code gives different results on Mac and Windows. I do not think that this is intended behavior, so I have filed a report with our developers on the issue. I will be sure to pass on any useful information that I get from our developers on this issue. Please let me know if you have any further questions. ...Technical Support Wolfram Research, Inc." \$\endgroup\$ – DavidC May 21 '13 at 19:25
  • \$\begingroup\$ @DavidCarraher "Yes, I have further questions: Will you send me a check for each bug?" \$\endgroup\$ – Dr. belisarius May 21 '13 at 21:55
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Yay, an euler characteristic approach. That's how I did it in python. \$\endgroup\$ – Kaya May 19 '13 at 19:20
  • 2
    \$\begingroup\$ @Kaya. (See Egg of Columbus en.wikipedia.org/wiki/Egg_of_Columbus) Once someone has given an Eulerian answer to your question, the likelihood that others will follow increases greatly. I can assure you it's far more challenging and gratifying to discover the approach on one's own, only afterwards making the connection to Euler's work with polyhedra. \$\endgroup\$ – DavidC May 21 '13 at 13:40
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ are you basically rasterising the triangulation and dumping a graphics library on that image? Doesn't that fail if a hole is too small? \$\endgroup\$ – John Dvorak May 19 '13 at 19:25
  • 1
    \$\begingroup\$ your second example returns 0 here (that's why I haven't used MorphologicalEulerNumber[]). Mma 9.01, Win XP. \$\endgroup\$ – Dr. belisarius May 19 '13 at 19:25
  • \$\begingroup\$ I'm using 9.0.1 also, but on a Mac. Are you're saying Mathematica returns a different answer from mine on Windows? If so, that sounds like a bug (in the Windows XP version). \$\endgroup\$ – DavidC May 19 '13 at 19:31
  • \$\begingroup\$ @DavidCarraher Yep: i.stack.imgur.com/LKcr1.png \$\endgroup\$ – Dr. belisarius May 19 '13 at 19:40
  • \$\begingroup\$ @Jan Dvorak. MorphologicalEulerNumber sometimes requires an image; it refuses to accept a graphics object. In these cases, the size of the hole and the resolution are critical (see codegolf.stackexchange.com/questions/8706/…). But here it works directly with the Graphics object, which explicitly contains all of the vertices. I imagined (or hoped) that it would use an approach that did not depend on the image. I wish I knew how it attempted to solve the issue. Perhaps some spelunking in the source code for the function will clarify things. \$\endgroup\$ – DavidC May 19 '13 at 19:48
1
\$\begingroup\$

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
\$\endgroup\$

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.