Cách nhanh nhất để tìm trung tâm "trực quan" của một đa giác có hình dạng bất thường là gì?

Question

Tôi cần tìm một điểm là trung tâm trực quan của một đa giác có hình dạng bất thường. Bởi trung tâm thị giác, tôi có nghĩa là một điểm xuất hiện ở trung tâm của một khu vực rộng lớn của đa giác một cách trực quan. Ứng dụng này là để đặt một nhãn bên trong đa giác.

Dưới đây là một giải pháp sử dụng bên trong đệm:

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

Nếu đây là để được sử dụng, một cách hiệu quả và nhanh chóng để tìm ra bộ đệm là gì? Nếu cách nào khác được sử dụng, đó là cách đó?

Một ví dụ tốt về đa giác thực sự khó khăn là một U khổng lồ dày (được viết bằng Arial Black hoặc Impact hoặc một số phông chữ như vậy).

Answer 1

Nếu bạn có thể chuyển đổi các đa giác thành một hình ảnh nhị phân, sau đó bạn có thể sử dụng nền tảng tồn tại trong lĩnh vực xử lý hình ảnh, ví dụ .: A Fast Skeleton Algorithm on Block Represented Binary Images.

Nhưng điều này là không thực sự hợp lý trong trường hợp chung, vì lỗi discretization và làm việc thêm.

Tuy nhiên, có thể bạn tìm thấy những hữu ích:

• Straight skeleton of a simple polygon
• Determining the Skeleton of a Simple Polygon in (Almost) Linear Time

EDIT: Có lẽ bạn muốn tìm kiếm những điểm đó là trung tâm của vòng tròn lớn nhất chứa trong đa giác. Nó không nhất thiết phải luôn luôn ở trong trung tâm quan sát, nhưng hầu hết thời gian có lẽ sẽ cho kết quả mong đợi, và chỉ trong những trường hợp bệnh lý hơi một cái gì đó hoàn toàn tắt.

Answer 2

Vấn đề này có thể tương tự như việc tìm kiếm "trung tâm khối lượng" giả sử mật độ đồng nhất.

EDIT: Phương pháp này sẽ không hoạt động nếu đa giác có "lỗ hổng"

Answer 3

Tính vị trí trung tâm (x, y) của mỗi cạnh của đa giác. Bạn có thể làm điều này bằng cách tìm sự khác biệt giữa các vị trí của các đầu của mỗi cạnh. Lấy trung bình của mỗi trung tâm trong mỗi chiều. Đây sẽ là trung tâm của đa giác.

Answer 4

Tôi nghĩ nếu bạn đã phá vỡ đa giác trở lại vào đỉnh của nó, và sau đó áp dụng một hàm để tìm thân lồi lớn nhất, và sau đó tìm trung tâm khỏi thân lồi, nó sẽ khớp với trung tâm "rõ ràng".

Tìm thân lồi lớn nhất cho các đỉnh: Look under the Simple Polygon paragraph.

Trung bình các đỉnh của thân lồi để tìm trung tâm.

Answer 5

Nếu tôi hiểu điểm của giấy bạn liên kết đến (một vấn đề thú vị, btw), kỹ thuật "đệm bên trong" này tương tự như mô hình hóa hình dạng được đề cập trong một phần đường đang bị hòa tan bởi axit từ các cạnh trong (ví dụ như khoảng cách bộ đệm tăng, ít hình dạng ban đầu vẫn còn) Các bit cuối cùng còn lại là nơi lý tưởng để đặt một nhãn.

Làm thế nào để thực hiện điều này trong một thuật toán không may là không phải là rất rõ ràng với tôi ....

Answer 6

bạn có thể đặt nhãn ở trung tâm ngây thơ (của hộp bounding, có lẽ), và sau đó di chuyển nó dựa trên các giao điểm của các cạnh đa giác cục bộ và BB của nhãn? Di chuyển dọc theo các tiêu chuẩn của các cạnh giao nhau, và nếu nhiều cạnh cắt nhau, tổng các chỉ tiêu của chúng cho chuyển động?

Chỉ cần đoán ở đây; trong loại vấn đề này, tôi có lẽ sẽ cố gắng giải quyết lặp đi lặp lại miễn là hiệu suất không quá quan tâm.

Answer 7

Bạn đã xem xét sử dụng công thức centroid chưa?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Answer 8

Làm thế nào để tìm ra "vòng tròn" của đa giác (vòng tròn lớn nhất vừa với nó), và sau đó căn giữa nhãn ở giữa đó? Dưới đây là một vài liên kết để giúp bạn bắt đầu:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

này sẽ không hoạt động hoàn hảo trên tất cả các đa giác, rất có thể; một đa giác trông giống như một C sẽ có nhãn ở một vị trí hơi khó lường. Nhưng lợi thế sẽ là nhãn sẽ luôn chồng chéo một phần cứng của đa giác.

Answer 9

Không có nhiều thời gian để xây dựng hoặc kiểm tra điều này ngay bây giờ, nhưng tôi sẽ cố gắng làm nhiều hơn nữa khi tôi có cơ hội.

Sử dụng centroid làm phương thức chính của bạn. Kiểm tra xem liệu trọng tâm có nằm trong đa giác hay không; nếu không, hãy vẽ một đường thẳng qua điểm gần nhất và ở phía bên kia của đa giác. Tại điểm giữa của phần của đường đó nằm trong đa giác, hãy đặt nhãn của bạn.

Bởi vì điểm gần nhất với centroid có khả năng bị ràng buộc một khu vực khá lớn, tôi nghĩ rằng điều này có thể cho kết quả tương tự như vòng vây của Kyralessa. Tất nhiên, điều này có thể trở nên bối rối nếu bạn có một đa giác có lỗ. Trong trường hợp đó, các vòng tròn có thể sẽ tốt hơn nhiều. Mặt khác, nó mặc định là phương pháp centroid (nhanh?) Cho các trường hợp điển hình.

Answer 10

Tôi không nói rằng đây là nhanh nhất, nhưng nó sẽ cung cấp cho bạn một điểm bên trong đa giác. Tính toán Straight Skeleton. Điểm bạn đang tìm kiếm là trên bộ xương này. Bạn có thể chọn một với khoảng cách bình thường ngắn nhất đến trung tâm của hộp giới hạn ví dụ.

Answer 11

Phương pháp Centroid đã được đề xuất nhiều lần. Tôi nghĩ rằng đây là một nguồn tài nguyên tuyệt vời mô tả các quá trình (và nhiều thủ thuật hữu ích khác với đa giác) rất trực giác:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

Ngoài ra, để đặt một nhãn UI đơn giản, nó có thể là đủ để chỉ tính toán bounding hộp của đa giác (một hình chữ nhật được xác định bởi x thấp nhất và cao nhất và tọa độ y của bất kỳ đỉnh trong đa giác), và nhận được trung tâm của nó tại địa chỉ:

{ 
    x = min_x + (max_x - min_x)/2, 
    y = min_y + (max_y - min_y)/2 
} 

Đây là nhanh hơn so với tính toán trọng tâm một chút, mà có thể là quan trọng đối với một ứng dụng thời gian thực hoặc nhúng.Cũng cần lưu ý rằng nếu đa giác của bạn là tĩnh (chúng không thay đổi hình dạng), bạn có thể tối ưu hóa bằng cách lưu kết quả của trung tâm BB/tâm tính khối lượng (tương ứng với đỉnh đầu tiên của đa giác) đến cấu trúc dữ liệu của đa giác.

Answer 12

bạn có thể sử dụng Trung tâm của Mass (hoặc Trung tâm của trọng lực) phương pháp được sử dụng trong công trình dân dụng, đây là một liên kết hữu ích từ wikipedia:

http://en.wikipedia.org/wiki/Center_of_mass

Answer 13

Làm thế nào về:

Nếu centroid của đa giác nằm bên trong đa giác, sau đó sử dụng nó, khác:

1) Mở rộng một đường thẳng từ trung tâm qua đa giác chia đa giác thành hai nửa diện tích bằng

2) "Trung tâm hình ảnh" là điểm nửa điểm giữa điểm gần nhất nơi đường chạm vào chu vi và điểm tiếp theo cắt chu vi theo hướng đi xa từ tâm

Dưới đây là một vài hình ảnh để minh họa cho nó:

Answer 14

tôi đã tìm thấy một giải pháp rất tốt để này từ MapBox gọi Polylabel. Toàn bộ nguồn có sẵn trên Github của chúng.

Về cơ bản, nó cố gắng tìm trung tâm hình ảnh của đa giác như T Austin đã nói.

Một số thông tin chi tiết đề nghị này có thể là một giải pháp thực hiện:

Thật không may, tính [giải pháp lý tưởng] vừa phức tạp và chậm chạp. Các giải pháp được công bố cho vấn đề này yêu cầu Triangulation Delaunay hạn chế hoặc tính toán một bộ xương thẳng như các bước tiền xử lý - cả hai bước đều chậm và dễ xảy ra lỗi.

Đối với trường hợp sử dụng của chúng tôi, chúng tôi không cần giải pháp chính xác - chúng tôi sẵn sàng trao đổi một số độ chính xác để tăng tốc độ. Khi chúng tôi đặt nhãn trên một bản đồ, điều quan trọng hơn là nó được tính bằng mili giây so với để hoàn hảo về mặt toán học.

Lưu ý nhanh về việc sử dụng. Mã nguồn hoạt động tuyệt vời cho Javascript out of the box tuy nhiên nếu bạn có ý định về việc sử dụng điều này với một đa giác "bình thường" thì bạn nên bọc nó trong một mảng trống rỗng như các chức năng ở đây mất GeoJSONPolygons chứ không phải là đa giác bình thường tức là

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; 
var center = polylabel([myPolygon]);