Chuyển tới nội dung chính
Z

Trình trực quan hóa giao điểm đoạn thẳng

Giao điểm đoạn thẳng dạng hoạt hình — các phép kiểm tra hướng (orientation) bằng tích có hướng (cross-product) cùng điểm giao chính xác, có điều khiển từng bước. Chạy ngay trong trình duyệt.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

/

Mã giả

Press Run to animate the algorithm.

Cách dùng

  1. 1 Nhấn Run để kiểm tra xem hai đoạn thẳng có cắt nhau hay không.
  2. 2 Theo dõi bốn phép kiểm tra hướng (tích có hướng) quyết định kết quả.
  3. 3 Nếu chúng cắt nhau, điểm giao sẽ được đánh dấu màu xanh lá; nếu không, các đoạn thẳng sẽ chuyển sang màu đỏ.
  4. 4 Dùng Shuffle để tạo một cặp đoạn thẳng ngẫu nhiên mới.

Vì sao dùng công cụ này

  • Xem cách bốn phép kiểm tra hướng bằng tích có hướng phát hiện giao điểm đoạn thẳng mà không cần phép chia.
  • Hiểu quy tắc: mỗi đoạn thẳng phải nằm vắt qua đường thẳng chứa đoạn còn lại.
  • Xem điểm giao chính xác được tính toán khi hai đoạn thẳng cắt nhau.
  • Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không tải lên dữ liệu.

Câu hỏi thường gặp

Làm sao để biết hai đoạn thẳng có cắt nhau hay không?

Sử dụng phép kiểm tra hướng (tích có hướng): hai đoạn thẳng thực sự cắt nhau khi mỗi đoạn có hai đầu mút nằm ở hai phía đối diện của đường thẳng chứa đoạn còn lại.

Phép kiểm tra hướng bằng tích có hướng là gì?

Dấu của (b−a) × (c−a) cho biết điểm c nằm bên trái (dương), bên phải (âm), hay nằm trên (bằng không) đường thẳng có hướng từ a đến b.

Độ phức tạp thời gian là bao nhiêu?

O(1) — một số lượng cố định các phép toán số học cho hai đoạn thẳng. Để tìm giao điểm hiệu quả giữa n đoạn thẳng, người ta dùng thuật toán quét đường thẳng (sweep-line) với độ phức tạp O((n+k) log n).

Điểm giao được tính như thế nào?

Bằng cách giải hệ hai phương trình đường thẳng bằng định thức (quy tắc Cramer), cho ra điểm giao chính xác một khi đã biết hai đoạn thẳng cắt nhau.

Trình trực quan hóa giao điểm đoạn thẳng là gì?

Trình trực quan hóa giao điểm đoạn thẳng minh họa bằng hoạt hình các phép kiểm tra hướng (tích có hướng) để xác định xem hai đoạn thẳng có cắt nhau hay không: mỗi đoạn thẳng phải nằm vắt qua đường thẳng chứa đoạn còn lại. Khi chúng cắt nhau, công cụ sẽ tính ra điểm giao chính xác.

Tính năng

Kiểm tra hướng

Xem các phép kiểm tra hướng rẽ bằng tích có hướng quyết định xem hai đoạn thẳng có cắt nhau hay không.

Độ phức tạp

Hai đoạn thẳng: O(1). n đoạn thẳng (sweep-line): O((n + k) log n). Không gian: O(n).

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

segments (0,0)-(4,4) and (0,4)-(4,0)

Output

intersect: yes, at (2, 2)

Trường hợp sử dụng

  1. 1

    Hình học & đồ họa

    Phát hiện các cạnh cắt nhau trong đa giác, bản đồ, hoặc kiểm tra va chạm.

  2. 2

    Học toán học về hướng

    Xem cách tích có hướng có dấu phân loại các kiểu rẽ và giao cắt.

  3. 3

    Trực giác về sweep-line

    Hiểu cách thuật toán quét đường thẳng tìm tất cả giao điểm một cách hiệu quả.

Tóm tắt

Công cụ trực quan hóa giao điểm đoạn thẳng của Zerethon mô phỏng xem hai đoạn thẳng có cắt nhau hay không và cắt nhau ở đâu, ngay trong trình duyệt của bạn, bằng các phép kiểm tra hướng (tích có hướng - cross-product). Kiểm tra hai đoạn thẳng có độ phức tạp O(1); phát hiện tất cả giao điểm giữa n đoạn thẳng mất O((n + k) log n) với thuật toán quét đường thẳng (sweep-line, Bentley–Ottmann, k = số giao điểm). Không gian bộ nhớ là O(n).

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

Tài liệu tham khảo

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa giao điểm đoạn thẳng chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Công cụ liên quan

Trình mô phỏng Bubble Sort

Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Insertion Sort

Insertion Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Selection Sort

Selection Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Merge Sort

Mô phỏng merge sort có hoạt ảnh với điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt.

Mở công cụ

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Đăng ký miễn phí