Làm thế nào để lấy được một sơ đồ Voronoi cho tập hợp điểm của nó và hình tam giác Delaunay của nó?

Question

Tôi đang làm việc trên một trò chơi mà tôi tạo một bản đồ ngẫu nhiên các tỉnh (a la Risk or Diplomacy). Để tạo bản đồ đó, đầu tiên tôi tạo ra một loạt các điểm bán ngẫu nhiên, sau đó tìm ra các tam giác Delaunay của các điểm đó.

Khi thực hiện xong, bây giờ tôi đang tìm cách tạo một sơ đồ Voronoi của các điểm để phục vụ như là một điểm khởi đầu cho ranh giới tỉnh. Dữ liệu của tôi tại thời điểm này (không có ý định chơi chữ) bao gồm chuỗi điểm gốc và tập hợp các hình tam giác Delaunay.

Tôi đã nhìn thấy một số cách để thực hiện điều này trên web, nhưng hầu hết trong số chúng được gắn với cách Delaunay được bắt nguồn. Tôi rất muốn tìm thứ gì đó không cần phải được tích hợp vào Delaunay, nhưng có thể làm việc dựa trên dữ liệu một mình. Không có điều đó, tôi đang tìm một cái gì đó dễ hiểu cho một newbie hình học tương đối, như trái ngược với tốc độ tối ưu. Cảm ơn!

Answer 1

Sơ đồ Voronoi chỉ là đồ thị kép của Delaunay triangulation.

• Vì vậy, các cạnh của biểu đồ Voronoi nằm dọc theo các bisectors vuông góc của các cạnh của tam giác Delaunay, do đó tính toán các dòng đó.
• Sau đó, tính các đỉnh của biểu đồ Voronoi bằng cách tìm các giao điểm của các cạnh liền kề.
• Cuối cùng, các cạnh sau đó là tập con của các dòng bạn đã tính nằm giữa các đỉnh tương ứng.

Lưu ý rằng mã chính xác phụ thuộc vào biểu diễn nội bộ bạn đang sử dụng cho hai sơ đồ.

Answer 2

Tôi khá chắc chắn rằng 'tam giác' http://www.cs.cmu.edu/~quake/triangle.html có thể tạo ra Voronoi

Answer 3

Lý do tại sao mọi thứ được gắn với nhau là do tam giác Delaunay và sơ đồ Voronoi là cấu trúc kép. Có nghĩa là nó không phải là trí tuệ để đi từ voronoi đến delaunay và ngược lại.

Có nghĩa là nếu bạn có biểu đồ voronoi, tất cả những gì bạn cần làm là kết nối các điểm chia sẻ một cạnh và bạn sẽ có hình tam giác xóa (và ngược lại).

Answer 4

Nếu tốc độ tối ưu không phải là một cân nhắc, mã giả sau đây sẽ tạo ra một Voronoi sơ đồ một cách khó khăn:

for yloop = 0 to height-1 
    for xloop = 0 to width-1 

    // Generate maximal value 
    closest_distance = width * height 

    for point = 0 to number_of_points-1 
     // calls function to calc distance 
     point_distance = distance(point, xloop, yloop) 

     if point_distance < closest_distance 
     closest_point = point 
     end if 
    next 

    // place result in array of point types 
    points[xloop, yloop] = point 

    next 
next 

Giả sử bạn có một lớp 'điểm' hoặc cấu trúc, nếu bạn gán cho chúng màu sắc ngẫu nhiên, sau đó bạn sẽ thấy mẫu voronoi quen thuộc khi bạn hiển thị đầu ra.

Answer 5

Mỗi tam giác Delaunay của bạn chứa một điểm duy nhất trong sơ đồ Voronoi.

Bạn có thể tính toán điểm này bằng cách tìm giao điểm của ba số perpendicular bisectors cho mỗi tam giác.

Sơ đồ Voronoi của bạn sẽ kết nối tập hợp các điểm này, mỗi điểm có ba điểm gần nhất. (mỗi người hàng xóm có chung một cạnh của tam giác Delaunay)

Bạn có kế hoạch tiếp cận các trường hợp cạnh như thế nào?

Answer 6

Sau khi cố gắng sử dụng chuỗi này làm nguồn cho câu trả lời cho câu hỏi tương tự của mình, tôi thấy rằng thuật toán của Fortune - có khả năng vì nó là phổ biến nhất & do đó được ghi lại nhiều nhất - dễ hiểu nhất.

The Wikipedia article on Fortune's algorithm giữ liên kết mới tới mã nguồn trong C, C# và Javascript. Tất cả chúng đều xuất sắc và đi kèm với những ví dụ đẹp.