Đa giác, phức tạp nhanh chóng (với lỗ) triangulation c/C++ thư viện với giấy phép cho phép

Question

Tôi là một nhà phát triển của trò chơi mã nguồn mở, Bitfighter. Theo SO bài sau, chúng tôi đã sử dụng 'Tam giác' thư viện tuyệt vời cho thế hệ lưới khu vực để sử dụng với chúng tôi trong game AI (robot):

Polygon Triangulation with Holes

Tuy nhiên, chúng tôi chạy vào một snag nhỏ khi muốn đóng gói trò chơi của chúng tôi cho Debian - việc sử dụng thư viện 'Triangle' sẽ khiến trò chơi của chúng tôi được coi là 'không miễn phí'.

Chúng tôi rất hài lòng với hiệu suất của thư viện 'Tam giác' và không thực sự muốn từ bỏ nó; tuy nhiên, chúng tôi cũng không thích xử lý các vấn đề về giấy phép. Vì vậy, chúng tôi đã bắt tay vào một nhiệm vụ để tìm ra một sự thay thế phù hợp, được cấp phép có thể phù hợp với 'Tam giác' trong sự vững mạnh và tốc độ của nó.

Chúng tôi đang tìm thư viện C hoặc C++ để chia các khu vực lớn, phức tạp thành hình tam giác, có thể xử lý bất kỳ loại đa giác bất thường nào được đặt cùng nhau theo bất kỳ cách nào cũng như lỗ. Mạnh mẽ là nhu cầu chính của chúng tôi, với tốc độ gần như là quan trọng.

Tôi đã tìm thấy poly2tri, nhưng nó bị một lỗi trong đó nó không thể xử lý đa giác với các cạnh trùng hợp.

Chúng tôi đã tìm thấy một số thư viện, nhưng tất cả dường như bị một điều này hay cách khác: quá chậm hoặc không xử lý lỗ hoặc bị lỗi. Hiện tại chúng tôi đang thử nghiệm polypartition và chúng tôi có hy vọng cao.

Các phương án thay thế tốt nhất cho thư viện 'Tam giác' tuyệt vời, nhưng có giấy phép cho phép là gì?

Answer 1

Tôi đã tìm được giải pháp. Đó là poly2tri sau khi tất cả, với việc sử dụng các thư viện xuất sắc Clipper, và một số bổ sung thuật toán nhỏ để đầu vào.

quá trình của chúng tôi là như sau:

1. Chạy tất cả các lỗ của chúng tôi thông qua Clipper sử dụng một sự kết hợp với khác không quanh co (điều này có nghĩa là lỗ bên trong được vết thương theo hướng ngược lại như những người bên ngoài). Clipper cũng đảm bảo các điểm đầu vào sạch đẹp và không lặp lại trong epsilon.
2. Lọc các lỗ của chúng tôi thành các lỗ được quấn ngược chiều kim đồng hồ và theo chiều kim đồng hồ. Các lỗ theo chiều kim đồng hồ có nghĩa là lỗ được mạch và có một khu vực đồng tâm khác bên trong cần được triangulated
3. Sử dụng poly2tri, triangulate các giới hạn bên ngoài và mỗi đa giác theo chiều kim đồng hồ, sử dụng phần còn lại của các lỗ như đầu vào cho poly2tri nếu chúng được tìm thấy trong một trong các giới hạn.

Kết quả: poly2tri dường như có kích thước chỉ bằng Tam giác và cho đến nay rất mạnh mẽ với mọi thứ chúng tôi đã ném vào đó.

Đối với những người quan tâm, here are our code changes.

Cập nhật

Tôi đã cố gắng kéo ra clipper-to-poly2tri mã của chúng tôi, với những bổ sung mạnh mẽ của chúng tôi, vào một thư viện riêng biệt mà tôi bắt đầu ở đây: clip2tri

Answer 2

Bạn có thể xem gói 2D Triangulations của CGAL. Một ví dụ để triangulate một đa giác với lỗ được đưa ra here. Giấy phép của gói là GPLv3 +.

Lưu ý rằng không quá khó để trích xuất chỉ gói này nếu cần.

Answer 3

Là một phụ lưu ý nhỏ :

Gần đây tôi đã phải triển khai một bộ tạo hình đa giác phức tạp & triangulator để cắt khung cửa sổ thành tường nhà.

Trong khi tôi hài lòng với kết quả clipper của Vatti, tam giác Delaunay được sử dụng trong poly2tri quá nặng để cho phép kéo khung cửa sổ trơn tru dọc theo các tọa độ barycentric của mặt tường. Sau khi gãi đầu của tôi một chút, tôi đã kết thúc lừa tam giác đơn giản hơn nhiều này để làm việc với lỗ:

http://wiki.unity3d.com/index.php?title=Triangulator

Những gì tôi đã làm là theo chiều ngang chia nhỏ các mặt tường bằng chiều cao của clipping nhiều ngắn nhất. Trong trường hợp của tôi, chúng luôn là hình chữ nhật, nhưng chúng không cần thiết. Dù sao, nó buộc các clipper để chỉ làm việc với polys thường xuyên hoặc lõm, và do đó cho phép bạn để có được đi với một phương pháp triangulation rẻ hơn.

Dưới đây là một số ảnh chụp màn hình cho thấy nó làm việc:

https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak

Hope this helps.