Algorithms for Urban Analysis

[2] J.-H. Haunert, D. Schmidt, and M. Schmidt. Anonymization via clustering of locations in road networks (short paper). In Proc. 11th International Conference on Geographic Information Science (GIScience' 21). 2021. doi:10.25436/E2CC7P

A raw trajectory is typically represented as a time-stamped sequence of location measurements. To enable trajectory-based applications, the raw trajectories need to be processed appropriately. This typically includes map matching, which identifies the path in the network that most likely led to the given movement sequence. Map matching helps to reduce noise that stems, e.g., from sensor inaccuracies and enables further network-based analysis. Map matching is specifically challenging if the underlying road network is incomplete [3] or the trajectories are not entirely restricted to the underlying network [4].

[3] J.-H. Haunert and B. Budig. An algorithm for map matching given incomplete road data. In Proc. 20th International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL' 12). New York, NY, USA, 510–513, 2012. doi:10.1145/2424321.2424402

[4] Timon Behr, Thomas C. van Dijk, Axel Forsch, Jan-Henrik Haunert, and Sabine Storandt. Map matching for semi-restricted trajectories. In Proc. 11th International Conference on Geographic Information Science (GIScience' 21). 2021. doi:10.4230/LIPIcs.GIScience.2021.II.12

Route planning tools play an essential role in modern mobility. They are not only used for commuting, i.e., to find the best path from one location to another but also for leisure activities, such as scenic cycling round trips that start and end at the same location. For both applications, it is crucial to choose the optimization objective, i.e., the definition of "best," such that it reflects a user's preferences. This preference can be inferred from the trajectory datasets using trajectory mining approaches [5-7].

[5] J. Oehrlein, A. Förster, D. Schunck, Y. Dehbi, R. Roscher, and J.-H. Haunert. Inferring routing preferences of bicyclists from sparse sets of trajectories. In volume IV-4/W7 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. 3rd International Conference on Smart Data and Smart Cities, pages 107-114. 2018

[6] J. Oehrlein, A. Förster, D. Schunck, Y. Dehbi, R. Roscher, and J.-H. Haunert. Inferring routing preferences of bicyclists from sparse sets of trajectories. In volume IV-4/W7 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. 3rd International Conference on Smart Data and Smart Cities, pages 107-114. 2018.

[7] Axel Forsch, Johannes Oehrlein, Benjamin Niedermann, and Jan-Henrik Haunert. Inferring routing preferences from user-generated trajectories using a compression criterion. Journal of Spatial Information Science, 0(0):0, 2023. Accepted for publication on 15 Mar 2023.

The results of the processing steps are often hard to interpret for non-expert users, so appropriate visualizations are needed to improve the accessibility of the results. For example, isochrone maps display the reachable area from a given starting point within a given travel time. We developed algorithms for the automatic generation of isochrones in multimodal transportation networks [8], allowing for easy analysis of deficits in the network. The concept of isochrones can be adopted for routing preferences to show how accessible a region is for specific routing profiles.

[8] Axel Forsch, Youness Dehbi, Benjamin Niedermann, Johannes Oehrlein, Peter Rottmann, and Jan-Henrik Haunert. Multimodal travel-time maps with formally correct and schematic isochrones. Transactions in GIS, 25(6):3233-3256, 2021.

In the context of the generation of city and building models, terrestrial laser scanning has become more and more popular. However, the planning of the surveying campaign is a crucial task since the selection of the standpoints heavily influences the quality of the resulting point cloud, e.g. if a complete scan of the whole scenery has been performed and the individual scans can be registered with sufficient quality.  In addition, for economic reasons, one would like to use as few standpoints as possible for the measurement. Therefore, our algorithms to find the minimum number of standpoints while guaranteeing a full coverage and a successful subsequent software-based registration using Mixed Integer Linear Programming (MILP) offer great potential, for static laser scanning [9] as well as for stop-and-go scanning including an optimal route planning [10].

[9] Youness Dehbi, Johannes Leonhardt, Johannes Oehrlein, and Jan-Henrik Haunert. Optimal scan planning with enforced network connectivity for the acquisition of three-dimensional indoor models. ISPRS Journal of Photogrammetry and Remote Sensing, 180:103-116, 2021.

[10] J. Knechtel, L. Klingbeil, J.-H. Haunert, and Y. Dehbi. Optimal position and path planning for stop-and-go laserscanning for the acquisition of 3d building models. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, V-4-2022:129-136, 2022.
 

Building Information Models do not only consist of the general structure of the underlying building, i.e. walls and windows, but also of infrastructure information which is mostly hidden in the wall, i.e. the electric wiring. Enriching a model with such information is challenging due to the high measurement overhead since mostly point-wise measurements, e.g. with a wire detector, are necessary. Utilizing norms and standards, Mixed Integer Linear Programming (MILP) can be applied to generate a hypothesis of the electric lines only based on easily observable structures like light switches and sockets. Furthermore, we developed and tested different reasoning strategies to unambiguously confirm this hypothesis with as few measurements as possible [11].

[11] Y. Dehbi, J. Knechtel, B. Niedermann, and J.-H. Haunert. Incremental constraint-based reasoning for estimating as-built electric line routing in buildings. Automation in Construction, 143:104571, 2022.