 |
|
|
|
|
There exist a vast number of algorithms to solve this problem; some of them
will be presented here.
These algorithms can be tried out in an applet to experience the constructed
polygon shapes. This applet should have been started by now and be visible in
it's own frame.
In the lower part of this page one can get a description of the applet.
A quite simple algorithm that constructs polygons which evince a half-convex shape (in this case a convex "bottom", hence the name).
The idea for this algorithm comes from
[PoPS].
First, the two extreme points regarding x coordinate are determined, that is the two points with lowest resp. highest x value. These points are connected by an imaginary line, so the point set is divided into an upper and a lower half.
Now the convex hull of the lower half is computed, and the imaginary line is removed again. The polygon's convex bottom has already been computed now.
All remaining points that do not lie on the hull are now sorted from left to right by x coordinate and connected in this order. Finally, the two extreme points are connected to the convex bottom.
The such constructed polygon typically evince - besides the convex bottom - a "zig-zag-pattern" of edges above the bottom.
Besides ConvexBottom, variants with a convex "roof" or a convex left or
right side are also imaginable naturally, with same time complexity.
SpacePartitioning
Runtime: O(n2) in worst case; with balanced recursion
O(n log n)
The point set is recursively divided into two sets each so that their convex hulls are disjoint and have only one edge in common. This way, in best case there are log(n) recursions. When a subset consists only of two points, the recursion terminates with the new polygon edge.
Computation details can be looked up in [AH96].
The created polygons are commonly quite much ramified and complex; there result both convex shapes and such that are similar to those created by SteadyGrowth.
SteadyGrowth
Runtime: quadratic in O(n2)
SteadyGrowth (taken from [AH96]) creates a simple polygon by successively extending a start polygon constructed from a subset until all point set points are contained in the polygon.
For the start polygon three points from the point set are chosen in such a way that
the convex hull of these three points does not contain any further points.
In each of the following iteration steps a point s is chosen in such a way that by appending s to the polygon it's convex hull again does not contain any further points of the point set. Then an edge (u, v) of the polygon that is completely visible from s is searched and replaced by the chain (u, s, v). This way the polygon is
extended with the point s.
SteadyGrowth typically yields polygons that spread from a center over two to three directions and thereby are very entangled.
TwoOptMoves
Runtime: O(n4)
With 2-opt Moves [AH96] describe - in short words - an algorithm that repeatedly replaces crossing edges in a random polygon (as it is constructed e.g. by Random) until a simple polygon is created.
As visible in the figure, a pair of crossing edges (s, t), (u, v) is searched and replaced by e.g. the pair (s, v), (u, t) to remove the intersection. According to [AH96], a maximum of O(n3) such replacements are performed, hence the high runtime complexity.
The created polygons are strongly ramified at sufficiently high point number.
It's a particular feature of this algorithm that every possible polygon can be constructed with respect to the given point set.
TwoPeasants
Runtime: O(n log n)
An algorithm with a strange name that - according to [PoPS] - got it's name after the way that is used in rural italy to fence pastures...
Similar to ConvexBottom, the points with lowest resp. highest x coordinate are determined und connected by an imaginary line first to build an upper and lower half of the point set. The next steps are as follows:
First of all, the upper half is regarded; beginning with the left extreme point, the actual point is connected with the closest point at a time while not crossing the imaginary line, until the right extreme point is reached.
Then, analogically, from right to left the lower half is traversed, until the left extreme point is reached again.
Generally, this way one gets a quite "balanced" simple polygon. The algorithm
is similar to the intuitive way a human being would connect a point set to a
simple polygon with pen and paper.
Random
Runtime: linear in O(n)
This most simple algorithm is depicted here only for reasons of completeness.
The point set is randomly traversed and the previous point is connected with the currently chosen point. After completion, the polygon is closed.
A closed polygon is constructed, but it can contain crossing edges.
The start button opens a separate frame containing the RandomPolygon2Tool, actually a part of a polygon editor that was programmed for another project (PolyRobot). Besides pure visualization, this tool provides the possibility to import a constructed polygon into the editor (by button Import); naturally, this is not possible here.
Below the import button there are six different buttons that are labelled with one of the algorithms each and create a polygon of the corresponding type.
The display area in the middle shows the constructed polygon. The three zoom buttons above can be used to zoom view in or out.
Placed below the algorithm buttons are the settings for point set size interval and polygon size:
The size interval specifies how many random points are created; the number of points
lies in the interval range.
The polygon size specifies maximal values for polygon width and height.
