镜之国的爱丽丝
0%

03 - 任意两线段是否相交 - 暴力法

发表于 更新于 分类于

1. 算法思路

直接遍历，两两检测线段是否相交

  • 时间复杂度：O(n2)O(n^2)

2. 示例代码

2.1 import

1
2
3
4
5
6
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;
import primitives.Point;
import primitives.Segment;

2.2 SegmentsIntersect.class

2.2.1 成员

1
2
// 记录一对相交的线段
private static Segment segm1, segm2;

2.2.2 检测两线段是否相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static boolean two(Segment s1, Segment s2) {
    
    Point p1 = s1.getLeft();
    Point p2 = s1.getRight();
    Point p3 = s2.getLeft();
    Point p4 = s2.getRight();
    
    double d1 = direction(p3, p4, p1);
    double d2 = direction(p3, p4, p2);
    double d3 = direction(p1, p2, p3);
    double d4 = direction(p1, p2, p4);
    
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        return true;
    } else if (d1 == 0 && onSegment(p3, p4, p1)) {
        return true;
    } else if (d2 == 0 && onSegment(p3, p4, p2)) {
        return true;
    } else if (d3 == 0 && onSegment(p1, p2, p3)) {
        return true;
    } else if (d4 == 0 && onSegment(p1, p2, p4)) {
        return true;
    } else {
        return false;
    }
}

private static double direction(Point p0, Point p1, Point p2) {
    return ((p2.getX() - p0.getX()) * (p1.getY() - p0.getY()) -
            (p2.getY() - p0.getY()) * (p1.getX() - p0.getX()));
}

private static boolean onSegment(Point pi, Point pj, Point pk) {
    return (Math.min(pi.getX(), pj.getX()) <= pk.getX() &&
            pk.getX() <= Math.max(pi.getX(), pj.getX()) &&
            Math.min(pi.getY(), pj.getY()) <= pk.getY() &&
            pk.getY() <= Math.max(pi.getY(), pj.getY()));
}

2.2.3 暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static boolean any_Naive(ArrayList<Segment> segments) {
    for (int i = 0; i < segments.size() - 1; i++) {
        for (int j = i + 1; j < segments.size(); j++) {
            if (SegmentsIntersect.two(segments.get(i), segments.get(j))) {
                
                segm1 = segments.get(i);
                segm2 = segments.get(j);
                
                return true;
            }
        }
    }
    
    return false;
}