Faces from a mesh
You are encouraged to solve this task according to the task description, using any language you may know.
A mesh defining a surface has uniquely numbered vertices, and named, simple-polygonal faces described usually by an ordered list of edge numbers going around the face,
For example:
External image of two faces
Rough textual version without edges:
1
17
7 A
B
11
23
- A is the triangle (1, 11, 7), or equally (7, 11, 1), going anti-clockwise, or
any of all the rotations of those ordered vertices.
1
7 A
11
- B is the four-sided face (1, 17, 23, 11), or equally (23, 17, 1, 11) or any
of their rotations.
1
17
B
11
23
Let's call the above the perimeter format as it traces around the perimeter.
- A second format
A separate algorithm returns polygonal faces consisting of a face name and an unordered set of edge definitions for each face.
- A single edge is described by the vertex numbers at its two ends, always in
ascending order.
- All edges for the face are given, but in an undefined order.
For example face A could be described by the edges (1, 11), (7, 11), and (1, 7) (The order of each vertex number in an edge is ascending, but the order in which the edges are stated is arbitrary).
Similarly face B could be described by the edges (11, 23), (1, 17), (17, 23), and (1, 11) in arbitrary order of the edges.
Let's call this second format the edge format.
- Task
1. Write a routine to check if two perimeter formatted faces have the same perimeter use it o check if the following pairs of perimeters are the same:
Q: (8, 1, 3) R: (1, 3, 8) U: (18, 8, 14, 10, 12, 17, 19) V: (8, 14, 10, 12, 17, 19, 18)
2. Write a routine and use it to transform the following faces from edge to perimeter format.
E: {(1, 11), (7, 11), (1, 7)}
F: {(11, 23), (1, 17), (17, 23), (1, 11)}
G: {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)}
H: {(1, 3), (9, 11), (3, 11), (1, 11)}
Show your output here.
Go
<lang go>package main
import (
"fmt" "sort"
)
// Check a slice contains a value. func contains(s []int, f int) bool {
for _, e := range s {
if e == f {
return true
}
}
return false
}
// Assumes s1, s2 are of same length. func sliceEqual(s1, s2 []int) bool {
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
return false
}
}
return true
}
// Reverses slice in place. func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
// Check two perimeters are equal. func perimEqual(p1, p2 []int) bool {
le := len(p1)
if le != len(p2) {
return false
}
for _, p := range p1 {
if !contains(p2, p) {
return false
}
}
// use copy to avoid mutating 'p1'
c := make([]int, le)
copy(c, p1)
for r := 0; r < 2; r++ {
for i := 0; i < le; i++ {
if sliceEqual(c, p2) {
return true
}
// do circular shift to right
t := c[le-1]
copy(c[1:], c[0:le-1])
c[0] = t
}
// now process in opposite direction
reverse(c)
}
return false
}
type edge [2]int
// Translates a face to perimeter format. func faceToPerim(face []edge) []int {
// use copy to avoid mutating 'face'
le := len(face)
if le == 0 {
return nil
}
edges := make([]edge, le)
for i := 0; i < le; i++ {
// check edge pairs are in correct order
if face[i][1] <= face[i][0] {
return nil
}
edges[i] = face[i]
}
// sort edges in ascending order
sort.Slice(edges, func(i, j int) bool {
if edges[i][0] != edges[j][0] {
return edges[i][0] < edges[j][0]
}
return edges[i][1] < edges[j][1]
})
var perim []int
first, last := edges[0][0], edges[0][1]
perim = append(perim, first, last)
// remove first edge
copy(edges, edges[1:])
edges = edges[0 : le-1]
le--
outer:
for le > 0 {
for i, e := range edges {
found := false
if e[0] == last {
perim = append(perim, e[1])
last, found = e[1], true
} else if e[1] == last {
perim = append(perim, e[0])
last, found = e[0], true
}
if found {
// remove i'th edge
copy(edges[i:], edges[i+1:])
edges = edges[0 : le-1]
le--
if last == first {
if le == 0 {
break outer
} else {
return nil
}
}
continue outer
}
}
}
return perim[0 : len(perim)-1]
}
func main() {
fmt.Println("Perimeter format equality checks:")
areEqual := perimEqual([]int{8, 1, 3}, []int{1, 3, 8})
fmt.Printf(" Q == R is %t\n", areEqual)
areEqual = perimEqual([]int{18, 8, 14, 10, 12, 17, 19}, []int{8, 14, 10, 12, 17, 19, 18})
fmt.Printf(" U == V is %t\n", areEqual)
e := []edge{{7, 11}, {1, 11}, {1, 7}}
f := []edge{{11, 23}, {1, 17}, {17, 23}, {1, 11}}
g := []edge{{8, 14}, {17, 19}, {10, 12}, {10, 14}, {12, 17}, {8, 18}, {18, 19}}
h := []edge{{1, 3}, {9, 11}, {3, 11}, {1, 11}}
fmt.Println("\nEdge to perimeter format translations:")
for i, face := range [][]edge{e, f, g, h} {
perim := faceToPerim(face)
if perim == nil {
fmt.Printf(" %c => Invalid edge format\n", i + 'E')
} else {
fmt.Printf(" %c => %v\n", i + 'E', perim)
}
}
}</lang>
- Output:
Perimeter format equality checks: Q == R is true U == V is true Edge to perimeter format translations: E => [1 7 11] F => [1 11 23 17] G => [8 14 10 12 17 19 18] H => Invalid edge format
Julia
<lang julia>iseq(f, g) = any(n -> f == circshift(g, n), 1:length(g))
function toface(evec)
try
ret, edges = collect(evec[1]), copy(evec[2:end])
while !isempty(edges)
i = findfirst(x -> ret[end] == x[1] || ret[end] == x[2], edges)
push!(ret, ret[end] == edges[i][1] ? edges[i][2] : edges[i][1])
deleteat!(edges, i)
end
return ret[1:end-1]
catch
println("Invalid edges vector: $evec")
exit(1)
end
end
const faces1 = [
[[8, 1, 3], [1, 3, 8]], [[18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18]]
]
const faces2 = [
[(1, 11), (7, 11), (1, 7)], [(11, 23), (1, 17), (17, 23), (1, 11)], [(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)], [(1, 3), (9, 11), (3, 11), (1, 11)]
]
for faces in faces1
println("Faces are ", iseq(faces[1], faces[2]) ? "" : "not ", "equivalent.")
end
for face in faces2
println(toface(face))
end
</lang>
- Output:
Faces are equivalent.
Faces are equivalent.
[1, 11, 7]
[11, 23, 17, 1]
[8, 14, 10, 12, 17, 19, 18]
Invalid edges vector: Tuple{Int64,Int64}[(1, 3), (9, 11), (3, 11), (1, 11)]
Perl
<lang perl>use strict; use warnings; use feature 'say'; use Set::Scalar; use Set::Bag; use Storable qw(dclone);
sub show { my($pts) = @_; my $p='( '; $p .= '(' . join(' ',@$_) . ') ' for @$pts; $p.')' }
sub check_equivalence {
my($a, $b) = @_; Set::Scalar->new(@$a) == Set::Scalar->new(@$b)
}
sub edge_to_periphery {
my $a = dclone \@_;
my $bag_a = Set::Bag->new;
for my $p (@$a) {
$bag_a->insert( @$p[0] => 1);
$bag_a->insert( @$p[1] => 1);
}
2 != @$bag_a{$_} and return 0 for keys %$bag_a;
my $b = shift @$a;
while ($#{$a} > 0) {
for my $k (0..$#{$a}) {
my $v = @$a[$k];
if (@$v[0] == @$b[-1]) {
push @$b, @$v[1];
splice(@$a,$k,1);
last
} elsif (@$v[1] == @$b[-1]) {
push @$b, @$v[0];
splice(@$a,$k,1);
last
}
}
}
@$b;
}
say 'Perimeter format equality checks:'; for ([[8, 1, 3], [1, 3, 8]],
[[18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18]]) {
my($a, $b) = @$_;
say '(' . join(', ', @$a) . ') equivalent to (' . join(', ', @$b) . ')? ',
check_equivalence($a, $b) ? 'True' : 'False';
}
say "\nEdge to perimeter format translations:"; for ([[1, 11], [7, 11], [1, 7]],
[[11, 23], [1, 17], [17, 23], [1, 11]],
[[8, 14], [17, 19], [10, 12], [10, 14], [12, 17], [8, 18], [18, 19]],
[[1, 3], [9, 11], [3, 11], [1, 11]]) {
say show($_) . ' ==> (' . (join ' ', edge_to_periphery(@$_) or 'Invalid edge format') . ')'
}</lang>
- Output:
Perimeter format equality checks: (8, 1, 3) equivalent to (1, 3, 8)? True (18, 8, 14, 10, 12, 17, 19) equivalent to (8, 14, 10, 12, 17, 19, 18)? True Edge to perimeter format translations: ( (1 11) (7 11) (1 7) ) ==> (1 11 7) ( (11 23) (1 17) (17 23) (1 11) ) ==> (11 23 17 1) ( (8 14) (17 19) (10 12) (10 14) (12 17) (8 18) (18 19) ) ==> (8 14 10 12 17 19 18) ( (1 3) (9 11) (3 11) (1 11) ) ==> Invalid edge format
Perl 6
<lang perl6>sub check-equivalence ($a, $b) { so $a.Bag eqv $b.Bag }
sub edge-to-periphery (@a is copy) {
return Nil unless @a.List.Bag.values.all == 2;
my @b = @a.shift.flat;
while @a > 1 {
for @a.kv -> $k, $v {
if $v[0] == @b.tail {
@b.push: $v[1];
@a.splice($k,1);
last
}
elsif $v[1] == @b.tail {
@b.push: $v[0];
@a.splice($k,1);
last
}
}
}
@b
}
say 'Perimeter format equality checks:';
for (8, 1, 3), (1, 3, 8),
(18, 8, 14, 10, 12, 17, 19), (8, 14, 10, 12, 17, 19, 18)
-> $a, $b {
say "({$a.join: ', '}) equivalent to ({$b.join: ', '})? ",
check-equivalence($a, $b)
}
say "\nEdge to perimeter format translations:";
for ((1, 11), (7, 11), (1, 7)),
((11, 23), (1, 17), (17, 23), (1, 11)),
((8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)),
((1, 3), (9, 11), (3, 11), (1, 11))
{
.gist.print;
say " ==> ({.&edge-to-periphery || 'Invalid edge format'})";
}</lang>
- Output:
Perimeter format equality checks: (8, 1, 3) equivalent to (1, 3, 8)? True (18, 8, 14, 10, 12, 17, 19) equivalent to (8, 14, 10, 12, 17, 19, 18)? True Edge to perimeter format translations: ((1 11) (7 11) (1 7)) ==> (1 11 7) ((11 23) (1 17) (17 23) (1 11)) ==> (11 23 17 1) ((8 14) (17 19) (10 12) (10 14) (12 17) (8 18) (18 19)) ==> (8 14 10 12 17 19 18) ((1 3) (9 11) (3 11) (1 11)) ==> (Invalid edge format)
Phix
<lang Phix>function perequiv(sequence a, b) -- Works by aligning and rotating in one step, so theoretically much faster on massive sets. -- (ahem, faster than multiple rotates, index-only loops would obviously be even faster...)
bool res = (length(a)==length(b))
if res and length(a)>0 then
integer k = find(a[1],b)
if k=0 then
res = false
else
-- align with a (ie make b[1]==a[1], by
-- rotating b k places in one operation)
b = b[k..$]&b[1..k-1]
if a!=b then
-- eg {8,3,4,5} <=> {8,5,4,3}, ie
-- rotate *and* keep in alignment.
b[2..$] = reverse(b[2..$])
res = (a==b)
end if
end if
end if
-- return res
return {"false","true"}[res+1]
end function
function edge2peri(sequence edges)
sequence was = edges, res = {}
string error = ""
integer lnk = 0
if length(edges)<2 then
error = "too short"
else
-- edges = sort(edges) -- (see note below)
res = edges[1]
edges = edges[2..$]
lnk = res[2]
while length(edges) and error="" do
bool found = false
for i=1 to length(edges) do
integer k = find(lnk,edges[i])
if k then
lnk = edges[i][3-k]
edges[i..i] = {}
if edges={} then
if lnk!=res[1] then error = "oh dear" end if
else
if find(lnk,res) then error = "oops" end if
res &= lnk
end if
found = true
exit
end if
end for
if not found then error = "bad link" exit end if
end while
end if
if length(error) then res = {error,res,lnk,edges,was} end if
return res
end function
constant ptests = {{{8, 1, 3}, {1, 3, 8}},
{{18, 8, 14, 10, 12, 17, 19}, {8, 14, 10, 12, 17, 19, 18}},
-- (check our results below against Go etc)
{{1,11,7},{1,7,11}},
{{11,23,17,1},{1,11,23,17}}}
for i=1 to length(ptests) do
sequence {p,q} = ptests[i]
printf(1,"%v equivalent to %v: %s\n",{p,q,perequiv(p,q)})
end for
constant etests = {{{1, 11}, {7, 11}, {1, 7}},
{{11, 23}, {1, 17}, {17, 23}, {1, 11}},
{{8, 14}, {17, 19}, {10, 12}, {10, 14}, {12, 17}, {8, 18}, {18, 19}},
{{1, 3}, {9, 11}, {3, 11}, {1, 11}}}
for i=1 to length(etests) do
printf(1,"%v\n",{edge2peri(etests[i])})
end for</lang>
- Output:
(second part matches Julia/Perl: un-comment that sort above to match Go/Python/zkl)
{8,1,3} equivalent to {1,3,8}: true
{18,8,14,10,12,17,19} equivalent to {8,14,10,12,17,19,18}: true
{1,11,7} equivalent to {1,7,11}: true
{11,23,17,1} equivalent to {1,11,23,17}: true
{1,11,7}
{11,23,17,1}
{8,14,10,12,17,19,18}
{"bad link",{1,3,11,9},9,{{1,11}},{{1,3},{9,11},{3,11},{1,11}}}
Python
<lang python>def perim_equal(p1, p2):
# Cheap tests first
if len(p1) != len(p2) or set(p1) != set(p2):
return False
if any(p2 == (p1[n:] + p1[:n]) for n in range(len(p1))):
return True
p2 = p2[::-1] # not inplace
return any(p2 == (p1[n:] + p1[:n]) for n in range(len(p1)))
def edge_to_periphery(e):
edges = sorted(e)
p = list(edges.pop(0)) if edges else []
last = p[-1] if p else None
while edges:
for n, (i, j) in enumerate(edges):
if i == last:
p.append(j)
last = j
edges.pop(n)
break
elif j == last:
p.append(i)
last = i
edges.pop(n)
break
else:
#raise ValueError(f'Invalid edge format: {e}')
return ">>>Error! Invalid edge format<<<"
return p[:-1]
if __name__ == '__main__':
print('Perimeter format equality checks:')
for eq_check in [
{ 'Q': (8, 1, 3),
'R': (1, 3, 8)},
{ 'U': (18, 8, 14, 10, 12, 17, 19),
'V': (8, 14, 10, 12, 17, 19, 18)} ]:
(n1, p1), (n2, p2) = eq_check.items()
eq = '==' if perim_equal(p1, p2) else '!='
print(' ', n1, eq, n2)
print('\nEdge to perimeter format translations:')
edge_d = {
'E': {(1, 11), (7, 11), (1, 7)},
'F': {(11, 23), (1, 17), (17, 23), (1, 11)},
'G': {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)},
'H': {(1, 3), (9, 11), (3, 11), (1, 11)}
}
for name, edges in edge_d.items():
print(f" {name}: {edges}\n -> {edge_to_periphery(edges)}")</lang>
- Output:
Perimeter format equality checks:
Q == R
U == V
Edge to perimeter format translations:
E: {(7, 11), (1, 11), (1, 7)}
-> [1, 7, 11]
F: {(11, 23), (1, 11), (1, 17), (17, 23)}
-> [1, 11, 23, 17]
G: {(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)}
-> [8, 14, 10, 12, 17, 19, 18]
H: {(1, 11), (9, 11), (1, 3), (3, 11)}
-> >>>Error! Invalid edge format<<<
zkl
<lang zkl>fcn perimSame(p1, p2){
if(p1.len() != p2.len()) return(False);
False == p1.filter1('wrap(p){ (not p2.holds(p)) })
}
fcn edge_to_periphery(faces){
edges:=faces.copy().sort(fcn(a,b){ if(a[0]!=b[0]) a[0]<b[0] else a[1]<b[1] });
p,last := ( if(edges) edges.pop(0).copy() else T ), ( p and p[-1] or Void );
while(edges){
foreach i,j in (edges){
if (i==last){ p.append( last=j ); edges.del(__iWalker.idx); break; }
else if(j==last){ p.append( last=i ); edges.del(__iWalker.idx); break; }
}
fallthrough{ return(">>>Error! Invalid edge format<<<") }
}
p[0,-1] // last element not part of result
}</lang> <lang zkl>println("Perimeter format equality checks:"); ps:=T( T( T(8,1,3), T(1,3,8) ),
T( T(18, 8, 14, 10, 12, 17, 19), T(8, 14, 10, 12, 17, 19, 18) ) );
foreach p1,p2 in (ps)
{ println(pp(p1), " equivalent to ", pp(p2), "? ", perimSame(p1,p2)) }
println("\nEdge to perimeter format translations:"); edge_d:=T(
T(T( 1, 11), T( 7, 11), T( 1, 7) ),
T(T(11, 23), T( 1, 17), T(17, 23), T( 1, 11) ),
T(T( 8, 14), T(17, 19), T(10, 12), T(10, 14), T(12, 17), T(8, 18), T(18, 19) ),
T(T( 1, 3), T( 9, 11), T( 3, 11), T( 1, 11) ),
);
foreach edges in (edge_d)
{ println(ppp(edges), " --> ", edge_to_periphery(edges)) }
fcn pp(a){ a.concat(", ","(",")") } fcn ppp(edges){ pp(edges.apply(pp)) }</lang>
- Output:
Perimeter format equality checks: (8, 1, 3) equivalent to (1, 3, 8)? True (18, 8, 14, 10, 12, 17, 19) equivalent to (8, 14, 10, 12, 17, 19, 18)? True Edge to perimeter format translations: ((1 11), (7 11), (1 7)) --> L(1,7,11) ((11 23), (1 17), (17 23), (1 11)) --> L(1,11,23,17) ((8 14), (17 19), (10 12), (10 14), (12 17), (8 18), (18 19)) --> L(8,14,10,12,17,19,18) ((1 3), (9 11), (3 11), (1 11)) --> >>>Error! Invalid edge format<<<