IBM's International Programing Contest Final Question!!!
The 1998 22nd Annual acm International Collegiate
Programming Contest World Finals
sponsored by IBM
Problem F
Polygon Intersections
Input: poly.in
Most drawing or illustration programs have simple tools for creating polygon objects. The better ones can find the
regions that are the intersections of two polygons. The picture below shows two polygons, one is a pentagon and the
other is a triangle. Their intersection consists of the two dark regions.
IBM has just hired you as a member of a programming team that will create a very sophisticated drawing/illustration
program. Your task is to write the part of the program that deals with polygon intersections. Your boss has told you
to delay work on the user interface and focus only on the geometric representations of the intersections.
A polygon in the Cartesian plane can be represented by a sequence of points that are its vertices. The vertices in the
sequence appear in the order in which they are visited when traveling clockwise around the polygon’s boundary; so
any two adjacent vertices in the sequence are the endpoints of a line segment that is one of the polygon’s sides. The
last and the first vertices in the sequence are also endpoints of a side. Vertices are identified by their x- and ycoordinates. Assume the following about each polygon.
·No point will occur as a vertex (on the same polygon) more than once.
·Two sides can intersect only at a common endpoint (vertex).
·The angle between any two sides with a common vertex has a measure that is greater than
0 and less than 360.
·The polygon has at least 3 vertices.
The intersection of two polygons consists of 0 or more connected regions. Your problem is to take two polygons and
determine the regions of their intersection that are polygons satisfying the criteria above.
Input
The input contains several data sets, each consisting of two polygons. Each polygon appears as a sequence of
numbers:
n x1 y1 x2 y2 ... xn yn
where the integer n is the number of vertices of the polygon, and the real coordinates (x1,y1) through (xn, yn) are the boundary vertices. The end of input is indicated by two 0’s for the values of n. These two 0’s merely mark the end of data and should not be treated as an additional data set.
Output
For each data set, your program should output its number (Data set 1, Data set 2, etc.), and the number of regions in the intersection of its two polygons. Label each region in the data set (Region 1, Region 2, etc.) and list its vertices in the order they appear when they are visited going either clockwise or counterclockwise around the boundary of
the region. The first vertex printed should be the vertex with the smallest x-coordinate (to break ties, use the smallestThe 1998 ACM Programming Contest World Finals sponsored by IBM y-coordinate). No region may include degenerate parts (consisting of adjacent sides whose angle of intersection is0). If the three endpoints of two adjacent sides are collinear, the two sides should be merged into a single side. Print each vertex in the standard form (x,y), where x and y have two digits to the right of the decimal.
The following sample input contains exactly one data set. (The data set corresponds to the illustration at the beginning of this problem description.)
Sample Input
3 2 1 0.5 3.5 8 5
5 1.5 3 2 7 6.5 6.5 6.5 3.25 4 4.5
0
0
Output for the Sample Input
Data Set 1
Number of intersection regions: 2
Region 11.50,3.00)(1.59,3.72)(3.25,4.05)
Region 24.43,4.29)(6.50,4.70)(6.50,4.00)(5.86,3.57)
Programming Contest World Finals
sponsored by IBM
Problem F
Polygon Intersections
Input: poly.in
Most drawing or illustration programs have simple tools for creating polygon objects. The better ones can find the
regions that are the intersections of two polygons. The picture below shows two polygons, one is a pentagon and the
other is a triangle. Their intersection consists of the two dark regions.
IBM has just hired you as a member of a programming team that will create a very sophisticated drawing/illustration
program. Your task is to write the part of the program that deals with polygon intersections. Your boss has told you
to delay work on the user interface and focus only on the geometric representations of the intersections.
A polygon in the Cartesian plane can be represented by a sequence of points that are its vertices. The vertices in the
sequence appear in the order in which they are visited when traveling clockwise around the polygon’s boundary; so
any two adjacent vertices in the sequence are the endpoints of a line segment that is one of the polygon’s sides. The
last and the first vertices in the sequence are also endpoints of a side. Vertices are identified by their x- and ycoordinates. Assume the following about each polygon.
·No point will occur as a vertex (on the same polygon) more than once.
·Two sides can intersect only at a common endpoint (vertex).
·The angle between any two sides with a common vertex has a measure that is greater than
0 and less than 360.
·The polygon has at least 3 vertices.
The intersection of two polygons consists of 0 or more connected regions. Your problem is to take two polygons and
determine the regions of their intersection that are polygons satisfying the criteria above.
Input
The input contains several data sets, each consisting of two polygons. Each polygon appears as a sequence of
numbers:
n x1 y1 x2 y2 ... xn yn
where the integer n is the number of vertices of the polygon, and the real coordinates (x1,y1) through (xn, yn) are the boundary vertices. The end of input is indicated by two 0’s for the values of n. These two 0’s merely mark the end of data and should not be treated as an additional data set.
Output
For each data set, your program should output its number (Data set 1, Data set 2, etc.), and the number of regions in the intersection of its two polygons. Label each region in the data set (Region 1, Region 2, etc.) and list its vertices in the order they appear when they are visited going either clockwise or counterclockwise around the boundary of
the region. The first vertex printed should be the vertex with the smallest x-coordinate (to break ties, use the smallestThe 1998 ACM Programming Contest World Finals sponsored by IBM y-coordinate). No region may include degenerate parts (consisting of adjacent sides whose angle of intersection is0). If the three endpoints of two adjacent sides are collinear, the two sides should be merged into a single side. Print each vertex in the standard form (x,y), where x and y have two digits to the right of the decimal.
The following sample input contains exactly one data set. (The data set corresponds to the illustration at the beginning of this problem description.)
Sample Input
3 2 1 0.5 3.5 8 5
5 1.5 3 2 7 6.5 6.5 6.5 3.25 4 4.5
0
0
Output for the Sample Input
Data Set 1
Number of intersection regions: 2
Region 11.50,3.00)(1.59,3.72)(3.25,4.05)
Region 24.43,4.29)(6.50,4.70)(6.50,4.00)(5.86,3.57)
Here's how I see it:
Let's name the polygons A and B.
First step should be to find vertexes of A that are inside B and vertexes of B that are inside A. These vertexes are on the borders of intersection regions. One way to see is a vertex is inside a polygon is to take a ray (direction doesn't matter) from the vertex and see how many times it intersects with the edges of a polygon. I'll assume you know how to find a line-line and line-ray intersections.
Once you find a vertex inside a polygon, put it into array C.
The second step is to find the points where edges of A and B intersect. Just try every edge of A with every edge of B. This could be greatly optimized (using data from previous step) but let's keep it simple. Once you have the intersections, put them into C.
The last step is to find closed loops in C. This is the step I'm not sure about. Perhaps a flexible representation of the polygons, where every line has pointers to it's endpoints and every point has an array of pointers to the lines that touch it could be of some use. I haven't tried that myself yet.
I'll let you know if I ever force myself to complete it.
Good luck.
Let's name the polygons A and B.
First step should be to find vertexes of A that are inside B and vertexes of B that are inside A. These vertexes are on the borders of intersection regions. One way to see is a vertex is inside a polygon is to take a ray (direction doesn't matter) from the vertex and see how many times it intersects with the edges of a polygon. I'll assume you know how to find a line-line and line-ray intersections.
Once you find a vertex inside a polygon, put it into array C.
The second step is to find the points where edges of A and B intersect. Just try every edge of A with every edge of B. This could be greatly optimized (using data from previous step) but let's keep it simple. Once you have the intersections, put them into C.
The last step is to find closed loops in C. This is the step I'm not sure about. Perhaps a flexible representation of the polygons, where every line has pointers to it's endpoints and every point has an array of pointers to the lines that touch it could be of some use. I haven't tried that myself yet.
I'll let you know if I ever force myself to complete it.
Good luck.
Topic archived. No new replies allowed.