# Compute convex hull given the figure type [closed]

Given a set of points in a 2D space, there are gazillions of suggestion on how to compute a convex hull. However, in my assignment, we need to add the information about the figure that's going to be produced. In fact, given the somewhat dull nature of the work, we do know that it's going to be a rectangle, triangle or, if things get wild and crazy, a trapezoid.

The convex hull given that it's rectangle is trivial to compute. One only needs to find the extremes of all the points' x and y. However, when it comes to the triangle, I feel a bit confused. It seems that there's a unique convex hull provided that we're supposed to produce a triangle but I can't shake off the feeling that it's actually an ambiguous concept. It gets even less transparent when it comes to the trapezoid.

1. Is it possible to uniquely determine the convex hull of a set of 2D points given that the resulting figure is a triangle?

2. And if so, how should I approach the problem?

3. Is it possible to uniquely determine the convex hull of a set of 2D points given that the resulting figure is a trapezoid?

4. Is the approach to be similar to triangle case?

There's a suggestion on how to do the triangle part but it has two significant drawbacks. First one being that I don't have access to MatLab (we work with C) and second being that I don't quite follow it, hehe.

## closed as unclear what you're asking by Crostul, iadvd, Daniel W. Farlow, Parcly Taxel, JonMark PerryAug 31 '16 at 8:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

Any of the standard convex hull algorithms will work regardless of the output. If you want to do better than $\Omega(n \log n)$ for situations where the hull has a constant number of points, use an output sensitive algorithm such as Chan's algorithm or the gift wrapping algorithm.
A quick sketch of the gift wrapping algorithm: Start with the leftmost point, then successively add points $p_{i+1}$ such that the all points are to the right of the line $p_ip_{i+1}$.