判断线段相交算法——ACM几何学基础

AM geometry algorithms foundation. PPT; 1. Determine if any two line segments do not intersect There is a group of line segments, and the task is to determine if any two line segments in this group do not intersect. Problem analysis: For a group of line segments, we can first assume that there are no line segments parallel to the vertical axis in this group of line segments, and there is also no situation where three line segments intersect at one point. Based on this assumption, we can use a vertical scanning line to scan this group of line segments. During the scanning process, we can observe that once two line segments intersect, the scanning result will change. That is, when the vertical scanning line scans from top to bottom, the outpu ...; School of Computer and Communication Engineering, Southwest Jiaotong University, January 2005 Intersecting Lines • We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect. • Your program;...