Construction,Planning And Expression Of 3D Route Graph For Building

Wayfinding is a necessarily basic issue in people's daily life. The problem of wayfinding can be divieded into two kinds according to different application environments: indoors and outdoors. A typical application of outdoor wayfinding is to find paths in a traffic system, i.e. electronic maps based on web and GPS navigation for cars. Outdoor wayfinding problem had attracted more people's attention. However, indoor wayfinding problems are often ignored by people. In fact, the efficient of finding a path in a building is very low for many people, especially for these people who are in an unfamiliar building environment. As a result, high efficient indoor wayfinding becames a research focus now. The emphasis of this paper is just to find a method of how to help people efficiently find a path in indoor environment especially in a tall building. The main contents of this paper are:1) Automatically generating route model (graph). In this section, the process of how to automatically generating route model is introduced. First, hallways of one floor are constructed by utilizing image thinning algorithm base on mathematical morphology and characteristic point detecting algorithm. Then we can connect entities nodes to these hallways. A route model of one floor can be constructed by this method. At last we link every two neighboring floors by connecting the portal nodes like stairs nodes and elevator nodes. Consequently, a three-dimensional route model has been eventually constrcted. The route model is a weighted graph which is composed of nodes and arcs. The route graph can be applied in many domains according to different weight definations. For example, it can be applied in firefighting systems. The weights are able to represent the cost of passing some arcs. In the case, the weight is decieded by fire conditions, temperature, and smoke density.2) Route planning. First, a method of updating weights is proposed in this section. These weights' values can be figured out by synthesizing the sensor data which are derived from real sensor devices. These weights can well reflect the runtime environment of building. Then we introduced heuristic search and implemented the heuristic A* algorithm to find the optimal path. At last, a mathematical model of making an evacuation plan is proposed. The mathematical model use time-expanded network and linear programming of min-cost flow to calculate the evacuation plan.3) Route expression. Route expression includes graphic route expression and natural language route expression. Graphic route expression is to display the retrieved optimal path in 3D building scene. In 3D building scene, an interactive interface which provides the function of selecting a start entity (node) and a destination entity (node) is provided. We mainly use a transformation from two-dimensional screen coordinate to three-dimensional space coordinate and pick up a three-dimensional object in an interactive system. At last, we transform the optimal path which is composed of node and arcs into natural language route description.