Hợp nhất các đoạn đường 2d

Question

Tôi đang tìm cách kết hợp các đoạn đường 2D với nhau. Một đoạn đường thẳng được tạo thành từ hai điểm vectơ, phần đầu của đoạn đường thẳng và điểm cuối của đoạn đường thẳng.

Tôi muốn tham gia các đoạn đường trông giống như chúng sẽ hình thành cùng một đường thẳng, tôi không muốn tham gia các đoạn thẳng nếu chúng có định hướng hoàn toàn khác nhau nhưng xảy ra có 2 điểm gần nhau. Hệ thống tôi sẽ sử dụng hệ thống này là một hệ thống thị giác máy tính, do đó các đoạn thẳng thu được sẽ không hoàn hảo tức là các hướng có thể hơi lệch, các đoạn có thể không có chiều dài toàn bộ e.t.c.

Tôi nghĩ 3 ví dụ sau có chứa các loại phân đoạn đường tôi muốn tham gia với nhau:

Cảm ơn

Answer 1

Đây là vấn đề hình học tính toán có thể có một số giải pháp trong sách giáo khoa có liên quan, nhưng được cảnh báo những vấn đề này thường rất khó giải quyết và độ chính xác hữu hạn là một vấn đề thực sự. Đối với vấn đề này (trong 2D) thuật ngữ bạn có thể tìm kiếm là các dòng là gần collinear. Thông thường những gì bạn làm để xác định xem các đường thẳng có được sắp xếp hay không trước tiên đặt chúng trong một vector representation, sau đó lấy sản phẩm dấu chấm giữa các vectơ, sẽ bằng cosin của góc giữa các đường. Vì vậy, nếu giá trị này gần một giá trị thì chúng gần với collinear và nên được kết hợp.

Vấn đề tiếp theo là xác định xem các dòng có đủ gần để cần tham gia không. Bạn có thể làm điều này bằng cách tìm các dòng intersect hoặc tìm các đường có điểm bắt đầu và kết thúc rất gần ... Đây không phải là tất cả những điều dễ dàng nói chung, nhưng bạn có thể nhận được 95% trong số chúng theo cách này.