5 September 2016 in Cartography and Geographic Information Science
Origin-destination flow maps are often difficult to read due to overlapping flows. Cartographers have developed design principles in manual cartography for origin-destination flow maps to reduce overlaps and increase readability. These design principles are identified and documented using a quantitative content analysis of 97 geographic origin-destination flow maps without branching or merging flows. The effectiveness of selected design principles is verified in a user study with 215 participants. Findings show that (a) curved flows are more effective than straight flows, (b) arrows indicate direction more effectively than tapered line widths, and (c) flows between nodes are more effective than flows between areas. These findings, combined with results from user studies in graph drawing, conclude that effective and efficient origin-destination flow maps should be designed according to the following design principles: overlaps between flows are minimized; symmetric flows are preferred to asymmetric flows; longer flows are curved more than shorter or peripheral flows; acute angles between crossing flows are avoided; sharp bends in flow lines are avoided; flows do not pass under unconnected nodes; flows are radially distributed around nodes; flow direction is indicated with arrowheads; and flow width is scaled with represented quantity.
23 March 2017 in International Journal of Geographical Information Science
This paper introduces a force-directed layout method for creating origin-destination flow maps. Design principles derived from manual cartography and automated graph drawing to increase readability of flow maps and graph layouts are taken into account. The origin-destination flow maps produced with our algorithm show flows with quadratic Bézier curves that reduce flow-on-flow and flow-on-node overlaps, and avoid sharp or irregular bends in flow lines. A survey of expert cartographers found that flow maps created with our automated method are similar in quality to manually produced flow maps.
1 October 2015 in IEEE Transactions on Visualization and Computer Graphics
Three-dimensional symmetric tensor fields have a wide range of applications in solid and fluid mechanics. Recent advances in the (topological) analysis of 3D symmetric tensor fields focus on degenerate tensors which form curves. In this paper, we introduce a number of feature surfaces, such as neutral surfaces and traceless surfaces, into tensor field analysis, based on the notion of eigenvalue manifold. Neutral surfaces are the boundary between linear tensors and planar tensors, and the traceless surfaces are the boundary between tensors of positive traces and those of negative traces. Degenerate curves, neutral surfaces, and traceless surfaces together form a partition of the eigenvalue manifold, which provides a more complete tensor field analysis than degenerate curves alone. We also extract and visualize the isosurfaces of tensor modes, tensor isotropy, and tensor magnitude, which we have found useful for domain applications in fluid and solid mechanics. Extracting neutral and traceless surfaces using the Marching Tetrahedra method can cause the loss of geometric and topological details, which can lead to false physical interpretation. To robustly extract neutral surfaces and traceless surfaces, we develop a polynomial description of them which enables us to borrow techniques from algebraic surface extraction, a topic well-researched by the computer-aided design (CAD) community as well as the algebraic geometry community. In addition, we adapt the surface extraction technique, called A-patches, to improve the speed of finding degenerate curves. Finally, we apply our analysis to data from solid and fluid mechanics as well as scalar field analysis.
4 December 2023 in Computer Graphics Forum
The need to plan motions for agents with variable shape constraints such as under different formations appears in several virtual and real‐world applications of autonomous agents. In this work, we focus on planning and execution of formation‐aware paths for a group of agents traversing a cluttered environment. The proposed planning framework addresses the trade‐off between being able to enforce a preferable formation when traversing the corridors of the environment, versus accepting to switch to alternative formations requiring less clearance in order to utilize narrower corridors that can lead to a shorter overall path to the final destination. At the planning stage, this trade‐off is addressed with a multi‐layer graph annotated with per‐layer navigation costs and formation transition costs, where each layer represents one formation together with its specific clearance requirement. At the navigation stage, we introduce Corridor Shortest Path Maps (CSPMs), which produce a vector field for guiding agents along the solution corridor, ensuring unobstructed in‐formation navigation in cluttered environments, as well as group motion along lengthwise‐optimal paths in the solution corridor. We also present examples of how our multi‐layer planning framework can be applied to other types of multi‐modal planning problems.
16 May 2023 in Computer Animation and Virtual Worlds
This article introduces the new problem of planning spatially distributed lanes for supporting multi‐agent navigation applications in 3D environments. Our proposed approach computes the max‐flow of a 3D medial axis representation of the environment in order to globally compute collision‐free lanes exploring the entire free space of the volumetric scene. Our method addresses agent clearance and path dispersion in order to provide a comprehensive solution to globally compute lanes to be used by multiple agents in 3D environments. By selecting the desired lane dispersion our approach offers an intuitive and powerful way to explore variations in the computed collections of lanes. Dispersion is addressed with a combination of new techniques based on max flow computation, clearance‐based path separation, and adaptive shortcut‐based smoothing.