IDEA: Polygon unions and intersections
Imagine two polygons A and B. A polygon is a set amount of points connected to each other where each point is connected to exactly two other points (see picture below). The task is to write the functions Union and Intersection.
The Union of A and B is defined as the polygon whose area is the union of A's area and B's area, meaning both areas are merged into one (see picture). Functions like A OR B.
The Intersection of A and B is defined as the polygon whose area is the intersection of A's area and B's area, meaning the parts that both areas have in common (see picture). Functions like A AND B.
First you have to come up with a good way of representing a polygon. Using a structure for a line (containing two points) and then a class to keep track of all lines could be a good way, since the number of lines in the resulting polygon will most likely vary.
This is not neccessary though, if you don't feel like using C++ that's fine :).
The functions should have a declaration similar to this:
You pass the adress of the two polygons A and B and the adress of a polygon where the result will be stored when done.
void PolygonUnion(POLYGON* PolyA, POLYGON* PolyB, POLYGON* PolyResult);
void PolygonIntersection(POLYGON* PolyA, POLYGON* PolyB, POLYGON* PolyResult);
Note that empty polygons (intersections of polygons that doesn't intersect) and multiple polygons (unions of polygons that doesn't intersect) are also valid solutions.
The functions should be able to handle convex polygons, but it's a plus if it can also handle concave polygons.
A convex polygon is a polygon where every point can "see" all other nodes. This means there are no lines that block their "sight". See the picture below and hopefully you'll understand.
The opposite of a convex polygon.
If you feel like doing some extra, you could also write additional functions like the Symmetric difference (functions like A XOR B) or the Relative Complement (Functions like A AND NOT B).