2D Convex Hull: I can't think of a 'criteria' to filter out the 'wrong' points, please help!

I can't think of a 'criteria' to filter out the 'wrong' points. I've been stuck for 5+ hours now with this assignment, but haven't gotten any further.

The goal is to create a convex hull from a cloud of points; a shape that contains all points and consists of the least points possible.

If you take the highest point of the cloud above and the three points to its right, what criteria can be setup to make it so that it chooses to eliminate the first and second point to the right, but keep the third point to the right, since this point we can easily see, should be on the convex hull.

That is what I'm struggling with... I can clearly see it visually, but I have no clue how to put this into code...

Updates on current code:

clear;
close all;
clc;

list = [
3 12 % 1
10 8 % 2
11 14 % 3
13 16 % 4
9 19 % 5
1 15 % 6
2 4 % 7
6 1 % 8
11 3 % 9
16 5 % 10
14 17 % 11
19 18 % 12
]

lowY = find(list==1, 1, "last") - length(list);

lowCoords = list(lowY,:);

rowValue = 1;

listAtan = [];
    
while rowValue < 13
    coords = lowCoords - list(rowValue,:);
    
    atan = atan2(coords(:,2),coords(:,1));
    listAtan = [listAtan, atan];
    
    rowValue = rowValue + 1;
end

listAtan = listAtan

[Matt J]

See also,

https://www.mathworks.com/matlabcentral/answers/494379-cloud-of-points-convex-hull

[Stephen Cobeldick]

Original question (before this one gets deleted too):

I can't think of a 'criteria' to filter out the 'wrong' points. I've been stuck for 5+ hours now with this assignment, but haven't gotten any further.

The goal is to create a convex hull from a cloud of points; a shape that contains all points and consists of the least points possible.

If you take the highest point of the cloud above and the three points to its right, what criteria can be setup to make it so that it chooses to eliminate the first and second point to the right, but keep the third point to the right, since this point we can easily see, should be on the convex hull.

That is what I'm struggling with... I can clearly see it visually, but I have no clue how to put this into code...

Updates on current code:

clear;
close all;
clc;
list = [
3 12 % 1
10 8 % 2
11 14 % 3
13 16 % 4
9 19 % 5
1 15 % 6
2 4 % 7
6 1 % 8
11 3 % 9
16 5 % 10
14 17 % 11
19 18 % 12
]
lowY = find(list==1, 1, "last") - length(list);
lowCoords = list(lowY,:);
rowValue = 1;
listAtan = [];
    
while rowValue < 13
    coords = lowCoords - list(rowValue,:);
    
    atan = atan2(coords(:,2),coords(:,1));
    listAtan = [listAtan, atan];
    
    rowValue = rowValue + 1;
end
listAtan = listAtan

Answer 1

[Stephen Cobeldick]

"I can't think of a 'criteria' to filter out the 'wrong' points."

The obvious criteria to pick is in the name convex hull: why is it called a convex hull? (hint: the 'right' points have convex angles).

You can easily calculate the angles at each of those points (use the law of cosines, or subtract vectors, or similar), and exclude those points where the boundary is concave. Note that your algorithm will also need to check the starting point somehow (unless you can guarantee that it is not situated on a concave point).

[The Merchant]

Thanks,

I don't get why this criteria is based on angles, sorry it might be really dumb of me..

But can you explain why it is based on angles, I need to make this assigment for tonight..

[Stephen Cobeldick]

"But can you explain why it is based on angles..."

A convex hull has no concave angles by definition of a convex hull.

Look at the angles in the diagram shown in part 2 of your assignment:

• which points do you want to keep? (hint: the convex ones)
• which points do you want to ignore? (hint the concave ones)

Answer 2

[John D'Errico]

It does not seem you have done anything at all. Write some code. Get started. Play with it. Find a way to overcome the problems. Instead, it looks like you are trying to devise the entire algorithm in your head. That can work. But if you can't get your head around it, where are you going?

Start with point #8, arbitrarily the lowest point in y. This would be a problem possibly if there were multiple colllinear points, all with the same (minimal) value of y. But that is a problem to worry about on your next assignment.

Given point #8, compute the angles of every other point as directed. (Why have you not done this already? WRITE THE CODE!) You will get a list of angles that vary from 0 to pi radians, or 0-180 degrees, if you used atan2d.

Sorting them on the angle atan2 will generate, you will find two extremal points in that list, #7 and #10.

(If you don't understand why this works, then TRY IT!!!!!!!!! Look at the points. What are the angles that result? THINK ABOUT IT! Look at the numbers. WRITE SOME CODE!)

At this point, I can think of several ways to proceed. You might just work in a clockwise direction around the entire set, picking the single point with the smallest angle to act as a new pivot point. Eventually, you will return to point #8, and you are done.

Or, you could work in a clockwise manner, going from point #8 to points 7, 6, 5, 12, etc.

But that does not reduce the set, making it more efficient as you go. So a simple scheme that does do so is...

1. Start at point #10, the lowest in y.
2. Find points 7 and 10, the two extremal points in terms of angle, relative to the pivot point, #10.
3. Consider the values y(7), y(10). Any other data points that have a LOWER value of y than min(y(7),y(10)) can now be discarded. You never need to look at them again, as they cannot be part of the convex hull.
4. Next choose to work either to the right, or to the left, depending on which is smaller - the point in the clockwise or counter clockwise direction. At each step you will extend the perimeter on the side with the smaller v value.
5. Continue until both sides of the convex hull have reached the point with the maximal value of y.

In practice, the result will be...

Start at #8

New vertices 7 and 10 are found. We see that y(7) < y(10). Drop point 9 from further consideration, because y(9) is less than y(7).

Extend the hull in a clockwise direction to point #6, so the two ends we now have are points #6 and #10. y(10) is now the lower of the two, so are any points remaining in the set lower than y(10)? No, so just extend the edge on the right to point #12.

Our current pair of end points are now #6 and #12, the lower of which is y(6). This allows us to drop out points #1,#2, #3 from further consideration.

Again, working from point #6, we will find that #5 is next, the point with the highest angle relative to point #6. Once we drop points 4 and 11 from the set, we are effectively done.

There are surely other ways you could write it. But the above scheme will work simply, reducing the set of points that need be considered at each step.

You will need to learn to use indexing to do all of the above efficiently. But it can surely be done without much difficulty. A 2-d convex hull is a pretty easy thing to compute. You could make it more robust, thinking about what to do if there are multiple collinear points that lie along the convex hull. What if there is not a unique minimal value in y? A unique maximal y value?

It is your homework assignment. Start writing. Don't worry about making it perfect at first. Get it into code, then make the code better once it works.

[The Merchant]

@John D'Errico

Extend the hull in a clockwise direction to point #6

Why go to 6? Point 1 is the next in line right? I'm not sure how to have the code determine to skip one or did you make a mistake?

[The Merchant]

Again, working from point #6, we will find that #5 is next

How will I find this? I literally have no clue.

Answer 3

[Image Analyst]

Can you use the built-in convhull()? If so, you can get the indexes of those on the convex hull:

x = rand(1, 20);
y = rand(1, 20);
plot(x, y, 'b+', 'MarkerSize', 10, 'LineWidth', 2);
grid on;
indexesOnHull = convhull(x, y);
% Get (x,y) of those points on the hull and put a circle around them.
xOnHull = x(indexesOnHull);
yOnHull = y(indexesOnHull);
hold on;
plot(xOnHull, yOnHull, 'bo', 'MarkerSize', 10, 'LineWidth', 2);
% Get (x,y) of those points NOT on the hull and put a x through them.
indexesNotOnHull = 1 : length(x); % Initialize to everything.
indexesNotOnHull(indexesOnHull) = []; % Remove those on the hull.
xNotOnHull = x(indexesNotOnHull);
yNotOnHull = y(indexesNotOnHull);
hold on;
plot(xNotOnHull, yNotOnHull, 'rx', 'MarkerSize', 10, 'LineWidth', 2);

[The Merchant]

Thank you for the effort!

However, unfortunately I am not allowed to use this function, but have to create my own function, which makes this assignment quite hard..

Sorry, but still thanks for the effort!

[Matt J]

We know from here,

https://www.mathworks.com/matlabcentral/answers/494379-cloud-of-points-convex-hull#comment_773570

that using convhull is not allowed.

[Image Analyst]

No problem. I'll add the tag homework so other people will know to give only hints and not a full solution, which could be a problem if your teacher found out.

[The Merchant]

Alright, I just seek guidance, I don't need the final answer, but a small code example could help me out alot, so I could see what you were doing, since making things up from text is really hard. And I think I would have bigger problem if my teacher found out than you'd have :P

Answer 4

[Matt J]

One thing you can also try to do is find where one of the rays from the pivot point lies inside the triangle formed by its two neighboring rays. You know that such a point can be eliminated as a non-vertex and you can show (an exercise for you) that there will always exist at least one such point that can be found and eliminated, until you've narrowed the set down to the polygon vertices only. For example, in the figure below, it would be fairly easy to show that ray R8,1 lies inside the triangle formed by rays R8,7 and R8,6 and therefore point 1 is a non-vertex that can be discarded.

[The Merchant]

Thank you!

Not sure how to do this, but I will do my best.

[The Merchant]

Also only have about 4 more hours to solve this :(

[Matt J]

Alright, well I'm willing to give one further hint. You know that the 2 neighboring rays R8,7 and R8,6 are linearly independent and therefore the ray in between them R8,1 can be written as a linear combination of the other two. What special form must that linear combination have in order for R8,1 ito lie inside the triangle formed by the other two rays?

Answer 5

[The Merchant]

This is what I've come up with so far:

clear;
close all;
clc;

list = [
3 12 % 1
10 8 % 2
11 14 % 3
13 16 % 4
9 19 % 5
1 15 % 6
2 4 % 7
6 1 % 8
11 3 % 9
16 5 % 10
14 17 % 11
19 18 % 12
]

lowY = find(list==1, 1, "last") - length(list);

lowCoords = list(lowY,:);

rowValue = 1;

listAtan = [];
    
while rowValue < 13
    coords = lowCoords - list(rowValue,:);
    
    atan = atan2(coords(:,2),coords(:,1));
    listAtan = [listAtan, atan];
    
    rowValue = rowValue + 1;
end

listAtan = listAtan

[Image Analyst]

Have you seen the various algorithms in Wikipedia:

https://en.wikipedia.org/wiki/Convex_hull

and

https://en.wikipedia.org/wiki/Convex_hull_algorithms