Problem Statement
The examples contain images.
An important part of 3-D rendering is polygon clipping. This tells you which parts of various objects can be seen from a certain angle. In this problem, we'll be dealing with a similar, but much simpler task - 2-D line segment clipping. Consider a viewpoint from the origin, looking at the upper right quadrant of the Cartesian coordinate space (+x, +y). Assuming that the field of view encompasses the full 90 degrees, your task is to determine which of a number of line segments contribute to the view. More formally, a line segment contributes to the view if there are an infinite number of points (with real coordinates) on that line segment such that the line segment between the origin and each of those points does not intersect any segments in the space.
You will be given a String[], segs, each element of which represents a line segment from (X1,Y1) to (X2,Y2) in the form "X1 Y1 X2 Y2". Return the number of the segments which contribute to the view.
An important part of 3-D rendering is polygon clipping. This tells you which parts of various objects can be seen from a certain angle. In this problem, we'll be dealing with a similar, but much simpler task - 2-D line segment clipping. Consider a viewpoint from the origin, looking at the upper right quadrant of the Cartesian coordinate space (+x, +y). Assuming that the field of view encompasses the full 90 degrees, your task is to determine which of a number of line segments contribute to the view. More formally, a line segment contributes to the view if there are an infinite number of points (with real coordinates) on that line segment such that the line segment between the origin and each of those points does not intersect any segments in the space.
You will be given a String[], segs, each element of which represents a line segment from (X1,Y1) to (X2,Y2) in the form "X1 Y1 X2 Y2". Return the number of the segments which contribute to the view.
Definition
- Class:
- Clipping
- Method:
- clip
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int clip(String[] segs)
- (be sure your method is public)
Constraints
- segs will contain between 1 and 50 elements, inclusive.
- Each element of segs will be formatted as "X1 Y1 X2 Y2".
- Each coordinate will be an integer between 0 and 100, inclusive, and will not contain any extraneous leading zeros.
- No two segments will intersect at more than a single point.
- No segment will touch (0,0).
Examples
{"10 0 0 10","5 0 0 5"}Returns: 1
The segment from (10,0) to (0,10) is completely clipped by the segment from (5,0) to (0,5){"10 0 5 10","10 5 0 10","10 0 0 10"}Returns: 1
{"10 0 5 10","10 5 0 10","11 0 0 11"}Returns: 3
{"10 0 5 5","5 5 0 10","2 1 8 4","6 5 5 6"}Returns: 2
The segment from (2,1) to (8,4) is parallel to the line of sight from the origin, and hence only a single point can be seen, so it doesn't contribute.
Back to all problems