How to smooth connected polygons without losing their connectivity?

Question

I have a number of polygons which covers some rectangle.

Each polygons is associated with some type (on the image accessible by link below it's shown by a color).

I need to smooth polygons and save the topology.

(i.e. we should to consider the following constraints:

1. The union of the polygons is equal to some rectangle
2. The intersection of any two distinct polygons is empty

(it's definition of the partition of a set))

ADDED

The egdes shouldn't be straight, on the contrary I need get smooth edges of polygons. But edges should remain connected together (i.e. without gaps and overlaps)

Example image

Answer 1

Here's a fragment of an answer.

One way to ensure that gaps between polygons don't arise is to devise your data structures such that polygons which have a common edge actually share an edge -- that is your data structures contain one edge which is associated with two polygons. This would also implement the topological relationship between polygons which share an edge.

I expect that this answer is inadequate, but take the hints you've already been given and clarify your question, explain in more detail what you have and what you want.