IDEA: Polygon unions and intersections

This is a discussion on IDEA: Polygon unions and intersections within the Contests Board forums, part of the Community Boards category; Imagine two polygons A and B. A polygon is a set amount of points connected to each other where each ...

  1. #1
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145

    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.

    Union:
    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.

    Intersection:
    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:
    Code:
    void PolygonUnion(POLYGON* PolyA, POLYGON* PolyB, POLYGON* PolyResult);
    void PolygonIntersection(POLYGON* PolyA, POLYGON* PolyB, POLYGON* PolyResult);
    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.

    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.

    Convex:
    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.

    Concave:
    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).
    Attached Images Attached Images  
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  2. #2
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    This is actually a really cool idea. I thought it was going to suck when I started to read it, but then I started to realize how it could be done. However, what is the area of the union of two polygons which do not intersect? 0, or A1+A2? We'd also need to have the POLYGON struct defined.
    Away.

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by blackrat364
    However, what is the area of the union of two polygons which do not intersect? 0, or A1+A2?
    A1+A2

    It would also be easier to test the functions if we had some kind of GUI. A simple one that only draws lines would be enough.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Well, it wouldn't be *that* bad to work out a data set on paper and then just apply that data to all entries. It's not *that* bad to figure out what the answers should be, either. I think.
    Away.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. intersections?
    By InvariantLoop in forum C Programming
    Replies: 2
    Last Post: 02-02-2005, 05:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21