# Ordering 2D Border Points

What i am trying to do

I have an image of a polygon exemple:

what i am tring to do is getting all border points, that do not have at least one neighbour with the same color, and ordering them in a way that later i can draw lines

The Code

private Vector2F[] ReorderBorder(Vector2F[] Data) {

List<Vector2F> BorderPixels = new List<Vector2F>();

List<int> Indexs = new List<int>();

bool Working = true;

while (Working)
{

int LastIndex = Indexs.Last();

List<int> Possible = new List<int>();

for (int Index = 0; Index < BorderPixels.Count; Index++)
{

if (!Indexs.Contains(Index))
{

if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
}
}

if (BorderPixels.Count == Indexs.Count)
Working = false;
}

List<Vector2F> Vertices = new List<Vector2F>();

for (int Index = 0; Index < Indexs.Count; Index++)

return Vertices.ToArray();
}

private int GetPreference(Vector2F Origin, int[] Indices, List<Vector2F> BorderPixels) {

if (Indices.Length == 1)
return Indices[0];

Vector2F[] IndicesTest = new Vector2F[Indices.Length];

///Relativity
/// 0 - Up
/// 1 - Up Right
/// 2 - Right
/// 3 - Down Right
/// 4 - Down
/// 5 - Down Left
/// 6 - Left
/// 7 - Up Left
for (int Index = 0; Index < Indices.Length; Index++) {

if(new Vector2F(Origin.X, Origin.Y - 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 0);
else if(new Vector2F(Origin.X + 1, Origin.Y - 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 1);
else if (new Vector2F(Origin.X + 1, Origin.Y) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 2);
else if (new Vector2F(Origin.X + 1, Origin.Y + 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 3);
else if (new Vector2F(Origin.X, Origin.Y + 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 4);
else if (new Vector2F(Origin.X - 1, Origin.Y + 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 5);
else if (new Vector2F(Origin.X - 1, Origin.Y) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 6);
else if (new Vector2F(Origin.X - 1, Origin.Y - 1) == BorderPixels[Indices[Index]])
IndicesTest[Index] = new Vector2F(Indices[Index], 7);
}

if (IndicesTest.Length != 0) {

Array.Sort(IndicesTest, CompareY);
return (int)IndicesTest[0].X;
}

return 0;
}

private int CompareY(Vector2F Left, Vector2F Right) {

if (Left.Y < Right.Y)
return -1;
else if (Left.Y == Right.Y)
return 0;
else
return 1;
}


What it does

private Vector2F[] ReorderBorder(Vector2F[] Data)


This is the main function where i pass the border points, currently orderd by y so 0,0 1,0 2,0 0,1 1,1 etc..

so what it does is starting from the first pixel it get all existing border pixels in 8 directions and add the "preferenced" pixel (see GetPreference function) then after finishing ordering all pixels it sends a orderd array back

private int GetPreference(Vector2F Origin, int[] Indices, List<Vector2F> BorderPixels)


this functions recives a point and a list of possible neighbours then it returns the index of the perfed one (lowest score see code)

private int CompareY(Vector2F Left, Vector2F Right)


this function is simply used to sort by the lowest y, for the score on the GetPreference function

What i want to know

All i want to know is if there is any way to optmized the code, or a better alternative, i know that the code as some bugs but this is the most reliable way i could do, since i was not able to find any good alternative online

• All green points seem to have at least one neighbour with the same color and all transparent points seem to have at least one neighbour being transparent. So, according to your definition there are no points in the result set. Your working example draws black lines that are not on a border. I'm a bit confused. – Olivier Jacot-Descombes Aug 29 at 22:50
• @OlivierJacot-Descombes first i dont know what you mean with green points the exemple is yellow second getting the points from the image is not in question, i have everything working i just want to know if the reorganization of the points can be optimized, and final in the exemple we have yellow so the way i get points is if a points is yellow see if any of the neighbours is transparent if yes then add to the border list if does not then do not add and in the point in question is transperent completely ignore – Bot Wade Aug 29 at 22:55
• Looking at HTML color codes and names I would say the color is very close to Tea Green. – Olivier Jacot-Descombes Aug 29 at 23:21
• @OlivierJacot-Descombes look that as nothing to do with the question so unless you have anything constructive to say please stop comenting – Bot Wade Aug 29 at 23:23
• @BotWade: don't be rude to people trying to help. The second picture, titled "working exemple", doesn't make much sense. The border lines are all over the place. I suggest you either update or remove the picture. Also, arguing over colors is unnecessary. Ever heard of colorblindness? – TomG Aug 29 at 23:33

You are making the test !Indexs.Contains(Index). Since Indexs is a List<int> you have a look up time of O(n). A HashSet<T> has an approximate look up time of O(1). Create a hash set for this test. Since a set is not ordered, you still need the list.

var Indexs = new List<int>();
var indexTest = new HashSet<int>();



and

int i = GetPreference(BorderPixels[LastIndex], Possible.ToArray(), BorderPixels);


and of course now test with

if (!indexTest.Contains(Index))

• Another point is the repeated indexed access of border pixels. Store the pixels in a temp. This also makes the code more readable.

• You can merge all the if-statements into one conditional expression. Because of the Short-Circuit Evaluation In C#, the evaluation will stop at the first term evaluating to true.

• You have duplicated some cases. You have 12 instead of 8. Reordering the conditions in a logical way makes it easier: x-1, x, x+1 combined with y-1, y, y+1.

• The Boolean temp Working can be inlined.

• You can initialize collections in the constructor or with collection initializers.

• The C# naming conventions use camelCase for parameter names and local variables.

• Since neither data nor borderPixels are altered, copying data into borderPixels seems superfluous. I simply renamed data to borderPixels. This change requires the type of the last parameter of GetPreference to be changed from List<Vector2F> to Vector2F[] and borderPixels.Count must be changed to borderPixels.Length.

• If you change the type of the corresponding parameter in GetPreference, the conversion of the possible list to array is not necessary. Since the collection is not altered in GetPreference, we don't need to make this copy. Note that IList<T> is compatible to List<T> as well as to T[].

The new ReorderBorder method:

private Vector2F[] ReorderBorder(Vector2F[] borderPixels)
{
var indexes = new List<int> { 0 };
var indexTest = new HashSet<int> { 0 };

while (indexes.Count < borderPixels.Length) {
int lastIndex = indexes.Last();
Vector2F last = borderPixels[lastIndex];

var possible = new List<int>();
for (int index = 0; index < borderPixels.Length; index++) {
if (!indexTest.Contains(index)) {
Vector2F current = borderPixels[index];
if (new Vector2F(last.X - 1, last.Y - 1) == current ||
new Vector2F(last.X - 1, last.Y) == current ||
new Vector2F(last.X - 1, last.Y + 1) == current ||
new Vector2F(last.X, last.Y - 1) == current ||
new Vector2F(last.X, last.Y + 1) == current ||
new Vector2F(last.X + 1, last.Y - 1) == current ||
new Vector2F(last.X + 1, last.Y) == current ||
new Vector2F(last.X + 1, last.Y + 1) == current)
{
}
}
}

int preferredIndex = GetPreference(last, possible, borderPixels);
}

var vertices = new List<Vector2F>();
for (int index = 0; index < indexes.Count; index++) {
}

return vertices.ToArray();
}


Now, to the GetPreference method.

• We can apply the C# naming conventions.

• If we change the type of the inidces and borderPixels parameters to IList<T>, we will be able to pass arrays or lists. The caller gains some flexibility.

• The indicesTest array must store two integers but is of Vector2F[] type based on float. We could use a ValueTuple (since C# 7.0) here. If you don't want this, at least use a vector type based on int. I will be using an array of (int index, int relativity). I rename it to relativeIndices.

• Instead of describing the relativity numbers in a comment, we can make them constants. This eliminates Magic numbers.

• We can store the double index lookup borderPixels[Indices[Index]] in temps.

private int GetPreference(Vector2F origin, IList<int> indices, IList<Vector2F> borderPixels)
{
/* Relativity */  const int Up = 0, UpRight = 1, Right = 2, DownRight = 3,
Down = 4, DownLeft = 5, Left = 6, UpLeft = 7;

if (indices.Count == 1) return indices[0];

var relativeIndices = new (int index, int relativity)[indices.Count];
for (int index = 0; index < indices.Count; index++) {
int pixelIndex = indices[index];
Vector2F pixel = borderPixels[pixelIndex];
if (new Vector2F(origin.X, origin.Y - 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: Up);
else if (new Vector2F(origin.X + 1, origin.Y - 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: UpRight);
else if (new Vector2F(origin.X + 1, origin.Y) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: Right);
else if (new Vector2F(origin.X + 1, origin.Y + 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: DownRight);
else if (new Vector2F(origin.X, origin.Y + 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: Down);
else if (new Vector2F(origin.X - 1, origin.Y + 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: DownLeft);
else if (new Vector2F(origin.X - 1, origin.Y) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: Left);
else if (new Vector2F(origin.X - 1, origin.Y - 1) == pixel)
relativeIndices[index] = (index: pixelIndex, relativity: UpLeft);
}

if (relativeIndices.Length > 0) {
Array.Sort(relativeIndices, CompareRelativity);
return relativeIndices[0].index;
}
return 0;
}

• We must adapt the CompareY method to the new type of the array. I rename it to CompareRelativity and flatten the if-statements. There is no need for else-statements, since we return.
private int CompareRelativity(
(int index, int relativity) left,
(int index, int relativity) right)
{
if (left.relativity < right.relativity) return -1;
if (left.relativity == right.relativity) return 0;
return 1;
}


I did not question the algorithm. Since your now deleted picture shows borders all over the place, a simple sorting might not be the right approach for finding the preferred pixel.

## DRY Principle

As a small addendum on Olivier Jacot-Descombes' answer, I would like to add you should go for DRY code.

"You have duplicated some cases. You have 12 instead of 8. Reordering the conditions in a logical way makes it easier: x-1, x, x+1 combined with y-1, y, y+1."

This..

var current = BorderPixels[Index];
var last = BorderPixels[LastIndex];
if (Math.Abs(current.X - last.X) <= 1 && Math.Abs(current.Y - last.Y) <= 1)
{
}


replaces..

if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])

• @Olivier Jacot-Descombes It doesn't matter, my point is how to refactor that redundant part to DRY code. If the original code was incorrect, my rewrite would also be. – dfhwze Aug 31 at 15:28

Use enums When in the below snippet each index really means what the numbers stand for in the comments then you definitely need at least an enum for that. This is so extremely fragile. Without these comments nobody ever would be able to decipher this logic.

///Relativity
/// 0 - Up
/// 1 - Up Right
/// 2 - Right
/// 3 - Down Right
/// 4 - Down
/// 5 - Down Left
/// 6 - Left
/// 7 - Up Left
for (int Index = 0; Index < Indices.Length; Index++)