@Test public void intersectionEdgeLimitTest() { LineSegment lineSegment1 = new LineSegment(new Point(0, 0), new Point(0, 1)); LineSegment lineSegment2 = new LineSegment(new Point(1, 1), new Point(-1, 1)); List<Point> res = LineSegmentIntersection.solve(Arrays.asList(lineSegment1, lineSegment2)); assertEquals(1, res.size()); assertEquals(new Point(0, 1), res.get(0)); }
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);  }