LEDA, a Platform for Combinatorial and Geometric Computing:Visualization

By -

Visualization

Visualization and animation of programs is very important for the understanding, presentation, and debugging of algorithms (see Chapter 44).

Leda provides two powerful tools

for interactive visualization and animation of data structures and algorithms:

Graph Win

The Graph Win data type (see [27], chapter 12) combines the graph and the window data type. An object of type Graph Win (short: a Graph Win) is a window, a graph, and a drawing of the graph, all at once. The graph and its drawing can be modified either by mouse operations or by running a graph algorithm on the graph. The Graph Win data type can be used to:

• construct and display graphs,

• visualize graphs and the results of graph algorithms,

• write interactive demos for graph algorithms,

image

FIGURE 41.1: A Graph Win. The display part of the window shows a graph G and the panel part of the window features the default menu of a Graph Win. G can be edited interactively, e.g., nodes and edges can be added, deleted, and moved around. It is also possible to run graph algorithms on G and to display their result or to animate their execution.

• animate graph algorithms.

All demos and animations of graph algorithms in Leda are based on Graph Win, many of the drawings in the Leda book ([27]) have been made with Graph Win, and many of the geometry demos in Leda have a Graph Win button that allows us to view the graph structure underlying a geometric object.

Graph Win can easily be used in programs for constructing, displaying and manipulating graphs and for animating and debugging graph algorithms. It offers both a programming and an interactive interface, most applications use both of them.

Geo Win

Geo Win ([23]) is a generic tool for the interactive visualization of geometric algorithms. Geo Win is implemented as a C++data type. It provides support for a number of programming techniques which have shown to be very useful for the visualization and animation of algorithms. The animations use smooth transitions to show the result of geometric algorithms on dynamic user-manipulated input objects, e.g., the Voronoi diagram of a set of moving points or the result of a sweep algorithm that is controlled by dragging the sweep line with the mouse (see Figure 41.2).

clip_image004

FIGURE 41.2: GeoWin animating Fortune’s Sweep Algorithm.

A Geo Win maintains one or more geometric scenes. A geometric scene is a collection of geometric objects of the same type. A collection is simply either a standard C++-list (STL-list) or a Leda-list of objects. Geo Win requires that the objects provide a certain functionality, such as stream input and output, basic geometric transformations, drawing and input in a Leda window. A precise definition of the required operations can be found in the manual pages [11]. Geo Win can be used for any collection of basic geometric objects (geometry kernel) fulfilling these requirements.

The visualization of a scene is controlled by a number of attributes, such as color, line width, line style, etc. A scene can be subject to user interaction and it may be defined from other scenes by means of an algorithm (a C++ function). In the latter case the scene (also called result scene) may be recomputed whenever one of the scenes on which it depends is modified. There are three main modes for re-computation: user-driven, continuous, and event-driven.

Geo Win has both an interactive and a programming interface. The interactive interface supports the interactive manipulation of input scenes, the change of geometric attributes, and the selection of scenes for visualization.

Comments

Post a Comment

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

By -
Introduction Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for un d e rstanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code. As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furt
Read more

Collision Detection:Penetration Depth Computation

By -
Image
Penetration Depth Computation In this section, we give a brief overview of penetration depth (PD) computation algorithms between convex polytopes and general polyhedral models. The PD of two inter-penetrating objects A and B is defined as the minimum translation distance that one object undergoes to make the interiors of A and B disjoint. It can be also defined in terms of the TCSO. When two objects are overlapping, the origin of the Minkowski sum of A and − B is contained inside the TCSO. The penetration depth corresponds to the minimum distance from the origin to the surface of TCSO [18]. PD computation is often used in motion planning [37], contact resolution for dynamic simulation [38, 39] and force computation in haptic rendering [40]. For example, computation of dynamic response in penalty-based methods often needs to perform PD queries for imposing the non-penetration constraint for rigid body simulation. In addition, many applications, such as motion planning and dynamic simula
Read more

Concurrent Data Structures:Linked Lists

By -
Linked Lists Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a se t ; if a data value is associated with each key, we have a dic tionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees. Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is ha nd-over-hand locking (sometimes called l o c k coupling ) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventin
Read more