Hội tụ điểm ngắt trong thuật toán của Fortune

Question

Tôi đang triển khai thuật toán quét của Fortune để tính toán sơ đồ Voronoi. Tài liệu tham khảo chính của tôi là "Hình học tính toán: Thuật toán và ứng dụng" của de Berg và cộng sự, và trong khi độ che phủ của chủ đề là rất rõ ràng, chúng vượt qua một số chi tiết nhỏ nhưng quan trọng mà tôi gặp khó khăn khi tự làm việc. Tôi đã tìm kiếm trên web để được trợ giúp, nhưng các trang web khác cung cấp một cái nhìn tổng quan thậm chí còn cao hơn sách giáo khoa, hoặc cung cấp mã giả tương tự được cung cấp bởi cuốn sách.

Tôi cần một cách để xác định xem một cặp điểm ngắt được xác định bởi ba vòng cung trên đường bờ biển hội tụ hay phân kỳ, để phát hiện sự kiện vòng tròn sắp tới. Dường như để đưa ra quyết định, tôi sẽ cần kiến ​​thức về hình dạng của các cạnh tế bào Voronoi mà các điểm ngắt xuất hiện khi thuật toán của tạp chí Fortune tiến triển. Ví dụ, nếu tôi có thể tìm thấy độ dốc của cạnh được bắt đầu bởi điểm ngắt, tôi có thể tính toán nơi hai đường được hình thành bởi các điểm ngắt và các sườn tương ứng giao nhau và quyết định liệu chúng có hội tụ dựa trên kết quả đó hay không. Tuy nhiên, tôi không có ý tưởng làm thế nào để có được thông tin về các sườn núi, chỉ có vị trí hiện tại của các điểm ngắt.

Thông tin duy nhất tôi phải làm việc là vị trí x, y của ba vị trí và toạ độ y hiện tại của đường quét (tôi đang sử dụng đường quét ngang).

Thực ra, tôi có một ý tưởng để xác định hội tụ. Với hai vị trí, điểm ngắt giữa hai phần của đường bờ biển mà chúng xác định chỉ được điều chỉnh bởi vị trí hiện tại của đường quét. Tôi nghĩ về việc ghi lại vị trí của hai điểm ngắt, tạm thời tiến lên đường quét một lượng nhỏ và ghi lại vị trí mới của họ. Bởi vì các cạnh trong biểu đồ Voronoi bình thường không cong, nếu khoảng cách giữa cặp điểm ngắt mới nhỏ hơn khoảng cách giữa cặp cũ, thì các điểm ngắt hội tụ; nếu không, chúng sẽ phân kỳ. Nhưng điều này có vẻ cả nguy hiểm (tôi không có ý tưởng nếu nó luôn luôn hoạt động) và xấu xí. Chắc chắn phải có một cách tốt hơn.

Bất kỳ ý tưởng nào sẽ được đánh giá cao và mã giả (trong cú pháp C# giống nếu có thể) đặc biệt là như vậy. Ngoài ra, tôi biết rằng có các thư viện hình học tính toán mà tôi có thể sử dụng để lấy sơ đồ Voronoi, nhưng đây là một bài tập học tập cá nhân, vì vậy tôi muốn tự mình triển khai tất cả các phần của thuật toán.

Answer 1

Chào mừng Drake. Tôi thực hiện nó bằng cách kiểm tra xem các điểm ngắt vật lý hội tụ trên trung tâm vòng tròn trong một 'hư cấu' tăng của vị trí quét. Điều này thực sự phức tạp một chút bởi vì trong một số trường hợp, trung tâm vòng tròn có thể gần như chính xác ở vị trí quét, do đó gia tăng đường quét cần tỷ lệ thuận với chênh lệch giữa vị trí quét hiện tại và trung tâm hình tròn được tạo ra theo ý bạn.

Say:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (và chúng tôi đang di chuyển xuống dưới, tức là theo hướng giảm dần).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY)/10.0f (số chia 10,0f được tùy ý chọn).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

Tôi biết điều này có lẽ rất tốn kém, vì bạn phải tính toán các vị trí điểm ngắt nhiều lần, nhưng tôi tự tin rằng nó sẽ xử lý tất cả các trường hợp có thể xảy ra.

Dù sao, tôi đang tìm các vấn đề nghiêm trọng với lỗi chính xác điểm nổi ở nơi khác trong thuật toán. Chắc chắn không đơn giản như tôi nghĩ ban đầu.

Answer 2

Vì vậy, điều này khá đáng ngại, nhưng sau khi ngủ về vấn đề, câu trả lời có vẻ hiển nhiên. Tôi đang viết điều này để hy vọng sẽ giúp học sinh trong tương lai với cùng một câu hỏi như tôi.

Cạnh Voronoi giữa hai vị trí vuông góc chia đôi đoạn đường (tưởng tượng) kết nối các trang web. Bạn có thể lấy được độ dốc của cạnh bằng cách lấy vuông góc với độ dốc của đoạn đường nối, và sau đó thực hiện kiểm tra giao cắt đường thẳng trên hai cạnh, nhưng có một cách dễ dàng hơn.

Miễn là ba trang web là not collinear, thì các cạnh vuông góc chia đôi các đoạn giữa các vị trí cũng tiếp xúc với vòng tròn có cạnh chứa tất cả ba vị trí. Do đó các điểm ngắt được xác định bởi ba vị trí Voronoi hội tụ nếu tâm của vòng tròn được xác định bởi ba vị trí nằm ở phía trước của trang giữa, trong đó "ở phía trước" và "phía sau" phụ thuộc vào hệ tọa độ và liên kết đường quét bạn có sự lựa chọn.

Trong trường hợp của mình, tôi có đường quét ngang mà tôi đang di chuyển từ y tối thiểu đến tối đa y, vì vậy các điểm ngắt hội tụ nếu toạ độ y của tâm vòng tròn lớn hơn toạ độ y của vị trí giữa và phân kỳ khác.

Chỉnh sửa: Kristian D'Amato đúng chỉ ra rằng thuật toán ở trên bỏ qua một số trường hợp hội tụ. Các thuật toán cuối cùng tôi đã kết thúc bằng cách sử dụng là dưới đây.Tất nhiên, tôi không tự tin rằng chính xác 100% của nó, nhưng nó có vẻ làm việc cho tất cả các trường hợp tôi đã thử nó trên.

Given left, middle, right sites 
    if they are collinear, return false 
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right) 
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center) 

IsRightOfLine(start, end, point) 
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0 

Answer 3

Nếu các vị trí được sắp xếp theo chiều kim đồng hồ xung quanh tâm của vòng tròn, vòng cung sẽ hội tụ. Nếu chúng được đặt ngược chiều kim đồng hồ xung quanh tâm của vòng tròn, cung tròn sẽ phân kỳ. (hoặc ngược lại, tùy thuộc vào việc triển khai của bạn). Thử nghiệm cho cw hoặc ccw rơi ra khỏi mã bạn sử dụng để tìm trung tâm của vòng tròn.

Dưới đây là một đoạn mã C# để tính circumcenter d của điểm a, b, c:

 Vector2 ba = b - a; 
     Vector2 ca = c - a;  
     float baLength = (ba.x * ba.x) + (ba.y * ba.y); 
     float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
     float denominator = 2f * (ba.x * ca.y - ba.y * ca.x); 
     if (denominator <= 0f) { // Equals 0 for colinear points. Less than zero if points are ccw and arc is diverging. 
      return false; // Don't use this circle event! 
     }; 
     d.x = a.x + (ca.y * baLength - ba.y * caLength)/denominator ; 
     d.y = a.y + (ba.x * caLength - ca.x * baLength)/denominator ;