Method and apparatus for regularizing building footprints using taxicab distance

An apparatus comprising:

• at least one processor;
• and
• at least one memory including computer program code for one or more programs,
• the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
• designate a vertex of a polygon as an initial vertex of a regularized polygon corresponding to the polygon;
• generate an edge from the initial vertex to a next vertex of the polygon to add to the regularized polygon based on determining that the edge can connect to the next vertex along at least one reference direction or at least one reference angle;
• add a new vertex to the regularized polygon based on determining that the edge cannot connect to the next vertex along the at least one reference direction or the at least one reference angle, wherein the edge is generated to connect the initial vertex to the new vertex along the at least one reference direction or the at least one reference angle, another edge is generated to connect the new vertex to the next vertex along the at least one reference direction or the at least one reference angle, and the edge and the another edge are added to the regularized polygon;
• and
• traverse to another next vertex of the polygon to add another edge, another new vertex, or a combination thereof to the regularized polygon,
• wherein the another edge, the another new vertex, or a combination thereof follow along the at least one reference direction or the at least one reference angle.

A non-transitory computer-readable storage medium, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform:

• rotating a polygon representing a building footprint based on a dominant orientation of the polygon, external map features, or a combination thereof, wherein the rotating aligns the polygon with a reference direction, a reference angle, or a combination thereof;
• converting the initial polygon to a regularized polygon by generating a regularized edge between each pair of vertices of the initial polygon, wherein the regularized edge follows along the reference direction, the reference angle, or a combination thereof;
• and
• rotating the regularized polygon to an original orientation of the polygon after the regularized polygon is generated.