Thuật toán cho bản đồ sơ đồ (metro)

Question

Đây là một cảnh quay dài, nhưng tôi nghĩ tôi có thể thử trước khi bắt đầu công việc bẩn thỉu.

Tôi có một dự án để xây dựng một ứng dụng cho một trạm đầu vào (đỉnh) và đường thẳng (cạnh), đó là bản đồ thực sự của một số phương tiện giao thông công cộng. . Tôi đã thực hiện một số nghiên cứu về vấn đề này và đó là vấn đề NP-complete tương đương với vấn đề 3-SAT. Tôi cũng có một số ý tưởng lý thuyết về cách tạo ra một bản đồ như vậy, nhưng chúng không đủ chi tiết. Những gì tôi đang tìm kiếm là bất kỳ giải pháp hiện có nào khác của vấn đề này, một số loại mã giả, một số mã thực sự (hầu như) bất kỳ ngôn ngữ lập trình nào khác vv, bất cứ điều gì sẽ làm giảm thời gian tôi cần phải làm việc về bản thân thuật toán, điều này sẽ giúp tôi có nhiều thời gian hơn để làm việc trên các khía cạnh khác của ứng dụng.

Nếu có ai từng thấy bất kỳ thứ gì có thể giúp tôi, tôi rất cảm kích.

Answer 1

Nếu bạn google "vấn đề bố cục bản đồ tàu điện ngầm" và "tuyến đường tàu điện ngầm", bạn sẽ tìm thấy nhiều tài liệu tham khảo vì nó đã được nghiên cứu rất tích cực trong 10 năm qua.

Vấn đề dường như không tầm thường chút nào và việc dịch các tính năng "nghệ thuật" sang các ràng buộc toán học dường như là một trong những nhiệm vụ khó khăn nhất.

Dù sao đây là ba ấn phẩm mà tôi thấy thú vị để bắt đầu với (trong số nhiều, nhiều người khác):

Metro Map Layout Using Multicriteria Optimization

Line Crossing Minimization on Metro Maps

The Metro Map Layout Problem

HTH!

Answer 2

Đây chỉ là một số gợi ý với handwaving - dùng với một nhúm muối.

Khái niệm về bản đồ "tàu điện ngầm" của tôi là một trong những đường có xu hướng một trong tám hướng chính và các trạm được đặt cách đều nhau.

Tôi giả sử bạn đang cố chuyển đổi một tập tọa độ thực thành tọa độ "metro".

Tôi sẽ bắt đầu với tuyến đường chính của bạn (ví dụ: vòng thành phố), sau đó tăng dần các tuyến đường khác theo thứ tự tầm quan trọng.

Đối với mỗi tuyến đường bạn muốn tìm xấp xỉ gần nhất, sử dụng số lượng đường thẳng nhỏ nhất đi theo tám hướng chính. Bạn có thể làm điều này bằng cách bắt đầu với hộp giới hạn cho tọa độ thực, chia thành lưới, sau đó tìm tuyến đường "metro" từ ô lưới vuông sang lưới vuông, sau đó liên tục tinh chỉnh tuyến đường đó để giảm số lượng đường cong mà không bóp méo bản đồ quá nhiều và không giới thiệu giao cắt với các tuyến đường khác nếu có thể.

Sau khi thực hiện điều đó, hãy chia tỷ lệ mỗi dòng sao cho các trạm liên tiếp có cùng khoảng cách với chế độ xem "metro".

Tôi đoán bạn vẫn muốn hỗ trợ tinh chỉnh thủ công kết quả.

Chúc may mắn!

Answer 3

Nghiên cứu tương tự như chủ đề của bạn: http://graphics.stanford.edu/papers/routemaps/

Answer 4

Cảm thấy giống như vấn đề quy hoạch. Có vẻ như những khó khăn khó khăn của bạn là:

• Mỗi trạm phải ở một điểm. Một điểm đang ở trên một mạng lưới với khoảng cách giữa các điểm X (Tôi muốn làm cho tĩnh trên 2cm)

• Không nên có 2 trạm trên cùng một chỗ

• Nên có đủ chỗ để vẽ nhãn trạm. Lưu ý rằng nhãn có thể được chỉ định các hướng khác nhau từ điểm mà trạm được gán.

• Sẽ có đủ chỗ để vẽ các đường tàu điện ngầm.

Hình như khó khăn mềm của bạn là:

• Đối với mỗi trạm, hạn chế tối đa các vị trí khoảng cách địa lý thực sự đến điểm giao cho nhà ga.

Sau đó, ném thứ gì đó như Drools Planner lên đó, here's an example of hard and soft constraints for nurse rostering.