-
Notifications
You must be signed in to change notification settings - Fork 1
/
SegmentsIntersectionScanline2.java
155 lines (138 loc) · 4.45 KB
/
SegmentsIntersectionScanline2.java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package Geometry;
import java.util.*;
public class SegmentsIntersectionScanline2 {
public static Segment[] findIntersection(Segment[] s) {
int n = s.length;
Event[] events = new Event[n * 2];
for (int i = 0, cnt = 0; i < n; ++i) {
events[cnt++] = new Event(s[i].x1, s[i].y1, 1, s[i]);
events[cnt++] = new Event(s[i].x2, s[i].y2, -1, s[i]);
}
Arrays.sort(events, eventComparator);
NavigableSet<Segment> set = new TreeSet<>(segmentComparator);
for (Event event : events) {
Segment cur = event.segment;
if (event.type == 1) {
Segment floor = set.floor(cur);
if (floor != null && isCrossOrTouchIntersect(cur, floor))
return new Segment[]{cur, floor};
Segment ceiling = set.ceiling(cur);
if (ceiling != null && isCrossOrTouchIntersect(cur, ceiling))
return new Segment[]{cur, ceiling};
// SortedSet<Segment> head = set.headSet(cur);
// if (!head.isEmpty() && isCrossOrTouchIntersect(cur, head.last()))
// return new Segment[]{cur, head.last()};
//
// SortedSet<Segment> tail = set.tailSet(cur);
// if (!tail.isEmpty() && isCrossOrTouchIntersect(cur, tail.first()))
// return new Segment[]{cur, tail.first()};
set.add(cur);
} else {
Segment lower = set.lower(cur);
Segment higher = set.higher(cur);
if (lower != null && higher != null && isCrossOrTouchIntersect(lower, higher))
return new Segment[]{lower, higher};
// SortedSet<Segment> head = set.headSet(cur);
// SortedSet<Segment> tail = set.tailSet(cur, false);
// if (!head.isEmpty() && !tail.isEmpty() && isCrossOrTouchIntersect(head.last(), tail.first()))
// return new Segment[]{head.last(), tail.first()};
set.remove(cur);
}
}
return null;
}
public static class Segment {
final int x1, y1, x2, y2;
public Segment(int x1, int y1, int x2, int y2) {
if (x1 < x2 || x1 == x2 && y1 < y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
} else {
this.x1 = x2;
this.y1 = y2;
this.x2 = x1;
this.y2 = y1;
}
}
}
static final Comparator<Segment> segmentComparator = (a, b) -> {
if (a.x1 < b.x1) {
long v = cross(a.x1, a.y1, a.x2, a.y2, b.x1, b.y1);
if (v != 0)
return v > 0 ? -1 : 1;
} else if (a.x1 > b.x1) {
long v = cross(b.x1, b.y1, b.x2, b.y2, a.x1, a.y1);
if (v != 0)
return v < 0 ? -1 : 1;
}
return Integer.compare(a.y1, b.y1);
};
static class Event {
final int x, y;
final int type;
final Segment segment;
public Event(int x, int y, int type, Segment segment) {
this.x = x;
this.y = y;
this.type = type;
this.segment = segment;
}
}
static final Comparator<Event> eventComparator = (a, b) -> {
if (a.x != b.x)
return a.x < b.x ? -1 : 1;
if (a.type != b.type)
return a.type > b.type ? -1 : 1;
return Integer.compare(a.y, b.y);
};
static long cross(long ax, long ay, long bx, long by, long cx, long cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
static boolean isCrossOrTouchIntersect(Segment s1, Segment s2) {
long x1 = s1.x1;
long y1 = s1.y1;
long x2 = s1.x2;
long y2 = s1.y2;
long x3 = s2.x1;
long y3 = s2.y1;
long x4 = s2.x2;
long y4 = s2.y2;
if (Math.max(x1, x2) < Math.min(x3, x4) || Math.max(x3, x4) < Math.min(x1, x2)
|| Math.max(y1, y2) < Math.min(y3, y4) || Math.max(y3, y4) < Math.min(y1, y2))
return false;
long z1 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
long z2 = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1);
long z3 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
long z4 = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3);
return (z1 <= 0 || z2 <= 0) && (z1 >= 0 || z2 >= 0) && (z3 <= 0 || z4 <= 0) && (z3 >= 0 || z4 >= 0);
}
// random test
public static void main(String[] args) {
Random rnd = new Random();
for (int step = 0; step < 100_000; step++) {
int n = rnd.nextInt(100);
Segment[] s = new Segment[n];
for (int i = 0; i < n; i++) {
int r = 20;
int x1 = rnd.nextInt(r) - r / 2;
int y1 = rnd.nextInt(r) - r / 2;
int x2 = rnd.nextInt(r) - r / 2;
int y2 = rnd.nextInt(r) - r / 2;
s[i] = new Segment(x1, y1, x2, y2);
}
Segment[] intersection = findIntersection(s);
boolean hasIntersection = hasIntersection(s);
if (intersection == null == hasIntersection)
throw new RuntimeException();
}
}
static boolean hasIntersection(Segment[] s) {
for (int i = 0; i < s.length; i++)
for (int j = i + 1; j < s.length; j++)
if (isCrossOrTouchIntersect(s[i], s[j]))
return true;
return false;
}
}