"Algorithm Project for convex hull[@more@]

資工二甲 494511689

賴家偉

什麼是convex hull? 中文翻成 “凸包”基本上，翻的非常爛，從字面上還是不知道是啥

但在這之前我們先來了解凸多邊型的定義:

凸多邊型，直觀的來說，就是不凹，沒有凹的部份。像 凹 、凸這兩個字都不算凸多邊型。 而像正方形長方形三角形這種形狀就是凸多邊型。可是上述這一定義很不嚴密，究竟何謂「凹陷位」？實在難以說清楚。因此在數學上，凸多邊形有另一個嚴格 的定義。假設我們在一個多邊形上(包括多邊形的邊界及邊界圍封的範圍)任意取兩點並以一條線段連結該兩點 ，如果線段上的每一點均在該多邊形上，那麼我們便說這個多邊形是凸的。根據以上定義，我們便可判斷「凸 」字形的確不是凸的。例如，在下圖中，連結A、B兩點的線段有一部分並不在該多邊形上。

而以下是wiki對convex hull 的定義

在一個實數向量空間V中，對於給定集合X，所有包含X的凸集的交集S被稱為X的凸包。

X的凸包可以用X內所有點 的線性組合來構造。

在二維歐幾裡得空間中，凸包可想像為一條剛好包著所有點的橡皮圈。

乍看之下，似乎很複雜，但簡單來說，就是給妳ㄧ堆點，然後將連起來是最大面積的點找出來，也就是最外面的點。

What is the convex hull of a set of points? 以下的兩點說明

• Formally: It is the smallest convex set containing the points.
• Informally: It is a rubber band wrapped around the "outside" points.

而常見用來找出convex hull的演算法有下列五種

1.      Incremental

The incremental algorithm is an algorithm for computing the convex hull of a set of points in two or more dimensions.

The basic idea is to add points one at a time updating the hull as we proceed.

 If the new point (shown in red) is inside the hull there is nothing to do. Otherwise, we must delete all the edges (shown in yellow) that the new point can see.

Add two edges to connect the new point to the remainder of the old hull

Repeat for the next point outside the hull.

2.      Gift wrap(Jarvis' march)

此演算法或許是對於解決convex hull來說最簡單的一種演算法, 而且在某些情況中它可以非常的快。它的基本概念如下：

• Start at some extreme point, which is guaranteed to be on the hull.
• At each step, test each of the points, and find the one which makes the largest right-hand turn. That point has to be the next one on the hull.

Because this process marches around the hull in counter-clockwise order, like a ribbon wrapping itself around the points, this algorithm also called the "gift-wrapping" algorithm.

當用程式來跑的話，若點為30個，且是亂數的話，需要run 247次。 就像我們看到的。並不快 quick hull快多了。

事實上 若 有N個點排成圓形的話Jarvis' march 花的次數則會是N^2 次數

If you think about it, Jarvis' march takes time proportional to nh, where n is the number of input points, and h is the number of points on the hull. In other words, Jarvis' march is output-sensitive. The algorithm works best such as the following, where h is 3:

則只需要run 85次

3. Graham's Scan

Given a set of points on the plane, Graham's scan 可以算出它們 convex hull.

這個演算法主要為列三個步驟

1. Find an extreme point. This point will be the pivot, is guaranteed to be on the hull, and is chosen to be the point with largest y coordinate.

2. Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).

3. Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.

而此演算法剛好跟第4個quick hull相反 在點是整齊排列時速度較快，而在點是亂數排列是較慢

用程式來跑的話，若點為50個，且是亂數的話，需要run201次。

若50個點排成圓形的話，則只需要run117次即可執行完畢

4.      Quick hull

就如他的名字， Quick 。它是一種很快地方法用來計算convex hull的演算法當有一群點集合在圖上時。I基本上它跟 quick-sort:  有許多類似之處。

以下的四個步驟為它的過程基本概念。

1. We are given a some points, and line segment AB which we know is a chord of the convex hull (IE, it's endpoints are known to be on the convex hull). A good chord to start the algorithm goes from the leftmost to the rightmost point in the set.
2. Among the given points, find the one which is farthest from AB. Let's call this point C.
3. The points inside the triangle ABC cannot be on the hull. Put them in set s0.
4. Put the points which lie outside edge AC in set s1, and points outside edge BC in set s2.

當partition做完了以後我們可以迴歸到s1 s2 這個演算法在當點是亂數排列的時是最快速的 但當點是很整齊的排列是就較差because step 3 of the partition typically discards a large fraction of the points.

用程式來跑的話，若點為50個，且是亂數的話，只需要run 124次。

若50個點排成圓形的話，則需要run318次!

剛好跟第3個成對比。

1. Divide and Conquer

Divide the points into two equal sized sets L and R such that all points of L are to the left of the most leftmost points in R.

Recursively find the convex hull of L (shown in light blue) and R (shown in purple).

To merge the left hull and the right hull it is necessary to find the two red edges shown on the left (the upper and lower common tangents).

The upper common tangent can be found in linear time by scanning around the left hull in a clockwise direction and around the right hull in an anti-clockwise direction.

The two tangents divide each hull into two pieces. The edges belonging to one of thse pieces must be deleted (shown in yellow).

The final hull.

以另一個程式來跑的話

見下表:

PS: In circle 代表最終的convex hull 為近似圓的圖形

   On circle 代表點為一個圓形

   In square 代表最終的 convex hull 為近似正方形的圖形

以此可以得到結論

Gift wrap 在 in circle and on circle, in square  是最快的

Quick hull 沒有意外的在 on circle 大幅落後對手最慢

總結來說 那一種演算法都各有好處也各有各的缺點 所以必須看情況來使用才是對正確的方法

Reference:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

http://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85

http://www.cs.princeton.edu/~ah/alg_anim/version1/ConvexHull.html

http://www.geocities.com/kfzhouy/Hull.html

"