Skip to main content

Thuật toán Jarvis để tính Convex Hull

· 9 min read
Doko

Gần đây khi làm việc với Aegisub và các công cụ karaoke, tôi nhận thấy việc tạo ra các hiệu ứng phức tạp liên quan đến hình học không đơn giản.

Ví dụ nếu muốn tạo hiệu ứng vỡ chữ sang các mảnh tam giác, ta cần đến thuật toán Jarviss hoặc Graham và Delauney. Trong đó:

  • Jarviss hoặc Graham: Dùng để tìm ra convex hull - bao lồi - là hình bao ngoài chứa tất cả các điểm đầu vào.
  • Delauney: Thuật toán chia convex hull thành các mảnh tam giác sao cho không có tam giác nào chồng lên nhau.

Thuật toán Jarviss​

Thuật toán Jarvis hay còn gọi là thuật toán chiều kim đồng hồ. Ý tưởng:

  • Ta bắt đầu từ điểm bên trái nhất (điểm có tọa độ x nhỏ nhất).
  • Từ điểm x này ta sẽ tiến hành "bao" các điểm còn lại theo hướng ngược chiều kim đồng hồ.

Vậy câu hỏi là, làm sao xác định được điểm tiếp theo? Câu trả lời là xét hướng.

Xác định hướng của 3 điểm (clockwise)​

Có 3 điểm nằm trên mặt phẳng tọa độ. Hướng quay của 3 điểm có thể là:

  • Ngược chiều kim đồng hồ (counterclockwise).
  • Thuận chiều kim đồng hồ (clockwise).
  • Thẳng góc (3 điểm nằm trên một đường thẳng - collinear).

Ta có sơ đồ sau:

  • Nếu chiều của (p1, p2, p3) là thẳng góc thì chiều của (p3, p2, p1) cũng thẳng góc.
  • Nếu chiều của (p1, p2, p3) thuận kim đồng hồ, thì chiều của (p3, p2, p1) ngược kim đồng hồ và điều ngược lại cũng đúng.

Ví dụ:

Đầu vào:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 2}
Đầu ra:  CounterClockWise

Đầu vào:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 1}
Đầu ra:  Colinear

Làm sao để tính? Ý tưởng là tính ra độ dốc:

slope

Độ dốc của 2 điểm (p1, p2): σ = (y2 - y1)/(x2 - x1) Độ dốc của 2 điểm (p2, p3): τ = (y3 - y2)/(x3 - x2)

Nếu σ > τ, hướng sẽ là thuận kim đồng hồ (quay phải).

Sử dụng các giá trị σ và τ trên, ta kết luận: Hướng của 3 điểm phụ thuộc vào dấu của biểu thức sau:

(y2 - y1)*(x3 - x2) - (y3 - y2)*(x2 - x1)

Nếu giá trị trả về của biểu thức trên là âm thì tức là ngược chiều kim đồng hồ.

Code thuật toán:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def orientation(p1, p2, p3):
    val = (float(p2.y - p1.y) * (p3.x - p2.x)) - (float(p2.x - p1.x) * (p3.y - p2.y))
    if (val > 0):

        # Thuận
        return 1
    elif (val < 0):

        # Ngược
        return 2
    else:

        # Thẳng hàng
        return 0

p1 = Point(0, 0)
p2 = Point(4, 4)
p3 = Point(1, 2)

o = orientation(p1, p2, p3)

if (o == 0):
    print("Linear")
elif (o == 1):
    print("Clockwise")
else:
    print("CounterClockwise")

Đọc đến đây thì ta gọi chút nhé:

  • p: Điểm đã xác định là nằm trong convex hull. Coi q là tâm đồng hồ.
  • q: Là điểm tiếp theo sao cho bộ ba (p, q, r) với r là điểm bất kì nào khác trong bộ điểm đầu vào.

Với thuật toán này thì ta có:

  • Độ phức tạp theo thời gian: O(1)
  • Auxiliary Space O(1)

Các bước tiếp theo:

slope

  1. Để tìm ra q, ta lấy q làm điểm tiếp theo, sau đó duyệt qua tất cả các điểm. Với điểm i bất kì, nếu i ngược chiều kim đồng hồ hơn (tính theo giá trị góc), ví dụ: orientation(p, i, q) là ngược chiều kim đồng hồ, thì ta gán q thành i. Kết quả q cuối cùng sẽ là điểm ban đầu (tức p).
  2. next[p] = q (Đặt q làm điểm tiếp theo của p để xét tiếp).
  3. p = q (Đặt p thành q cho lần duyệt tiếp).

Dưới đây là code của thuật toán trên:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def Left_index(points):

    minn = 0
    for i in range(1,len(points)):
        if points[i].x < points[minn].x:
            minn = i
        elif points[i].x == points[minn].x:
            if points[i].y > points[minn].y:
                minn = i
    return minn

def orientation(p, q, r):
    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2

def convexHull(points, n):
    if n < 3:
        return

    l = Left_index(points)

    hull = []

    p = l
    q = 0
    while(True):

        hull.append(p)

        q = (p + 1) % n

        for i in range(n):

            if(orientation(points[p],
                           points[i], points[q]) == 2):
                q = i


        p = q

        if(p == l):
            break

    for each in hull:
        print(points[each].x, points[each].y)

points = []
points.append(Point(0, 3))
points.append(Point(2, 2))
points.append(Point(1, 1))
points.append(Point(2, 1))
points.append(Point(3, 0))
points.append(Point(0, 0))
points.append(Point(3, 3))

convexHull(points, len(points))

Đầu ra: tập các điểm liên kết tạo thành Convex Hull:

(0, 3)
(0, 0)
(3, 0)
(3, 3)

Độ phức tạp tời gian: O(m * n), với n là số điểm đầu vào và m là số đầu ra (hay các điểm tạo thân), và m <= n. Với mỗi điểm m, ta xét tất cả các điểm khác để biết vị trí tiếp theo.

Worst case theo độ phức tạp thời gian: O(n2). Xảy ra khi tất cả các điểm đều nằm trên bao lồi (m = n).

Auxiliary Space: O(n), do n không gian phụ trợ đã được lấp đầy.

Lưu ý: Các đoạn code trên sẽ cho ra các kết quả khác nhau với các đầu vào có thứ tự khác nhau, nếu như có các điểm thẳng hàng trên bao lồi. Ví dụ:

Đầu vào:

(0, 3), (0, 0), (0, 1), (3, 0), (3, 3)

sẽ cho ra:

(0, 3) (0, 0) (3, 0) (3, 3)

một ví dụ khác, đầu vào:

(0, 3), (0, 1), (0, 0), (3, 0), (3, 3)

sẽ cho ra:

(0, 3) (0, 1) (0, 0) (3, 0) (3, 3)

Nguồn tham khảo:

http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/x05-convexhull.pdf http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf