Xjyuk

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>();

 BorderPixels.AddRange(Data);

 List<int> Indexs = new List<int>();
 Indexs.Add(0);

 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])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y + 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X - 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
 Possible.Add(Index);
 else if (new Vector2F(BorderPixels[LastIndex].X + 1, BorderPixels[LastIndex].Y - 1) == BorderPixels[Index])
 Possible.Add(Index);
 
 

 Indexs.Add(GetPreference(BorderPixels[LastIndex], Possible.ToArray(), BorderPixels));

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

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

 for (int Index = 0; Index < Indexs.Count; Index++)
 Vertices.Add(BorderPixels[Indexs[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

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>();

Indexs.Add(0);
indexTest.Add(0);

and

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

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.

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 
 

 int preferredIndex = GetPreference(last, possible.ToArray(), borderPixels);
 indexes.Add(preferredIndex);
 indexTest.Add(preferredIndex);
 

 var vertices = new List<Vector2F>();
 for (int index = 0; index < indexes.Count; index++) 
 vertices.Add(borderPixels[indexes[index]]);
 

 return vertices.ToArray();

You can also apply some of these changes to GetPreference.

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

DRY Principle

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

answer snippet:

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

 Possible.Add(Index);

replaces..

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