Jump to content

Faces from a mesh

From Rosetta Code
Task
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 to 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.

11l

Translation of: Python
F perim_equal(p1, =p2)
   I p1.len != p2.len | Set(p1) != Set(p2)
      R 0B
   I any((0 .< p1.len).map(n -> @p2 == (@p1[n ..] [+] @p1[0 .< n])))
      R 1B
   p2 = reversed(p2)
   R any((0 .< p1.len).map(n -> @p2 == (@p1[n ..] [+] @p1[0 .< n])))

F edge_to_periphery(e)
   V edges = sorted(e)
   [Int] p
   I !edges.empty
      p = [edges[0][0], edges[0][1]]
      edges.pop(0)
   V last = I !p.empty {p.last} E -1
   L !edges.empty
      L(ij) edges
         V (i, j) = ij
         I i == last
            p.append(j)
            last = j
            edges.pop(L.index)
            L.break
         E I j == last
            p.append(i)
            last = i
            edges.pop(L.index)
            L.break
      L.was_no_break
         R ‘>>>Error! Invalid edge format<<<’
   R String(p[0 .< (len)-1])

print(‘Perimeter format equality checks:’)
L(eq_check) [(‘Q’, [8, 1, 3],
              ‘R’, [1, 3, 8]),
             (‘U’, [18, 8, 14, 10, 12, 17, 19],
              ‘V’, [8, 14, 10, 12, 17, 19, 18])]
   V (n1, p1, n2, p2) = eq_check
   V eq = I perim_equal(p1, p2) {‘==’} E ‘!=’
   print(‘  ’n1‘ ’eq‘ ’n2)

print("\nEdge to perimeter format translations:")
V 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)]]
L(name, edges) edge_d
   print(‘  ’name‘: ’edges"\n     -> "edge_to_periphery(edges))
Output:
Perimeter format equality checks:
  Q == R
  U == V

Edge to perimeter format translations:
  E: [(1, 11), (7, 11), (1, 7)]
     -> [1, 7, 11]
  F: [(11, 23), (1, 17), (17, 23), (1, 11)]
     -> [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, 3), (9, 11), (3, 11), (1, 11)]
     -> >>>Error! Invalid edge format<<<

C++ 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

typedef std::pair<int32_t, int32_t> Edge;

std::string to_string(const int32_t& value) {
	return std::to_string(value);
}

std::string to_string(const Edge& edge) {
	return "(" + std::to_string(edge.first) + ", " + std::to_string(edge.second) + ")";
}

template <typename T>
std::string vector_to_string(const std::vector<T>& list) {
	std::string result = "[";
	for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
		result += to_string(list[i]) + ", ";
	}
	result += to_string(list.back()) + "]";
	return result;
}

bool is_same_face(const std::vector<int32_t>& list_1, const std::vector<int32_t>& list_2) {
	if ( list_1.size() != list_2.size() || list_1.empty() ) {
		return false;
	}

	std::vector<int32_t> copy_2(list_2);
	for ( int32_t i = 0; i < 2; ++i ) {
		int32_t start;
		if ( auto iterator = std::find(copy_2.begin(), copy_2.end(), list_1.front()); iterator != copy_2.end() ) {
			start = std::distance(copy_2.begin(), iterator);
		} else {
			return false;
		}
		std::vector<int32_t> test(copy_2.begin() + start, copy_2.end());
		test.insert(test.end(), copy_2.begin(), copy_2.begin() + start);//addAll(copyTwo.subList(0, start));
		if ( list_1 == test ) {
			return true;
		}
		std::reverse(copy_2.begin(), copy_2.end());
	}

	return false;
}

std::vector<int32_t> to_perimeter_format_face(const std::vector<Edge>& edge_format_face) {
	if ( edge_format_face.empty() ) {
		return std::vector<int32_t>();
	}

	std::vector<Edge> edges(edge_format_face);
	std::vector<int32_t> result;
	Edge first_edge = edges.front();
	edges.erase(edges.begin());
	int next_vertex = first_edge.first;
	result.push_back(next_vertex);

	while ( ! edges.empty() ) {
		int32_t index = -1;
		for ( Edge edge : edges ) {
			if ( edge.first == next_vertex || edge.second == next_vertex ) {
				if ( auto iterator = std::find(edges.begin(), edges.end(), edge); iterator != edges.end() ) {
					index = std::distance(edges.begin(), iterator);
				}
				next_vertex = ( next_vertex == edge.first ) ? edge.second : edge.first;
				break;
			}
		}
		if ( index == -1 ) {
			return std::vector<int32_t>();
		}
		result.push_back(next_vertex);
		edges.erase(edges.begin() + index);
	}

	if ( next_vertex != first_edge.second ) {
		return std::vector<int32_t>();
	}
	return result;
}

int main() {
	const std::vector<int32_t> perimeter_format_q = { 8, 1, 3 };
	const std::vector<int32_t> perimeter_format_r = { 1, 3, 8 };
	const std::vector<int32_t> perimeter_format_u = { 18, 8, 14, 10, 12, 17, 19 };
	const std::vector<int32_t> perimeter_format_v = { 8, 14, 10, 12, 17, 19, 18 };

	const std::vector<Edge> edge_format_e = { Edge(1, 11), Edge(7, 11), Edge(1, 7) };
	const std::vector<Edge> edge_format_f = { Edge(11, 23), Edge(1, 17), Edge(17, 23), Edge(1, 11) };
	const std::vector<Edge> edge_format_g =
		{ Edge(8, 14), Edge(17, 19), Edge(10, 12), Edge(10, 14), Edge(12, 17), Edge(8, 18), Edge(18, 19) };
	const std::vector<Edge> edge_format_h = { Edge(1, 3), Edge(9, 11), Edge(3, 11), Edge(1, 11) };

	std::cout << "PerimeterFormat equality checks:" << std::endl;
	bool same_face = is_same_face(perimeter_format_q, perimeter_format_r);
	std::cout << vector_to_string(perimeter_format_q) << " == "
			  << vector_to_string(perimeter_format_r) << ": " << std::boolalpha << same_face << std::endl;
	same_face = is_same_face(perimeter_format_u, perimeter_format_v);
	std::cout << vector_to_string(perimeter_format_u) << " == "
			  << vector_to_string(perimeter_format_v) << ": " << std::boolalpha << same_face << std::endl;

	std::cout << "\nEdgeFormat to PerimeterFormat conversions:" << std::endl;
	std::vector<std::vector<Edge>> edge_format_faces = { edge_format_e, edge_format_f, edge_format_g, edge_format_h };
	for ( std::vector<Edge> edge_format_face : edge_format_faces ) {
		std::vector<int32_t> perimeter_format_face = to_perimeter_format_face(edge_format_face);
		if ( perimeter_format_face.empty() ) {
			std::cout << vector_to_string(edge_format_face) << " has invalid edge format" << std::endl;
		} else {
			std::cout << vector_to_string(edge_format_face) << " => "
					  << vector_to_string(perimeter_format_face) << std::endl;
		}
	}
}
Output:
PerimeterFormat equality checks:
[8, 1, 3] == [1, 3, 8]: true
[18, 8, 14, 10, 12, 17, 19] == [8, 14, 10, 12, 17, 19, 18]: true

EdgeFormat to PerimeterFormat conversions:
[(1, 11), (7, 11), (1, 7)] => [1, 7, 11]
[(11, 23), (1, 17), (17, 23), (1, 11)] => [11, 1, 17, 23]
[(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)] => [8, 18, 19, 17, 12, 10, 14]
[(1, 3), (9, 11), (3, 11), (1, 11)] has invalid edge format

FreeBASIC

Translation of: Go
' Check if a dynamic array contains a value
Function contains(s() As Integer, f As Integer) As Boolean
    For i As Integer = 0 To Ubound(s)
        If s(i) = f Then Return True
    Next
    Return False
End Function

' Check if two dynamic arrays are equal
Function sliceEqual(s1() As Integer, s2() As Integer) As Boolean
    If Ubound(s1) <> Ubound(s2) Then Return False
    
    For i As Integer = 0 To Ubound(s1)
        If s1(i) <> s2(i) Then Return False
    Next
    Return True
End Function

' Reverse a dynamic array in place
Sub reverse(s() As Integer)
    Dim As Integer i, j
    For i = 0 To (Ubound(s) + 1) \ 2 - 1
        j = Ubound(s) - i
        Swap s(i), s(j)
    Next
End Sub

' Check if two perimeters are equal
Function perimEqual(p1() As Integer, p2() As Integer) As Boolean
    Dim As Integer le = Ubound(p1) + 1
    If le <> Ubound(p2) + 1 Then Return False
    
    Dim As Integer i, r, t, j
    For i = 0 To Ubound(p1)
        If Not contains(p2(), p1(i)) Then Return False
    Next
    
    Dim As Integer c(Ubound(p1))
    For i = 0 To Ubound(p1)
        c(i) = p1(i)
    Next
    
    For r = 0 To 1
        For i = 0 To le - 1
            If sliceEqual(c(), p2()) Then Return True
            
            ' Circular shift to right
            t = c(le - 1)
            For j = le - 1 To 1 Step -1
                c(j) = c(j - 1)
            Next
            c(0) = t
        Next
        reverse(c())
    Next
    
    Return False
End Function

Type edge
    e(0 To 1) As Integer
End Type

' Translate a face to perimeter format
Function faceToPerim(face() As edge) As Integer Ptr
    Dim As Integer le = Ubound(face) + 1
    If le = 0 Then Return 0
    
    Dim edges(0 To le - 1) As edge
    Dim As Integer i, j
    For i = 0 To le - 1
        If face(i).e(1) <= face(i).e(0) Then Return 0
        edges(i) = face(i)
    Next
    
    ' Sort edges (bubble sort for simplicity)
    For i = 0 To le - 2
        For j = 0 To le - 2 - i
            If edges(j).e(0) > edges(j + 1).e(0) Or _
            (edges(j).e(0) = edges(j + 1).e(0) And _
            edges(j).e(1) > edges(j + 1).e(1)) Then
                Dim As edge temp = edges(j)
                edges(j) = edges(j + 1)
                edges(j + 1) = temp
            End If
        Next
    Next
    
    Dim As Integer Ptr perim = Callocate((le + 1) * Sizeof(Integer))
    Dim As Integer perimCount = 0, first = edges(0).e(0), last = edges(0).e(1)
    
    perim[perimCount] = first : perimCount += 1
    perim[perimCount] = last : perimCount += 1
    
    le -= 1
    For i = 0 To le - 1
        edges(i) = edges(i + 1)
    Next
    
    Do While le > 0
        Dim As Boolean found = False
        For i = 0 To le - 1
            If edges(i).e(0) = last Then
                perim[perimCount] = edges(i).e(1) : perimCount += 1
                last = edges(i).e(1)
                found = True
            Elseif edges(i).e(1) = last Then
                perim[perimCount] = edges(i).e(0) : perimCount += 1
                last = edges(i).e(0)
                found = True
            End If
            
            If found Then
                For j = i To le - 2
                    edges(j) = edges(j + 1)
                Next
                le -= 1
                If last = first Then
                    If le = 0 Then
                        ' Remove the last element (which is equal to the first)
                        perimCount -= 1
                        ' Terminate the array with a -1
                        perim[perimCount] = -1
                        Return perim
                    Else
                        Deallocate(perim)
                        Return 0
                    End If
                End If
                Exit For
            End If
        Next
        If Not found Then
            Deallocate(perim)
            Return 0
        End If
    Loop
    
    ' Terminate the array with a -1
    perim[perimCount] = -1
    Return perim
End Function

'Main program
Print "Perimeter format equality checks:"

Dim As Integer q(2) = {8, 1, 3}
Dim As Integer r(2) = {1, 3, 8}
Dim As Boolean areEqual = perimEqual(q(), r())
Print "  Q == R is "; areEqual

Dim As Integer u(6) = {18, 8, 14, 10, 12, 17, 19}
Dim As Integer v(6) = {8, 14, 10, 12, 17, 19, 18}
areEqual = perimEqual(u(), v())
Print "  U == V is "; areEqual

Print !"\nEdge to perimeter format translations:"

Dim As edge e(0 To 2)
e(0).e(0) = 7 : e(0).e(1) = 11
e(1).e(0) = 1 : e(1).e(1) = 11
e(2).e(0) = 1 : e(2).e(1) = 7

Dim As edge f(0 To 3)
f(0).e(0) = 11 : f(0).e(1) = 23
f(1).e(0) = 1  : f(1).e(1) = 17
f(2).e(0) = 17 : f(2).e(1) = 23
f(3).e(0) = 1  : f(3).e(1) = 11

Dim As edge g(0 To 6)
g(0).e(0) = 8  : g(0).e(1) = 14
g(1).e(0) = 17 : g(1).e(1) = 19
g(2).e(0) = 10 : g(2).e(1) = 12
g(3).e(0) = 10 : g(3).e(1) = 14
g(4).e(0) = 12 : g(4).e(1) = 17
g(5).e(0) = 8  : g(5).e(1) = 18
g(6).e(0) = 18 : g(6).e(1) = 19

Dim As edge h(0 To 3)
h(0).e(0) = 1 : h(0).e(1) = 3
h(1).e(0) = 9 : h(1).e(1) = 11
h(2).e(0) = 3 : h(2).e(1) = 11
h(3).e(0) = 1 : h(3).e(1) = 11

Dim As Integer Ptr perim
Dim As edge Ptr faces(3) = {@e(0), @f(0), @g(0), @h(0)}
Dim As Integer faceSizes(3) = {3, 4, 7, 4}

Dim As Integer i, j
For i = 0 To 3
    Redim As edge face(0 To faceSizes(i) - 1)
    For j = 0 To faceSizes(i) - 1
        face(j) = faces(i)[j]
    Next
    
    perim = faceToPerim(face())
    
    If perim = 0 Then
        Print "  "; Chr(69 + i); " => Invalid edge format"
    Else
        Print "  "; Chr(69 + i); " =>";
        j = 0
        While perim[j] <> -1
            Print perim[j];
            If perim[j + 1] <> -1 Then Print ",";
            j += 1
        Wend
        Print
        Deallocate(perim)
    End If
Next

Sleep
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

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

Haskell 

import Data.List (find, delete, (\\))
import Control.Applicative ((<|>))

------------------------------------------------------------

newtype Perimeter a = Perimeter [a]
  deriving Show

instance Eq a => Eq (Perimeter a) where
  Perimeter p1 == Perimeter p2 =
    null (p1 \\ p2)
    && ((p1 `elem` zipWith const (iterate rotate p2) p1)
        || Perimeter p1 == Perimeter (reverse p2))

rotate lst = zipWith const (tail (cycle lst)) lst

toEdges :: Ord a => Perimeter a -> Maybe (Edges a)
toEdges (Perimeter ps)
  | allDifferent ps = Just . Edges $ zipWith ord ps (tail (cycle ps))
  | otherwise = Nothing
  where
    ord a b = if a < b then (a, b) else (b, a)

allDifferent [] = True
allDifferent (x:xs) = all (x /=) xs && allDifferent xs

------------------------------------------------------------

newtype Edges a = Edges [(a, a)]
  deriving Show

instance Eq a => Eq (Edges a) where
  e1 == e2 = toPerimeter e1 == toPerimeter e2

toPerimeter :: Eq a => Edges a -> Maybe (Perimeter a)
toPerimeter (Edges ((a, b):es)) = Perimeter . (a :) <$> go b es
  where
    go x rs
      | x == a = return []
      | otherwise = do
          p <- find ((x ==) . fst) rs <|> find ((x ==) . snd) rs
          let next = if fst p == x then snd p else fst p
          (x :) <$> go next (delete p rs)

First task. 

λ> Perimeter [8,1,3] == Perimeter [1,3,8]
True

λ> Perimeter [8,1,3] == Perimeter [1,8,3]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19,18]
True

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,19]
False

λ> Perimeter [18,8,14,10,12,17,19] == Perimeter [8,14,10,12,17,18,19]
False

Second task 

λ> toPerimeter (Edges [(1,11),(7,11),(1,7)])
Just (Perimeter [1,11,7])

λ> toPerimeter (Edges [(11,23),(1,17),(17,23),(1,11)])
Just (Perimeter [11,23,17,1])

λ> toPerimeter (Edges [(8,14),(17,19),(10,12),(10,14),(12,17),(8,18),(18,19)])
Just (Perimeter [8,14,10,12,17,19,18])

λ> toPerimeter (Edges [(1,3),(9,11),(3,11),(1,11)])
Nothing

J

First task: 

   NB. construct a list of all rotations of one of the faces
   NB. including all rotations of the reversed list.
   NB. Find out if the other face is a member of this list.

   NB. ,&:rotations -> append, but first enlist the rotations.


   rotations=. |."0 1~ i.@#
   reverse=: |.
   same_perimeter=: e. (,&:rotations reverse)

   (3, 1, 8)same_perimeter(8, 1, 3)
1

   (18, 8, 14, 10, 12, 17, 19)same_perimeter(8, 14, 10, 12, 17, 19, 18)
1

Secondly: 

edge_to_node=: 3 :0
 assert. 2 = #/.~ , y [ 'expect each node to appear twice'
 oel=. 1 2 {. y
 Y=. }. y
 while. # Y do.
  i =. <. -: 1 i.~ , Y (e."1) {: oel
  assert. 0 < # i [ 'isolated edge detected'
  oel =. oel , i { Y
  Y =. i ({. , (}.~ >:)~) Y
 end.
 ~. , oel
)

   boxdraw_j_ 0

   ]TESTS=: ([: < _2 ]\ ".);._2'{}'-.~0 :0
{(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)}
)
┌────┬─────┬─────┬────┐
│1 11│11 23│ 8 14│1  3│
│7 11│ 1 17│17 19│9 11│
│1  7│17 23│10 12│3 11│
│    │ 1 11│10 14│1 11│
│    │     │12 17│    │
│    │     │ 8 18│    │
│    │     │18 19│    │
└────┴─────┴─────┴────┘



   edge_to_node ::('failure'"_)&.> TESTS
┌──────┬──────────┬───────────────────┬───────┐
│1 11 7│11 23 17 1│8 14 10 12 17 19 18│failure│
└──────┴──────────┴───────────────────┴───────┘


   edge_to_node _1 {:: TESTS
|assertion failure: edge_to_node
|       2=#/.~,y['expect each node to appear twice'

Java 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

public final class FacesFromMesh {

	public static void main(String[] aArgs) {
		final List<Integer> perimeterFormatQ = Arrays.asList( 8, 1, 3 );
		final List<Integer> perimeterFormatR = Arrays.asList( 1, 3, 8 );
		final List<Integer> perimeterFormatU = Arrays.asList( 18, 8, 14, 10, 12, 17, 19 );
		final List<Integer> perimeterFormatV = Arrays.asList( 8, 14, 10, 12, 17, 19, 18 );
		
		final List<Edge> edgeFormatE = Arrays.asList( new Edge(1, 11), new Edge(7, 11), new Edge(1, 7) );	
		final List<Edge> edgeFormatF =
			Arrays.asList( new Edge(11, 23), new Edge(1, 17), new Edge(17, 23), new Edge(1, 11) );
		final List<Edge> edgeFormatG = Arrays.asList( new Edge(8, 14), new Edge(17, 19),
			new Edge(10, 12), new Edge(10, 14), new Edge(12, 17), new Edge(8, 18), new Edge(18, 19) );
		final List<Edge> edgeFormatH = 
			Arrays.asList( new Edge(1, 3), new Edge(9, 11), new Edge(3, 11), new Edge(1, 11) );		
		
		System.out.println("PerimeterFormat equality checks:");
		boolean sameFace = isSameFace(perimeterFormatQ, perimeterFormatR);
		System.out.println(perimeterFormatQ + " == " + perimeterFormatR + ": " + sameFace);
		sameFace = isSameFace(perimeterFormatU, perimeterFormatV);
		System.out.println(perimeterFormatU + " == " + perimeterFormatV + ": " + sameFace);

		System.out.println(System.lineSeparator() + "EdgeFormat to PerimeterFormat conversions:");
		List<List<Edge>> edgeFormatFaces = List.of( edgeFormatE, edgeFormatF, edgeFormatG, edgeFormatH ); 
		for ( List<Edge> edgeFormatFace : edgeFormatFaces ) {
			List<Integer> perimeterFormatFace = toPerimeterFormatFace(edgeFormatFace);
		    if ( perimeterFormatFace.isEmpty() ) {
		    	System.out.println(edgeFormatFace + " has invalid edge format");
		    } else {
		        System.out.println(edgeFormatFace + " => " + perimeterFormatFace);
		    }
		}
	}
	
	private static boolean isSameFace(List<Integer> aOne, List<Integer> aTwo) {
		if ( aOne.size() != aTwo.size() || aOne.isEmpty() ||
			! new HashSet<Integer>(aOne).equals( new HashSet<Integer>(aTwo) )) {
			return false;
		}

		List<Integer> copyTwo = new ArrayList<Integer>(aTwo);
		for ( int i = 0; i < 2; i++ ) {
			int start = copyTwo.indexOf(aOne.get(0));
			List<Integer> test = new ArrayList<Integer>(copyTwo.subList(start, copyTwo.size()));
			test.addAll(copyTwo.subList(0, start));
			if ( aOne.equals(test) ) {
			    return true;
			}
			Collections.reverse(copyTwo);
		}	
		return false;
	}
	
	private static List<Integer> toPerimeterFormatFace(List<Edge> aEdgeFormatFace) {
		if ( aEdgeFormatFace.isEmpty() ) {
			return Collections.emptyList();
		}		
		
		List<Edge> edges = new ArrayList<Edge>(aEdgeFormatFace);
		List<Integer> result = new ArrayList<Integer>();
		Edge firstEdge = edges.remove(0);
		int nextVertex = firstEdge.first;
		result.add(nextVertex);
		
		while ( ! edges.isEmpty() ) {
			int index = -1;
			for ( Edge edge : edges ) {
				if ( edge.first == nextVertex || edge.second == nextVertex ) {
			        index = edges.indexOf(edge);
			        nextVertex = ( nextVertex == edge.first ) ? edge.second : edge.first;
			        break;
				}
			}			
			if ( index == -1 ) {
				return Collections.emptyList();
			}
			result.add(nextVertex);
			edges.remove(index);
		}
		
		if ( nextVertex != firstEdge.second ) {
		    return Collections.emptyList();
		}		
		return result;
	}
	
	private static class Edge {
		
		public Edge(int aFirst, int aSecond) {
			first = aFirst;
			second = aSecond;
		}
		
		@Override
		public String toString() {
			return "(" + first + ", " + second + ")";
		}
		
		private int first, second;
		
	}

}
Output:
PerimeterFormat equality checks:
[8, 1, 3] == [1, 3, 8]: true
[18, 8, 14, 10, 12, 17, 19] == [8, 14, 10, 12, 17, 19, 18]: true

EdgeFormat to PerimeterFormat conversions:
[(1, 11), (7, 11), (1, 7)] => [1, 7, 11]
[(11, 23), (1, 17), (17, 23), (1, 11)] => [11, 1, 17, 23]
[(8, 14), (17, 19), (10, 12), (10, 14), (12, 17), (8, 18), (18, 19)] => [8, 18, 19, 17, 12, 10, 14]
[(1, 3), (9, 11), (3, 11), (1, 11)] has invalid edge format

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

Koka 

alias perimeter = list<int>
alias face = (char, perimeter)
alias edge = (int, int)

fun isSame(p1: perimeter, p2: perimeter, noSwitch: list<int> = []): div bool
  match (p1, p2)
    ([], []) -> True
    (Cons(x1, xs1), Cons(x2, xs2)) | x1 == x2 -> isSame(xs1, xs2)
    _ -> 
      match p2
        Nil -> False
        Cons(x2, xs2) -> 
          if noSwitch.any(fn(x') x' == x2) then False else p1.isSame(xs2 ++ [x2], Cons(x2, noSwitch))

fun show(f: face)
  val (c, p) = f
  c.core/show ++ " " ++ p.core/show

fun findRemove(l: list<a>, acc: ctx<list<a>>, pred: (a) -> bool): maybe<(a, list<a>)>
  match l
    [] -> Nothing
    Cons(x, xs) -> match pred(x)
      True -> Just((x, acc ++. xs))
      False -> findRemove(xs, acc ++ ctx Cons(x, _), pred)

fun toPerimeter(search: int, edges: list<edge>, acc: ctx<perimeter>): <div,exn> perimeter
  match edges
    [] -> acc ++. Cons(search, Nil) // Assume the search matches the first edge's missing
    _ -> match edges.findRemove(ctx _, fn((a, b)) a == search || b == search)
      Just(((a, b), xs')) -> if search == a then 
          toPerimeter(b, xs', acc ++ ctx Cons(a, _))
        else 
          toPerimeter(a, xs', acc ++ ctx Cons(b, _))
      Nothing -> throw("Cannot find the next edge for " ++ search.show ++ " current perimeter is " ++ (acc ++. Nil).show ++ " and the rest of the edges are: " ++ edges.show-list(fn(s) s.show-tuple(show, show)))

fun main()
  val fp = [(('P', [8, 1, 3]), ('R', [1, 3, 8])), 
            (('U', [18, 8, 14, 10, 12, 17, 19]), ('V', [8, 14, 10, 12, 17, 19, 18]))]
  fp.foreach() fn((f1, f2))
    val same = f1.snd.isSame(f2.snd)
    print(f1.show ++ (if same then " is " else " is not ") ++ "the same as " ++ f2.show ++ "\n")
  val fe = [('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)])]
  fe.foreach() fn((f, edges))
    match edges
      [] -> ()
      Cons((initX, _), edges') ->
        val p = toPerimeter(initX, edges', ctx _)
        print(f.show ++ " perimeter is " ++ p.show ++ "\n")
Output:
'P' [8,1,3] is the same as 'R' [1,3,8]
'U' [18,8,14,10,12,17,19] is the same as 'V' [8,14,10,12,17,19,18]
'E' perimeter is [1,7,11]
'F' perimeter is [11,1,17,23]
'G' perimeter is [8,18,19,17,12,10,14]
uncaught exception: Cannot find the next edge for 9 current perimeter is [1,11] and the rest of the edges are: [(3,11)]

Lua 

-- support
function T(t) return setmetatable(t, {__index=table}) end
table.eql = function(t,u) if #t~=#u then return false end for i=1,#t do if t[i]~=u[i] then return false end end return true end
table.rol = function(t,n) local s=T{} for i=1,#t do s[i]=t[(i+n-1)%#t+1] end return s end
table.rev = function(t) local s=T{} for i=1,#t do s[#t-i+1]=t[i] end return s end

-- 1
function pfeq(pf1, pf2)
  if #pf1 ~= #pf2 then return false end -- easy case
  for w = 0,1 do -- exhaustive cases
    local pfw = pf1 -- w:winding
    if w==1 then pfw=pfw:rev() end
    for r = 0,#pfw do
      local pfr = pfw -- r:rotate
      if r>0 then pfr=pfr:rol(r) end
      if pf2:eql(pfr) then return true end
    end
  end
  return false
end

Q = T{8, 1, 3}
R = T{1, 3, 8}
U = T{18, 8, 14, 10, 12, 17, 19}
V = T{8, 14, 10, 12, 17, 19, 18}
print("pfeq(Q,R): ", pfeq(Q, R))
print("pfeq(U,V): ", pfeq(U, V))

-- 2
function ef2pf(ef)
  local pf, hse = T{}, T{} -- hse:hash of sorted edges
  for i,e in ipairs(ef) do table.sort(e) hse[e]=e end
  local function nexte(e)
    if not e then return ef[1] end
    for k,v in pairs(hse) do
      if e[2]==v[1] then return v end
      if e[2]==v[2] then v[1],v[2]=v[2],v[1] return v end
    end
  end
  local e = nexte()
  while e do
    pf[#pf+1] = e[1]
    hse[e] = nil
    e = nexte(e)
  end  
  if #pf ~= #ef then pf=T{"failed to convert edge format to perimeter format"} end
  return pf
end

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}}
print("ef2pf(E): ", ef2pf(E):concat(","))
print("ef2pf(F): ", ef2pf(F):concat(","))
print("ef2pf(G): ", ef2pf(G):concat(","))
print("ef2pf(H): ", ef2pf(H):concat(","))
Output:
pfeq(Q,R):      true
pfeq(U,V):      true
ef2pf(E):       1,11,7
ef2pf(F):       11,23,17,1
ef2pf(G):       8,14,10,12,17,19,18
ef2pf(H):       failed to convert edge format to perimeter format

Nim 

import algorithm, strutils

type
  Perimeter = seq[int]
  Face = tuple[name: char; perimeter: Perimeter]
  Edge = tuple[first, last: int]

const None = -1   # No point.

#---------------------------------------------------------------------------------------------------

func isSame(p1, p2: Perimeter): bool =
  ## Return "true" if "p1" and "p2" represent the same face.

  if p1.len != p2.len: return false

  for p in p1:
    if p notin p2: return false

  var start = p2.find(p1[0])
  if p1 == p2[start..^1] & p2[0..<start]:
    return true

  let p3 = reversed(p2)
  start = p3.find(p1[0])
  if p1 == p3[start..^1] & p3[0..<start]:
    return true

#---------------------------------------------------------------------------------------------------

func `$`(perimeter: Perimeter): string =
  ## Convert a perimeter to a string.
  '(' & perimeter.join(", ") & ')'

func `$`(face: Face): string =
  ## Convert a perimeter formatted face to a string.
  face.name & $face.perimeter

#---------------------------------------------------------------------------------------------------

func toPerimeter(edges: seq[Edge]): Perimeter =
  ## Convert a list of edges to perimeter representation.
  ## Return an empty perimeter if the list of edges doesn’t represent a face.

  var edges = edges
  let firstEdge = edges.pop()       # First edge taken in account.
  var nextPoint = firstEdge.first   # Next point to search in remaining edges.
  result.add(nextpoint)

  while edges.len > 0:
    # Search an edge.
    var idx = None
    for i, e in edges:
      if e.first == nextPoint or e.last == nextPoint:
        idx = i
        nextPoint = if nextpoint == e.first: e.last else: e.first
        break
    if idx == None:
      return @[]      # No edge found containing "newPoint".

    # Add next point to perimeter and remove the edge.
    result.add(nextPoint)
    edges.del(idx)

  # Check that last added point is the expected one.
  if nextPoint != firstEdge.last:
    return @[]

#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:

  # List of pairs of perimeter formatted faces to compare.
  const FP = [(('P', @[8, 1, 3]), ('R', @[1, 3, 8])),
              (('U', @[18, 8, 14, 10, 12, 17, 19]), ('V', @[8, 14, 10, 12, 17, 19, 18]))]

  echo "Perimeter comparison:"
  for (p1, p2) in FP:
    echo p1, if isSame(p1[1], p2[1]): " is same as " else: "is not same as", p2

  # List of edge formatted faces.
  const FE = {'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)]}

  echo ""
  echo "Conversion from edge to perimeter format:"
  for (faceName, edges) in FE:
    let perimeter = edges.toPerimeter()
    echo faceName, ": ", if perimeter.len == 0: "Invalid edge list" else: $perimeter
Output:
Perimeter comparison:
P(8, 1, 3) is same as R(1, 3, 8)
U(18, 8, 14, 10, 12, 17, 19) is same as V(8, 14, 10, 12, 17, 19, 18)

Conversion from edge to perimeter format:
E: (1, 11, 7)
F: (1, 17, 23, 11)
G: (18, 8, 14, 10, 12, 17, 19)
H: Invalid edge list

Perl

Translation of: Raku
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') . ')'
}
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 

with javascript_semantics
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(deep_copy(edges)) -- (see note below)
        res = deep_copy(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
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 

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)}")
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<<<

Raku

(formerly Perl 6)

Works with: Rakudo version 2019.11
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'})";
}
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)

Wren

Translation of: Go
Library: Wren-sort
Library: Wren-seq
Library: Wren-fmt
import "./sort" for Sort
import "./seq" for Lst
import "./fmt" for Fmt
 
// Check two perimeters are equal.
var perimEqual = Fn.new { |p1, p2|
    var le = p1.count
    if (le != p2.count) return false
    for (p in p1) {
        if (!p2.contains(p)) return false
    }
    // use copy to avoid mutating 'p1'
    var c = p1.toList
    for (r in 0..1) {
        for (i in 0...le) {
            if (Lst.areEqual(c, p2)) return true
            // do circular shift to right
            Lst.rshift(c)
        }
        // now process in opposite direction
        Lst.reverse(c) // reverses 'c' in place
    }
    return false
}
 
var faceToPerim = Fn.new { |face|
    // use copy to avoid mutating 'face'
    var le = face.count
    if (le == 0) return []
    var edges = List.filled(le, null)
    for (i in 0...le) {
        // check edge pairs are in correct order
        if (face[i][1] <= face[i][0]) return []
        edges[i] = [face[i][0], face[i][1]]
    }
    // sort edges in ascending order
    var cmp = Fn.new { |e1, e2|
        if (e1[0] != e2[0]) {
            return (e1[0] - e2[0]).sign
        }
        return (e1[1] - e2[1]).sign
    }
    Sort.insertion(edges, cmp)
    var first = edges[0][0]
    var last  = edges[0][1]
    var perim = [first, last]
    // remove first edge
    edges.removeAt(0)
    le = le - 1
    while (le > 0) {
        var i = 0
        var outer = false
        var cont = false
        for (e in edges) {
            var found = false
            if (e[0] == last) {
                perim.add(e[1])
                last = e[1]
                found = true
            } else if (e[1] == last) {
                perim.add(e[0])
                last = e[0]  
                found = true
            }
            if (found) {
                // remove i'th edge
                edges.removeAt(i)
                le = le - 1
                if (last == first) {
                    if (le == 0) {
                        outer = true
                        break
                    } else {
                        return []
                    }
                }
                cont = true
                break
            }
            i = i + 1
        }
        if (outer && !cont) break
    }
    return perim[0..-2]
}
 
System.print("Perimeter format equality checks:")
var areEqual = perimEqual.call([8, 1, 3], [1, 3, 8])
System.print("  Q == R is %(areEqual)")
areEqual = perimEqual.call([18, 8, 14, 10, 12, 17, 19], [8, 14, 10, 12, 17, 19, 18])
System.print("  U == V is %(areEqual)")
var e = [[7, 11], [1, 11], [1, 7]]
var f = [[11, 23], [1, 17], [17, 23], [1, 11]]
var g = [[8, 14], [17, 19], [10, 12], [10, 14], [12, 17], [8, 18], [18, 19]]
var h = [[1, 3], [9, 11], [3, 11], [1, 11]]
System.print("\nEdge to perimeter format translations:")
var i = 0
for (face in [e, f, g, h]) {
    var perim = faceToPerim.call(face)
    if (perim.isEmpty) {
        Fmt.print("  $c => Invalid edge format", i + 69) // 'E' is ASCII 69
    } else {
        Fmt.print("  $c => $n", i + 69, perim)
    }
}
Output:
Perimeter format equality checks:
  Q == R is true
  U == V is true

Edge to perimeter format translations:
  E => [1, 7, 11]
  E => [1, 11, 23, 17]
  E => [8, 14, 10, 12, 17, 19, 18]
  E => Invalid edge format

zkl

Translation of: Python
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
}
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)) }
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<<<
Retrieved from "https://rosettacode.org/wiki/Faces_from_a_mesh?oldid=371538"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information