@Test public void randomTest() { int upLimit = 100; for (int i = 0; i < 100; i++) { if (i % 20 == 19) upLimit <<= 1; Set<LineSegment> xLines = generateLine(upLimit / 5, upLimit, true); Set<LineSegment> yLines = generateLine(upLimit / 20, upLimit, false); List<LineSegment> testInput = new ArrayList<>(); testInput.addAll(xLines); testInput.addAll(yLines); List<Point> res = LineSegmentIntersection.solve(testInput); assertEquals(expect(xLines, yLines), new HashSet(res)); } }
public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; }
LineSegmentIntersection { public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; } }
LineSegmentIntersection { public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; }  }
LineSegmentIntersection { public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; }  static List<Point> solve(List<LineSegment> input); }
LineSegmentIntersection { public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; }  static List<Point> solve(List<LineSegment> input);  }