2
$\begingroup$

I was given some points to calculate the convex hull. So when I try to find that on internet I also saw that a question which has asked what is the difference of convex hull and convex polygon. According to my knowledge convex hull is the set of points in convex set and polygon is the representation of them in 2D plane. (PLEASE CORRECT ME IF IM WRONG)

However my given points are below and how I tried do calculate convex hull is given below.

Points

$P1=(1,1) , P2=(2,2)$ , $P3=(1.5,3)$ , $P4=(2.5,5)$ , $P5=(3,4)$, $P6=(3,2)$ , $P7=(5,4)$ , $P8=(6,2)$ , $P9=(4,1)$

Tried way

By plotting them in 2D space and going to each point, tried to draw lines to each remaining points and tried to find the internal angle less than 180 while being the largest one among other angles.

Problem

I'm not 100% sure that my method is correct. So if someone can please tell me how to find the convex hull by hand (not with programs) and tell me the difference between convex hull and polygon (if my interpretation is wrong).

Thank you

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The convex hull of a subset $S$ of the plane is the smallest convex set that contains all of them. If $S$ is finite, this is a convex polygon whose vertices form some subset of $S$.

In your case, the points look like

enter image description here

Start from, say, the highest point $P_4$, which must be one of the vertices of the convex hull (it wouldn't be in the convex hull of lower points). Think of a line through $P_4$ that starts out horizontal and pivots clockwise. The first point it hits will be $P_7$, so that's the next point of your polygon.

enter image description here

Draw the line segment $P_4, P_7$. This will be an edge of your polygon. Now pivot the line, still clockwise, around $P_7$. The next point it hits will be $P_8$.

enter image description here

Draw the segment $P_7, P_8$, and continue in this way until you come back to $P_4$. And there's your convex hull.

enter image description here

$\endgroup$
2
  • $\begingroup$ Thanks alot for images and great clarification. So convex polygon is the representation and hull is the smallest set that has every point in it? Is that right? Also is there any wrong with the way I explained in question? Thank you $\endgroup$
    – Samitha Nanayakkara
    Oct 27, 2016 at 18:43
  • $\begingroup$ A convex polygon is a polygon that is a convex set. The convex hull is the smallest convex set that has all your points in it. $\endgroup$
    – Robert Israel
    Oct 27, 2016 at 20:28
2
$\begingroup$

Start with a line parallel to the $x$ axis and far enough up so that all the points are below it. Then imagine that line dropping until it touches one (or maybe more) of the points. That will be the "highest" point $P=P4$. Now pivot that line around $P$ until it meets another point, say $Q$. Then $PQ$ is one of the edges of the polygon that is the boundary of the convex hull. Now pivot around $Q$ to find the next point $R$, and so on until you get back to $P$.

If I had time I'd draw the picture. Maybe someone will edit this and to that. In any case you should.

$\endgroup$
6
  • $\begingroup$ Thank you. Before more questions about that could you please tell me what I described about convex hull and polygon is right or wrong? $\endgroup$
    – Samitha Nanayakkara
    Oct 27, 2016 at 18:30
  • 1
    $\begingroup$ This is called the Gift Wrapping Algorithm in the literature. There's a nice illustration on the page of an algorithm running, but Ethan's method of doing this by hand is just fine. As for the difference between "Convex Hull" and "Convex Polygon": A convex hull is a type of convex polygon, but we usually refer to "hulls" when we work with a set of points and "polygon" when we work with the shape per-se. $\endgroup$
    – Larry B.
    Oct 27, 2016 at 18:32
  • 1
    $\begingroup$ The polygon is the boundary of the convex hull. Both are sets of points in the plane. $\endgroup$
    – Ethan Bolker
    Oct 27, 2016 at 18:32
  • $\begingroup$ Thanks alot. But can you explain it a little bit more? What does that mean convex hull is a type of convex polygon? $\endgroup$
    – Samitha Nanayakkara
    Oct 27, 2016 at 18:35
  • $\begingroup$ @LarryB. I didn't think my algorithm was new - now I know it has a name. Thanks. I don't think a convex hull is a type of convex polygon, since the hull includes the interior. A convex polygon together with its interior is a kind of convex set. $\endgroup$
    – Ethan Bolker
    Oct 27, 2016 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .