If you follow all my recommendations from my comments:
- Distinguish between intersection and touching points
- Keep a link between the two equivalents of the intersection points in the two polygons
The solution for the union will be:
- Consider only outer, touching and intersection points
- Make sure the points in the two polygons are ordered in different direction (one of the sets is in clockwise direction, the other one in counter-clockwise)
- Start from random point in any of the two polygons.
- For every vertex in any of the two polygons keep if you have visited it
- Every time you encounter an intersection point keep on traversing from the next to follow point in the other polygon after the equivalent of the intersection point.
- If you come back to the point you started from this closes one of the components of the join of the two polygons. If not all vertices were traversed repeat the whole of it from any unvisited vertex.
- In the end calculate the area of all the polygons you have found. The largest in area will be the real union. The rest will be holes in the union.
The solution for the join will be:
- Consider only inner and intersection points
- Make sure the points in the two polygons are ordered in the same direction
- Start from random point in any of the two polygons.
- For every vertex in any of the two polygons keep if you have visited it
- Every time you encounter an intersection point keep on traversing from the next to follow point in the other polygon after the equivalent of the intersection point.
- If you come back to the point you started from this closes one of the components of the join of the two polygons. If not all vertices were traversed repeat the whole of it from any unvisited vertex.
EDIT: As I already mentioned, I have the god feeling my approach with the polygon orientation needs to be revised. However, when searching through the web I found a description of algorithm that might do the work for you: The Vatti clipping algorithm
EDIT2 One more article describing such clipping algorithm.