Làm thế nào để tạo ra một đa giác lồi ngẫu nhiên?

Question

Tôi đang cố gắng đưa ra một phương pháp để tạo các đa giác lồi 2D ngẫu nhiên. Nó phải có các thuộc tính sau:

• tọa độ phải là số nguyên;
• đa giác nên nằm trong một hình vuông có các góc (0, 0) và (C, C), trong đó C được cho;
• đa giác nên có số đỉnh gần với một số N. đưa

Ví dụ, tạo đa giác ngẫu nhiên mà có 10 đỉnh và nằm bên vuông [0..100] x [0..100] .

Điều gì làm cho nhiệm vụ này trở nên khó khăn, thực tế là tọa độ phải là số nguyên.

Cách tiếp cận mà tôi đã thử là tạo ra các tập hợp điểm ngẫu nhiên trong hình vuông đã cho và tính toán thân lồi của những điểm này. Nhưng thân lồi kết quả là rất ít đỉnh so với N.

Bất kỳ ý tưởng nào?

Answer 1

Điều này không hoàn toàn đầy đủ, nhưng nó có thể cung cấp cho bạn một số ý tưởng.

Thoát ra nếu N < 3. Tạo vòng tròn đơn vị có N đỉnh và xoay vòng ngẫu nhiên [0.90] độ.

Ngắt ngẫu nhiên mỗi đỉnh ra ngoài từ gốc và sử dụng dấu của sản phẩm chéo giữa mỗi cặp đỉnh liền kề và gốc để xác định lồi. Đây là bước mà có sự cân bằng giữa tốc độ và chất lượng.

Sau khi thiết lập đỉnh của bạn, hãy tìm đỉnh có độ lớn nhất từ ​​gốc. Chia mỗi đỉnh theo độ lớn đó để bình thường hóa đa giác, và sau đó mở rộng nó theo (C/2). Dịch (C/2, C/2) và truyền lại thành số nguyên.

Answer 2

Một thuật toán đơn giản sẽ là:

1. Bắt đầu với dòng ngẫu nhiên (một hai đỉnh và hai cạnh đa giác)
2. Hãy ngẫu nhiên cạnh E của đa giác
3. Hãy mới điểm ngẫu nhiên P trên cạnh này
4. Lấy một đường thẳng L vuông góc với E đi qua điểm P. Bằng cách tính điểm giao nhau giữa đường T và các đường được xác định bởi hai cạnh kề với E, tính toán độ lệch lớn nhất của P khi độ lồi không bị phá vỡ.
5. Bù đắp điểm P một cách ngẫu nhiên trong phạm vi đó.
6. Nếu không đủ điểm, lặp lại từ 2.

Answer 3

cách tiếp cận ban đầu của bạn là đúng - tính thân lồi là cách duy nhất bạn sẽ làm hài lòng ngẫu nhiên, lồi và integerness.

Cách duy nhất tôi có thể nghĩ đến việc tối ưu hóa thuật toán của bạn để có được "nhiều điểm hơn" là bằng cách sắp xếp chúng xung quanh một vòng tròn thay vì hoàn toàn ngẫu nhiên. Điểm của bạn sẽ có nhiều khả năng ở gần "cạnh" của hình vuông hơn gần trung tâm. Ở trung tâm, xác suất phải là ~ 0, vì đa giác phải lồi.

Một tùy chọn đơn giản sẽ đặt bán kính tối thiểu cho các điểm của bạn xuất hiện - có thể là C/2 hoặc C * 0,75.Tính trung tâm của hình vuông C và nếu một điểm quá gần, hãy di chuyển nó ra khỏi tâm cho đến khi đạt đến khoảng cách tối thiểu.

Answer 4

Đây là thuật toán nhanh nhất mà tôi biết tạo ra mỗi đa giác lồi với xác suất bằng nhau. Đầu ra có chính xác N đỉnh, và thời gian chạy là O (N log N), vì vậy nó có thể tạo ra các đa giác lớn ngay cả rất nhanh.

• Tạo hai danh sách, X và Y, của N số nguyên ngẫu nhiên giữa 0 và C. Hãy chắc chắn rằng không có bản sao.
• Sắp xếp X và Y và lưu trữ các yếu tố tối đa và tối thiểu của chúng.
• Phân chia ngẫu nhiên các phần tử khác (không phải tối đa hoặc tối thiểu) thành hai nhóm: X1 và X2 và Y1 và Y2.
• Chèn lại các yếu tố tối thiểu và tối đa khi bắt đầu và kết thúc các danh sách này (minX khi bắt đầu X1 và X2, maxX ở cuối, v.v.).
• Tìm sự khác biệt liên tiếp (X1[i + 1] - X1[i]), đảo ngược thứ tự cho nhóm thứ hai (X2[i] - X2[i + 1]). Lưu trữ chúng trong danh sách XVec và YVec.
• Ngẫu nhiên (phát ngẫu nhiên) YVec và xử lý từng cặp XVec[i] và YVec[i] làm vector 2D.
• Sắp xếp các vectơ này theo góc và sau đó đặt chúng từ đầu đến cuối để tạo thành đa giác.
• Di chuyển đa giác đến các tọa độ tối thiểu và cực đại ban đầu.

Hoạt ảnh và triển khai Java có sẵn tại đây: Generating Random Convex Polygons.

Thuật toán này dựa trên một bài báo của Pavel Valtr: “Probability that n random points are in convex position.” Discrete & Hình học tính toán 13.1 (1995): 637-643.