2 views (last 30 days)

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

Stephen Cobeldick
on 3 Dec 2019

Edited: Stephen Cobeldick
on 3 Dec 2019

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

Stephen Cobeldick
on 3 Dec 2019

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

Sign in to comment.

John D'Errico
on 3 Dec 2019

Edited: John D'Errico
on 3 Dec 2019

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...

- Start at point #10, the lowest in y.
- Find points 7 and 10, the two extremal points in terms of angle, relative to the pivot point, #10.
- 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.
- 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.
- 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.

Image Analyst
on 3 Dec 2019

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

Matt J
on 3 Dec 2019

We know from here,

that using convhull is not allowed.

Image Analyst
on 3 Dec 2019

Sign in to comment.

Matt J
on 3 Dec 2019

Edited: Matt J
on 3 Dec 2019

Matt J
on 3 Dec 2019

Sign in to comment.

The Merchant
on 3 Dec 2019

Image Analyst
on 3 Dec 2019

Have you seen the various algorithms in Wikipedia:

and

Sign in to comment.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 2 Comments

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/494591-2d-convex-hull-i-can-t-think-of-a-criteria-to-filter-out-the-wrong-points-please-help#comment_773978

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/494591-2d-convex-hull-i-can-t-think-of-a-criteria-to-filter-out-the-wrong-points-please-help#comment_773978

## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/494591-2d-convex-hull-i-can-t-think-of-a-criteria-to-filter-out-the-wrong-points-please-help#comment_774358

⋮## Direct link to this comment

https://ch.mathworks.com/matlabcentral/answers/494591-2d-convex-hull-i-can-t-think-of-a-criteria-to-filter-out-the-wrong-points-please-help#comment_774358

Sign in to comment.