Làm cách nào để tính điểm giao nhau của đường thẳng và hình dạng tùy ý?

Question

Có cách tính toán hình học các điểm giao nhau của đường thẳng và đường đồ họa tùy ý không? Tôi biết tất cả các đường và đường cong nằm trong đường dẫn, và tôi đang sử dụng phần tử canvas HTML5 nếu nó giúp ích gì. Về cơ bản, tôi có quyền truy cập vào tất cả các lệnh vẽ canvas và các đối số của chúng. Ví dụ, nếu API được gọi với một lineTo, sau đó một moveTo, sau đó một vòng cung tôi có tất cả các thông tin đó. Mỗi cuộc gọi đến API được lưu trữ trong một mảng. Tôi có định nghĩa đường dẫn, tôi chỉ muốn tìm ra nơi đường cắt ngang đường. Dưới đây là một hình ảnh cho thấy một ví dụ về các điểm tôi sẽ cần phải tìm.

alt text http://cl.ly/3228b0e7ea32b172e960/content

Cảm ơn bạn đã được trợ giúp! Một lần nữa, tôi muốn làm điều này hình học hơn là dựa trên pixel nếu có thể.

Answer 1

Bạn có thể muốn có một cái nhìn tại thư viện hình học Javascript Kevin Lindsey - nó chứa có lẽ tất cả các thuật toán interesection bạn đang tìm kiếm: http://www.kevlindev.com/geometry/index.htm

Answer 2

Không biết cách xác định đường dẫn đồ họa của bạn, bạn không thể trả lời câu hỏi của mình bằng thuật toán cụ thể. Có một giải pháp trong this book on algorithms cho các đoạn đường thẳng.

Answer 3

Nếu bạn có phương trình cho mọi thứ, thì bạn có thể làm điều đó (theo lý thuyết). Trong thực tế, nó không phải dễ dàng như vậy (đặc biệt là không phải trong trường hợp chung). This discussion có một số lời khuyên tốt về đường giao nhau và đường cong bezier.

Answer 4

Bạn muốn cắt một đường thẳng và một "spline" x (t), y (t) phải có nhiều nhất là đa thức bậc 4 cho cả x (t) và y (t). Bạn chỉnh sửa các phương trình, nhưng yo cần biết tất cả các tham số. Nếu giải pháp nằm ngoài một trong hai phạm vi (đoạn đường và phân đoạn spline đã bắt đầu và kết thúc) - hãy loại bỏ nó. q liên quan:

The intersection point between a spline and a line