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