How to filter the points to get only the left most and right most?

[tommy_chai]

Hi all,
Kindly need your attention here.
Let say,

n = 0;  // number of corner points detected
if (......)
{
corner_list[n].x = j;  //x coordinate
corner_list[n].y = i;  //y coordinate
n++;
:
:
}

"m7.pgm"-->attached
This is the image and the marking at the contour are the detected points.
"m-004-1.pgm"-->attached
I want to get only the left most and right most points as corner. How can i write the codes to keep only these 2 corner points for every image?
From the left side, we can see there are two points with the same x-coordinate. From the right there are 3 or 4 points at the same x-coordinate.
How can we program to choose the most middle position for the left most and right most corner points?

Please help or give some ideas.
Thank you.

Best regards,
Tommy

[JohnW@Wessex]

Sort the coordinates by y coordinate and choose the middle one in the list?

[tommy_chai]

Do you mind to show me? I have just started my C programming few days ago.

Thanks.

[JohnW@Wessex]

My suggestion was assuming that you had already extracted the positions on the left or right with the same x coordinate.

If not then you could do the following..

Sort the entire coordinate array by x coordinate.
This will put the left most points at one end of the array and the right most points at the other end.
You could then step through from each end to find how many are at the same x coordinate.
Then you would need to sort each of these sections by y coordinate.
The middle points should be the points half way along these sorted sections.
You could make it a little easier by extracting these ranges from the whole array first before you sort again.

If you are restricted to programming in C then your only real option is to use the library function qsort (short for quicksort)

This can be a bit complicated for novice C programmer as it involves pointers to structures and functions.

Here is some information on qsort

Basically qsort takes the following parameters.

1. A pointer to the start of the range you wish to sort.
2. The number of items you wish to sort.
3. The size in bytes of each item (Use sizeof)
4. A pointer to a function that will compare two items, returning -1 for 'less than' 0 for 'equal to' and 1 for 'greater than'

In your case you would want two such functions, one that compares the x coordinates and another that compares the y.

struct Coordinate
{
	int x;
	int y;
};

int Compare_X(void *first, void *second)
{
	Coordinate *coord1 = (struct Coordinate *) first;
	Coordinate *coord2 = (struct Coordinate *) second;

	if (coord1.x < coord2.x)
   {
		return -1;
	}
	else if (coord1.x > coord2.x)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

[Lindley]

There's no reason to do two separate sorts just to sort by first x, then y. Simply modify the comparison function as such:

int Compare_X(void *first, void *second)
{
	Coordinate *coord1 = (struct Coordinate *) first;
	Coordinate *coord2 = (struct Coordinate *) second;

	if (coord1.x < coord2.x)
        {
		return -1;
	}
	else if (coord1.x > coord2.x)
	{
		return 1;
	}
        else if (coord1.y < coord2.y)
        {
		return -1;
	}
	else if (coord1.y > coord2.y)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

[tommy_chai]

Thanks for helping. If I am not mistaken, only the selected x-coordinate will be kept into corner_list[n].x but i need the same correspoding y coordinate also . This is because the detected points, x and y will be saved if they meet the condition if() in a loop as shown in my 1st post.
So, in order to filter it, if x1 has been chosen, continuously y1 needs to be saved too.
Unless when there are a few left most or right most points with the same x-position. In this case i need to choose the one which is the nearest to 40. This is because the height of my image is 80 and i have tried and prove a better result by using this term to elimane the left most or right most points with the same x-position.
Can you guys please try to relate to my 1st program so it is easier for a dummy like me to understand. Anyway, good codes and i can understand it.
Please kindly give me a helping hand. Thank you.

[JohnW@Wessex]

If I am not mistaken, only the selected x-coordinate will be kept into corner_list[n].x but i need the same correspoding y coordinate also.

Your coordinates are obviously in a structure of some sort so the x & y values will stay together. corner_list[n] will always contain a pair of coordinates. When you say something like corner_list[1] = corner_list[0]; you are copying the entire contents of the structure.

Sort the array of coordinates.

int corner_list_size = <something>;

qsort(&corner_list[0], corner_list_size, sizeof(corner_list[0]), &Compare_X);

For the left hand side, step through the corner_list from index zero and find the number of corner_list elements with the same x coordinate.

int initial_x = corner_list[0].x;
int count = 1;

for (int i = 1; (i < corner_list_size) && (corner_list[i].x == initial_x); ++i)
{
	++count;
}

Now step through these elements and find the one with the y coordinate closest to 40.

struct Coordinate = left_corner;
left_corner.x = 0;
left_corner.y = 0;

for (int i = 0; i < count; ++i)
{
	if (abs(corner_list[i].y - 40) < abs(left_corner.y - 40))
	{
		left_corner = corner_list[i];
	}
}

Now do something similar for the right hand side, which will be at the other end of the array. (Or sort in reverse order using a different compare function and repeat the above method)

abs is a standard library function that returns the absolute value (turns negative numbers into positive)

There is plenty of room for optimisation but the first thing is to get the algorithm correct.

[tommy_chai]

Thanks for giving me such a good example to learn. After some studies and modifications, i have already solved my problems using C programming.

Thank you very much.

best regards,
Tommy