CENTER LINE GENERATION DEVICE, NETWORK DATA GENERATION SYSTEM AND PROGRAM

A centerline for generating network data of an indoor space can be generated while limiting the amount of calculation. Points where first straight lines and second straight lines constituting centerlines meet are created using re-entrant vertices (Step 1). The points created in Step 1 are connected by lines (Step 2). Connection lines corresponding to the longest sides are repeatedly deleted from closed polygons defined by the connection lines obtained in Step 2 until no closed polygons are left (Step 3). Each vertex of the connection lines obtained in Step 3 is connected to a farthest center point on the perimeter of the shape of the passage if there is such a farthest center point to which the vertex can be connected without touching the perimeter and without crossing other connection lines (Step 4).