EDIT :
I didn't realized that an ordered list of coordinates was required, my original answer was making a non oriented graph around the shape.
I updated the answer to add a function that would build an oriented list from this graph
Considering you're using Unity, I made a very simple algorithm.
Knowing only the coordinates of every vertices that is part of the figure you want to outline, and with the assumption that the distance between them is always the same, I came up with this :
Firstly a very crude way of making the squares :
The assumption is that I the coordinates have no concept of what are their edges, only the four points of each square are given.
For the sake of this example I've done this handcrafting a list of list of vertex.
public void CreateCoords()
{
_squares = new List<List<Vector3>>()
{
new List<Vector3>()
{
new Vector3(0,0,0),
new Vector3(0,0,1),
new Vector3(1,0,0),
new Vector3(1,0,1),
},
new List<Vector3>()
{
new Vector3(0,0,1),
new Vector3(1,0,1),
new Vector3(1,0,2),
new Vector3(0,0,2),
},
new List<Vector3>()
{
new Vector3(1,0,1),
new Vector3(2,0,1),
new Vector3(2,0,2),
new Vector3(1,0,2),
},
new List<Vector3>()
{
new Vector3(2,0,1),
new Vector3(2,0,2),
new Vector3(3,0,1),
new Vector3(3,0,2),
},
new List<Vector3>()
{
new Vector3(2,0,1),
new Vector3(3,0,1),
new Vector3(2,0,0),
new Vector3(3,0,0),
},
new List<Vector3>()
{
new Vector3(4,0,1),
new Vector3(3,0,1),
new Vector3(4,0,0),
new Vector3(3,0,0),
},
new List<Vector3>()
{
new Vector3(1,0,2),
new Vector3(1,0,3),
new Vector3(2,0,2),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,2),
new Vector3(3,0,3),
new Vector3(2,0,2),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,4),
new Vector3(3,0,3),
new Vector3(2,0,4),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(1,0,4),
new Vector3(1,0,3),
new Vector3(2,0,4),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,4),
new Vector3(3,0,5),
new Vector3(2,0,4),
new Vector3(2,0,5),
},
new List<Vector3>()
{
new Vector3(3,0,2),
new Vector3(3,0,3),
new Vector3(4,0,2),
new Vector3(4,0,3),
},
};
}
Here's the result :
Now for the algorithm :
My solution is based on the fact that all edges that are part of the border will only appear once.
It also works on the assumption that the coordinates of the squares are not ordered, the algorithm would be a bit simpler if it was the case.
private void ComputeEdges()
{
// The edges collection is a set of pair of vertex
_edges = new HashSet<KeyValuePair<Vector3, Vector3>>();
foreach (var square in _squares)
{
// Iterate over the coordinates to compute the edges
// Using for loop to skip already processed edges
var squareCount = square.Count;
for (var i = 0; i < squareCount; i++)
{
// The source vertex
var src = square[i];
for (var j = 0; j < squareCount; j++)
{
if (i == j) continue;
// The vertex with whom we want to determine if they form and edge
var dest = square[j];
// Check the distance between them to filter out the diagonal edges
if (!(Math.Abs(Vector3.Distance(src, dest) - edgeDistance) < 0.001)) continue;
var edge = new KeyValuePair<Vector3, Vector3>(src, dest);
// _edges is a set, making it viable to use Contains
// even when the collections contains a lot of elements
if (_edges.Contains(edge))
{
// If the edge already exists in the set,
// it means its not part of the border
_edges.Remove(edge);
}
else
{
_edges.Add(edge);
}
}
}
}
}
Here's a simple Gizmos example that will display the borders.
foreach (var (src, dest) in _edges)
{
Gizmos.DrawLine(src, dest);
}
And here's the final result :
As I understood later that an ordered list of points would be prefered, I made another algorithm that could make one out of the edges collection.
public void BuildList()
{
_coordsList = new List<Vector3>();
// Make a copy of the edges so we can remove items from it
// without destroying the original collection
var copy = new HashSet<KeyValuePair<Vector3, Vector3>>(_edges);
// Add the first pair before starting the loop
var previousEdge = _edges.First();
_coordsList.Add(previousEdge.Key);
_coordsList.Add(previousEdge.Value);
KeyValuePair<Vector3, Vector3> currentEdge;
// While there is an edge that follows the previous one
while (!(currentEdge = copy.FirstOrDefault(pair => pair.Key == previousEdge.Value))
.Equals(default(KeyValuePair<Vector3, Vector3>)))
{
// Our graph is not oriented but we want to ignores edges
// that go back from where we went
if (currentEdge.GetHashCode() == previousEdge.GetHashCode())
{
copy.Remove(currentEdge);
continue;
}
// Add the vertex to the list and continue
_coordsList.Add(currentEdge.Value);
previousEdge = currentEdge;
// Remove traversed nodes
copy.Remove(currentEdge);
}
}
A case might be made about the performance, has my algorithm has first to computes the edges, makes uses of the Vector3.Distance function and frequently uses a Contains() method.
Building the edges iterating over everyone of them using the distance is clearly not optimal performance wise, but I wanted to keep this part simple and I don't think the impact will make it that much different compared to the other algorithm proposed.
As for the Contains() method, keep in mind that it comes from a HashSet, making it of the same complexity as using the indexer operator on a Dictionnary or a List.
For the sake of completeness and ease of use, here's the full class :
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
namespace DrawOuterGraph
{
public class OuterGraph: MonoBehaviour
{
private List<List<Vector3>> _squares;
private HashSet<KeyValuePair<Vector3, Vector3>> _edges;
private List<Vector3> _coordsList;
[SerializeField]
private float edgeDistance = 1;
private void Start()
{
CreateCoords();
ComputeEdges();
BuildList();
}
private void ComputeEdges()
{
// The edges collection is a set of pair of vertex
_edges = new HashSet<KeyValuePair<Vector3, Vector3>>();
foreach (var square in _squares)
{
// Iterate over the coordinates to compute the edges
// Using for loop to skip already processed edges
var squareCount = square.Count;
for (var i = 0; i < squareCount; i++)
{
// The source vertex
var src = square[i];
for (var j = 0; j < squareCount; j++)
{
if (i == j) continue;
// The vertex with whom we want to determine if they form and edge
var dest = square[j];
// Check the distance between them to filter out the diagonal edges
if (!(Math.Abs(Vector3.Distance(src, dest) - edgeDistance) < 0.001)) continue;
var edge = new KeyValuePair<Vector3, Vector3>(src, dest);
// _edges is a set, making it viable to use Contains
// even when the collections contains a lot of elements
if (_edges.Contains(edge))
{
// If the edge already exists in the set,
// it means its not part of the border
_edges.Remove(edge);
}
else
{
_edges.Add(edge);
}
}
}
}
}
public void BuildList()
{
_coordsList = new List<Vector3>();
// Make a copy of the edges so we can remove items from it
// without destroying the original collection
var copy = new HashSet<KeyValuePair<Vector3, Vector3>>(_edges);
// Add the first pair before starting the loop
var previousEdge = _edges.First();
_coordsList.Add(previousEdge.Key);
_coordsList.Add(previousEdge.Value);
KeyValuePair<Vector3, Vector3> currentEdge;
// While there is an edge that follows the previous one
while (!(currentEdge = copy.FirstOrDefault(pair => pair.Key == previousEdge.Value))
.Equals(default(KeyValuePair<Vector3, Vector3>)))
{
// Our graph is not oriented but we want to ignores edges
// that go back from where we went
if (currentEdge.GetHashCode() == previousEdge.GetHashCode())
{
copy.Remove(currentEdge);
continue;
}
// Add the vertex to the list and continue
_coordsList.Add(currentEdge.Value);
previousEdge = currentEdge;
// Remove traversed nodes
copy.Remove(currentEdge);
}
}
public void CreateCoords()
{
_squares = new List<List<Vector3>>()
{
new List<Vector3>()
{
new Vector3(0,0,1),
new Vector3(1,0,0),
new Vector3(0,0,0),
new Vector3(1,0,1),
},
new List<Vector3>()
{
new Vector3(0,0,1),
new Vector3(1,0,1),
new Vector3(1,0,2),
new Vector3(0,0,2),
},
new List<Vector3>()
{
new Vector3(1,0,1),
new Vector3(2,0,1),
new Vector3(2,0,2),
new Vector3(1,0,2),
},
new List<Vector3>()
{
new Vector3(2,0,1),
new Vector3(2,0,2),
new Vector3(3,0,1),
new Vector3(3,0,2),
},
new List<Vector3>()
{
new Vector3(2,0,1),
new Vector3(3,0,1),
new Vector3(2,0,0),
new Vector3(3,0,0),
},
new List<Vector3>()
{
new Vector3(4,0,1),
new Vector3(3,0,1),
new Vector3(4,0,0),
new Vector3(3,0,0),
},
new List<Vector3>()
{
new Vector3(1,0,2),
new Vector3(1,0,3),
new Vector3(2,0,2),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,2),
new Vector3(3,0,3),
new Vector3(2,0,2),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,4),
new Vector3(3,0,3),
new Vector3(2,0,4),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(1,0,4),
new Vector3(1,0,3),
new Vector3(2,0,4),
new Vector3(2,0,3),
},
new List<Vector3>()
{
new Vector3(3,0,4),
new Vector3(3,0,5),
new Vector3(2,0,4),
new Vector3(2,0,5),
},
new List<Vector3>()
{
new Vector3(3,0,2),
new Vector3(3,0,3),
new Vector3(4,0,2),
new Vector3(4,0,3),
},
};
}
private void OnDrawGizmos()
{
// Draw using the edges
if (_edges is not null)
{
foreach (var (src, dest) in _edges)
{
Gizmos.DrawLine(src, dest);
}
}
// Draw using the ordered list
if (_coordsList is null || _coordsList.Count == 0) return;
var previous = _coordsList[0];
foreach (var current in _coordsList)
{
Gizmos.DrawLine(previous, current);
previous = current;
}
}
}
}
