For example I have rectangular polygon (4 vertices). I want to add mid-point on each line of the polygon, so in total now I have 8 vertices. And from them I want to build new polygon who will have same exterior footprint, but have 8 vertices:

What I did and it's not working (I want to do this on every polygon in my buildings.shp): (pseudo algorithm, I'm working with "WITH... AS")

1. Get all original vertices (The 4 black) ST_DumpPoints on buildings twice(!)

   Prepare borders of the multi-polygon buildings as line-strings in order to apply ST_Line_Interpolate_Point-

2. All possible lines between same polygon vertices: ST_MakeLine(points1.geom, points2.geom) WHERE (points1.path <> points2.path) AND (points1.id = points2.id)

3. Buildings borders: ST_ExteriorRing(the_geom) ON (ST_Dump(build.geom)).geom AS the_geom

4. From lines @ 2 select only the border lines: St_touches(build.geom, lines.geom) AND St_touches(border.geom, lines.geom)=false AND lines.id = build.id AND lines.id = border.id --all points from same building, all lines from same building have same id belonging to the building

5. Get the mid points: ST_Line_Interpolate_Point(border_lines.geom, 0.5) (green points)

6. UNION points @ 1 and points @ 5

Now the problem is that I don't have any order in the points @ 6 so it's almost impossible to use ST_MakePolygon, and tricks with ST_ConcaveHull & ST_ConvexHull also not working because they ignores the mid point and eventually I return to where I started.