ComputationalGeometry - Algoviz Wiki

Works

Yes

Description

Demonstration of the Weiler-Atherton clipping algorithm for two polygons. User first enters two polygons by specifying the vertices on the screen, and then the AV walks through the steps of the algorithm. While it presents as a Java applet, its actually written in Jython.

Evaluation

Entering reasonably complex polygons is easy. The step-by-step walkthrough of the algorithm is quite clear.

Step Control; User Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2008-06-30

Last Visited

2008-06-30

Last Updated

2008-05-07

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

AlViE - Closest Pair

Recommendation

Recommended

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Demonstrates a divide and conquer algorithm for computing the closest pair of points within a specified set of points in the Euclidean plane. C-like pseudo-code is included. The visualization tries to mimic as far as possible the animation of the algorithm used by Prof. Ottmann at the University of Freiburg. The visualization shows both the horizontal and the vertical strips used during the merge operation and it uses color to distinguish nodes within a vertical/horizontal strip from nodes out of the strip. Colors are also used to emphasize which nodes and distances are currently under examination. The user can go backward and forward, can zoom in and zoom out, and can set bookmarks. This visualization is easily configurable and localizable.

Evaluation

Simple-to-use user interface for walking through the example, since a good example is already provided with the algorithm. Simply open up the AV (see directions below) and step through the example with pseudo-code. Not clear if one can add data for this particular AV (you can for other ALVIE AVs). As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors indicating the current points being considered and an indication of the strip of area within the current maximum distance.

Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

See http://alvie.algoritmica.org/alvie3/quickstart. Download and unzip the ALVIE system from the website. Double click on the .jar file. In the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms. Select 'Closest Pair of Points'. Once selected, click OK and step through the AV with the arrow icons (in the middle of the toolbar).

First Visited

2009-07-20

Last Visited

2009-07-20

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/DouglasPeucker.html

Edit

You may edit this entry if you have an account.

Trakla - Douglas-Peucker Line Simplification

Recommendation

Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

User works through the line thinning algorithm to demonstrate proficiency

Evaluation

Surprisingly, its not the exercise that makes this AV, even though the exercise aspect is usually the strong point for Trakla AVs. In this case, stepping through the "model answer" for an example does a really nice job of getting the algorithm across. Unfortunately, the exercise itself is hard to figure out how to get the mechanics right.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/IntersectionsLineSweep.html

Edit

You may edit this entry if you have an account.

Trakla - Line Sweep

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

Presents an exercise on the line sweep algorithm for locating intersections among a collection of line segments.

Evaluation

Somewhat difficult to follow what the user should do to work the exercise. Putting the subroutines into separate tabs makes it harder to follow. The Model Answer step-through could use some work to be a better presentation of the algorithm.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-30

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/VisibleVertices.html

Edit

You may edit this entry if you have an account.

Trakla - Visibility with Rotational Sweep

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

Presents an exercise for determining visible vertices from a collection of polygons

Evaluation

Somewhat difficult to follow what the user should do to work the exercise. Putting the subroutines into separate tabs makes it harder to follow. The Model Answer step-through is quite good, and is an effective way of illustrating the algorithm.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-30

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/PointInPolygon.html

Edit

You may edit this entry if you have an account.

Trakla - Point in Polygon

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

User answers some questions about whether points are in the polygon or not

Evaluation

This isn't really an AV, more a quiz. And what you see about the point-in-polygon algorithm is pretty obvious (count intersections).

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/ClosestPairOfPoints.html

Edit

You may edit this entry if you have an account.

Trakla - Closest Pair of Points

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

User works through the algorithm, setting various processing variables. There is also a step-through for the suggested answer that illustrates the algorithm

Evaluation

This AV isn't easy to understand, and does not do a good job of getting the algorithm across. The instructions for the exercise part are unclear. Even the step-through doesn't make the algorithm clear (granted the algorithm is fairly complex).

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/ExpandingWave.html

Edit

You may edit this entry if you have an account.

Trakla - Delaunay Triangulation

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Works

Yes

Description

Presentation and exercise for computing the Delaunay triangulation for a collection of points using the Expanding Wave method.

Evaluation

The exercise is difficult to comprehend what the user is supposed to do. The Model Answer step-through presentation does not do a good job of illustrating the algorithm

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-30

Last Visited

2008-07-30

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://donar.umiacs.umd.edu/quadtree/points/voronoi.html

Edit

You may edit this entry if you have an account.

Maryland Voronoi Diagram

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Frantisek Brabec; Hanan Samet

Institution

University of Maryland

Project

Maryland Spatial Index Demos:

Works

Yes

Description

This tool can be used to visualize a number of different decompositions. The main visualization window is zoomable and the user can optionally overlay it with a grid. There are a number of operations that can be performed. Users can insert, move and delete points that define the structure. Shows the Voronoi diagram associated with (user-entered) data points. Can also show the corresponding Delaunay triangulation.

Evaluation

Easy to enter/delete points (just point and click). No explanations of what is happening, so user will learn what the structure is, but not how it works.

User Data

Lecture Aid; Self Study; Debugging

Screenshots

Videos

References

First Visited

2006-09-21

Last Visited

2008-07-06

Last Updated

2003-02-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://donar.umiacs.umd.edu/quadtree/points/delaunay.html

Edit

You may edit this entry if you have an account.

Maryland Delaunay Triangulation

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Frantisek Brabec; Hanan Samet

Institution

University of Maryland

Project

Maryland Spatial Index Demos:

Works

Yes

Description

This tool can be used to visualize a number of different decompositions. The main visualization window is zoomable and the user can optionally overlay it with a grid. There are a number of operations that can be performed. Users can insert, move and delete points that define the structure. Shows the Delaunay triangulation associated with (user-entered) data points.

Evaluation

Easy to enter/delete points (just point and click). No explanations of what is happening, so user will learn what the structure is, but not how it works. Maryland's Voronoi diagram AV also shows the Delaunay triangulation, so this AV is rather redundant. Users should just look at the Voronoi diagram AV and turn on the Delaunay overlay. That will give more insight as to what is going on.

User Data

Lecture Aid; Self Study; Debugging

Screenshots

Videos

References

First Visited

2006-09-21

Last Visited

2008-07-06

Last Updated

2003-02-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://loki.cs.brown.edu:8080/pages/ConvexHull.html

Edit

You may edit this entry if you have an account.

(FIXME) BrownHull

Recommendation

Unrated

Link

Delivery Method

License

Language

English

Author

Institution

Brown University

Project

Mocha

Works

Unavailable

Description

Evaluation

Screenshots

Videos

References

First Visited

Last Visited

2007-09-24

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.princeton.edu/courses/archive/spr09/cos226/demo/ah/ConvexHull.html

Edit

You may edit this entry if you have an account.

Gawain Convex Hull

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Alejo Hausner

Institution

Princeton University

Project

Works

Yes

Description

An intro page is given that describes what Convex Hull is, with links to three AVs showing algorithms to implement Convex Hull: Jarvis' March (gift wrapping), Graham's scan, and a quicksort-like "Quick hull" algorithm. Each displays a set of (random) points and shows, step by step, processing appropriate to that algorithm. For example, the Graham's scan shows the search for the lowest point (pivot), sorting the other points in order of angle from the pivot and forming the convex hull by traversing the polygon constructed from these points. User interaction is limited to starting and pausing the animation.

Evaluation

The visual representations in the animation (points, polygon edges in different colours, slanted lines for angles) are mostly obvious and clear, but rely on colour to distinguish different points and edges (for example, lines in the initial polygon from the convex hull that is being built). The animation proceeds quite quickly (and lacks speed control and stepping), making it hard to observe the behaviour of the algorithm on the level of individual steps. The supporting text is a brief summary of the algorithm, which is mostly adequate but leaves out details of the backtracking in the final phase. The animation itself does not explain the decisions made by the algorithm in the final phase at all, it just adds and removes edges from the view, making it hard to see why some points are added to the convex hull and some are not. As such, the animation can be used to get an overview of the algorithm, but a detailed understanding is hard to get and exploration is not supported.

Animation; Step Control

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

From the link given above, follow the links to the page for each Convex Hull algorithm. These are applets that load automatically. Just hit "Run" or "Step" to advance the algorithm. Hit "Init" to restart with a new set of random points.

First Visited

2007-09-22

Last Visited

2009-08-17

Last Updated

1997-05-30

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.auckland.ac.nz/software/AlgAnim/convex_hull.html#convex_anim

Edit

You may edit this entry if you have an account.

Auckland - Convex Hull

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

KyungTae Kim; JiMo Jung; John Morris

Institution

University of Auckland

Project

Morris' Collection

Works

Yes

Description

Two separate AVs with similarities in layout. They both show a field that is filled with points. These points are then connected so that the there will be the smallest possible polygon which encloses each point. In the process of comparing coordinates and connecting the points the two applications have a bit different approach. There is possibility to control actions with buttons Stop, Run, Step and Skip. Unfortunately the command for viewing source code doesn't work.

Evaluation

The first application by KyungTae Kim provides a fixed set of points that will always appear in the same order when launching the program. Each step will pop out a small comment beside the active points to explain the process. Beside the graph the names of the points chosen currently for the polygon are updated step by step to a list. The second application by JiMo Jung offers a randomly created set of points every time the program is launched. During the steps of the process there appears a list of coordinates of the points that have been checked and those that belong currently to the polygon. Further written explanations about the steps in the process are not available. When evaluating both applications the first one benefits from having more explanations whereas the second one benefits from having a randomly generated example. A downside for both is that the user is not in active interaction with the process of algorithm. All in all, the visualizations provided in these two applications give a possibility to see step by step the building of a convex hull. The first one with more detailed explanations is more suitable for an independent learner and the second one offers more alternative examples. The visualizations are more about showing the process that making user to actively build an answer.

Step Control; Animation; Canned Data

Lecture Aid

Screenshots

Videos

References

First Visited

2007-10-03

Last Visited

2008-07-17

Last Updated

2004

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cosc.canterbury.ac.nz/mukundan/cgeo/Sweep1.html

Edit

You may edit this entry if you have an account.

Java Applets Centre - Closest Points

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. Mukundan

Institution

University of Canterbury

Project

Java Applets Centre

Works

Yes

Description

Presents a plane-sweep algorithm for finding the closest pair of points within a 2-D collection of points. User clicks on the screen to set a collect. Then a vertical line sweeps across the 2-D space, trailing a bounding box that shows the distance of the closest pair found so far.

Evaluation

This AV can't stand on its own. It has to come in the context of a separate explanation for the particular algorithm being illustrated.

Animation Only; User Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-21

Last Updated

2006

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cosc.canterbury.ac.nz/mukundan/cgeo/applcgeo.html

Edit

You may edit this entry if you have an account.

Java Applets Centre - Convex Hull

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. Mukundan

Institution

University of Canterbury

Project

Java Applets Centre

Works

Yes

Description

A collection of four AVs, showing convex hull algorithms named "Insertion Hull," "Gift Wrap," Graham's Scan," and "Quick Hull." The user clicks on the screen to set a collection of points. Then the algorithms are set to run, drawing lines as the algorithm progresses.

Evaluation

Unless you already are familiar with the algorithms, this won't make much sense. Even if you are familiar with the algorithms, you won't learn much from looking at the lines wrap around the boxes. You might gain a little appreciation for Graham's Scan from watching the AV, but only if you could control the pacing so you could absorb what is happening. The others are pretty much a mystery.

Animation Only; User Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-21

Last Updated

2006

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.eecs.wsu.edu/~holder/courses/cse2320/lectures/applets/convexhull/ch.html

Edit

You may edit this entry if you have an account.

UTAHull

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Jeff So

Institution

University of Texas at Arlington

Project

Works

Yes

Description

Animates two algorithms for the Convex Hull problem: a brute-force algorithm and Quick Hull. In both cases the user selects the input (a set of points) graphically and starts the animation at one of three speeds. The visualization contains the points, edges in the convex hull and edges that are being considered (the point or edge currently under consideration is highlighted in red).

Evaluation

According to the web page, the "purpose is to compare the speed and techniques of each algorithm in finding the hull", not to aid in understanding how the algorithm works. Therefore, it is hardly surprising that there are no explanations of what the algorithm is doing, and even on the slowest speed, the Quick Hull algorithm runs by in a blur after the initial sweeps through the full set of points. The stated purpose also explains why the animation mostly visualizes the time-consuming scanning through points one at a time looking for the left- and rightmost points or the point farthest from chosen chord, and does not visualize the partitioning of the set of points at all. The applet does have sound, but as it consists solely of a "plop" for every event, it is of little use.

Screenshots

Videos

References

First Visited

2007-09-26

Last Visited

2007-09-26

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://loki.cs.brown.edu:8080/pages/Delaunay.html

Edit

You may edit this entry if you have an account.

BrownDelaunay

Recommendation

Unrated

Link

Delivery Method

License

Language

English

Author

Institution

Brown University

Project

Mocha

Works

Unavailable

Description

Evaluation

Screenshots

Videos

References

First Visited

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://loki.cs.brown.edu:8080/pages/Voronoi.html

Edit

You may edit this entry if you have an account.

(FIXME) BrownVoronoi

Recommendation

Unrated

Link

Delivery Method

License

Language

English

Author

Institution

Brown University

Project

Mocha

Works

Unavailable

Description

Evaluation

Screenshots

Videos

References

First Visited

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

AlViE - Nearest Neighbor

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Walkthrough showing an algorithm to compute the nearest neighbor to a point from a collection of points.

Evaluation

Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/nearestNeighbor.swf

Lecture Aid; Self Study

Screenshots

Videos

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which select the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic