Xác định nếu đa giác 2d có thể được vẽ bằng một quạt tam giác đơn

Question

Lúc đầu, tôi nghĩ vấn đề này sẽ tương đương với việc xác định xem đa giác có lồi hay không, tuy nhiên có vẻ như một đa giác không lồi vẫn có thể được vẽ bởi một tam giác quạt. Consider this shape, đa giác không lồi. Người ta có thể dễ dàng tưởng tượng một số khu vực trung tâm mà sẽ cho phép đa giác này được rút ra với một fan hâm mộ tam giác (mặc dù sẽ có trung tâm khác mà sẽ không). Với một điểm trung tâm cố định, tôi muốn có thể xác định nếu tập hợp các điểm 2d xác định đa giác cho phép nó được vẽ bằng một quạt tam giác đơn.

Có vẻ như điều quan trọng là đảm bảo không có gì "bị cản trở" của đường thẳng được vẽ từ điểm giữa đến bất kỳ đỉnh nào, điều đó có nghĩa là các đường cạnh khác của đỉnh. Tuy nhiên, điều quan trọng là làm cho việc này trở nên kém tốn kém về mặt tính toán nhất có thể và tôi không chắc liệu có một lối tắt toán học tốt để thực hiện điều này hay không. Cuối cùng, tôi sẽ có các đỉnh của đa giác di chuyển, và tôi sẽ cần phải xác định "ranh giới" một đỉnh được phép di chuyển, phần còn lại được cố định (và có lẽ sau này thậm chí cho phép phản ứng đồng thời chuyển động của 2 hàng xóm trực tiếp), để giữ cho đa giác có khả năng được vẽ trong một quạt tam giác đơn. Nhưng đó là tương lai, hy vọng thử nghiệm trên đa giác đầy đủ có thể được chia thành một tập hợp con các phép tính để kiểm tra các giới hạn của chuyển động của một đỉnh với giả định của một đa giác đã lồi.

Answer 1

Một đa giác có thể được vẽ như một quạt tam giác nếu góc từ neo đến mỗi đỉnh di chuyển theo cùng một hướng. Cách dễ nhất để kiểm tra điều này là kiểm tra các sản phẩm chấm của các sản phẩm chéo của các đỉnh liên tiếp.

Nó sẽ giống như thế này:

vector lastCross = cross_product(vector(vertex[0] - center), vector(vertex[numVerts - 1] - center)); 

canBeFan = true; 
for (n = 1; canBeFan && n < numVerts; ++n) { 
    vector testCross = cross_product(vector(vertex[n] - center), vector(vertex[n - 1] - center)); 
    if (0.0 >= dot_product(testCross, lastCross)) { 
     canBeFan = false; 
    } 
} 

Answer 2

Thuộc tính bạn đang tìm kiếm là "star-shaped". Đa giác hình ngôi sao được xác định bằng cách có một điểm mà từ đó toàn bộ đa giác hiển thị.

Để kiểm tra xem đa giác có hình ngôi sao hay không, bạn có thể tạo vùng mà toàn bộ đa giác sẽ hiển thị. Vùng đó sẽ là một tập hợp lồi, vì vậy bạn có thể giao cắt nó bằng một nửa thủy phi cơ trong O(log(n)).

Điều đó có nghĩa là bạn có thể giao nhau với nửa cầu được tạo thành bởi các cạnh và kiểm tra xem vùng hiển thị kết quả là không rỗng trong O(n log n).

Answer 3

Dường như tất cả centerpoints tiềm năng sẽ cần phải được ở bên nội thất của mỗi cạnh của đa giác của bạn. Vì vậy, đối xử với tất cả các cạnh của bạn là một nửa không gian và xác định xem giao lộ của chúng có trống hay không.

Như @jpalecek nói, thuật ngữ này là hình ngôi sao. Nếu đa giác của bạn có hình ngôi sao, sẽ có đa giác lồi (bên trong bản gốc) có điểm có thể xem tất cả các cạnh của bản gốc - và ngược lại, nếu không có đa giác phụ như vậy, bản gốc không phải là hình ngôi sao và bạn không thể vẽ nó bằng quạt tam giác.

Xác định đa giác con này về cơ bản là ứng dụng dual của sự cố convex hull; nó có thể được tính toán trong O(n log n).