Home | Bookmarks | Papers | Blog |

This applet demonstrate how to compute various really interesting properties of a point set in the plane. In particular:

**Diameter**

Compute the two points of our set that their distance is maximal.**Weak Diameters**

Compute all the pair of points in the set, such that the two lines penpendicular to the segment connecting the points also contains the whole set of points (strange, but...).**Minimum Area**

Compute the minimum area rectangle that contains all the points**Minimum Circumference Rectangle**

Compute the rectangle with minimum Circumference (i.e. perimeter) rectangle that contains all the points.**Minimum Width**

Find the two closest parallel lines that contains the set.

G.T. Toussaint,Solving geometric problems with the rotating calipers,
In *Proc. IEEE MELECON '83*, A10.02/1-4, 1983.

Now, we'll check all of the antipodal pairs of points ( O(n) ). For each pair we'll find the distance between the two points, and so we'll find the maximum distance. We go through the pairs in the following way:

- The first pair will consist of the leftmost and the rightmost points. We draw two vertical lines thru them.
- Now, at each step, we rotate the parallel lines in the minimal angle which changes the pair of antipodal points that are defined by the lines.
- We finish when we complete a whole round.

The minimum width is the distance between the closest parallel
lines between which all of the point are placed.
To find the minimal width, we'll go through a sequence
of pairs of parallel lines the hold all of the points between them. In
each pair, one of the lines *must* coincide with a polygon edge. The
other line will be the most distant line that still touches the polygon
(There are at most n pairs).

- For each pair, we'll find the distance between the two lines, and the width is the minimal distance.
- We'll find the pairs in the following way:
- The first pair will consist of two vertical lines that go thru the most left and the most right points.
- Then, for each pair, (exactly like in the diameter) we rotate the two parallel lines in the angle that move one line to lie on a new edge.

By computing a formula, deriving and finding the minimum, one can prove that the minimum rects will always have at least one side that lies on a polygon edge.

In order to find the minimum area or circumference blocking
rectangule, we'll examine a sequence of such rectangles. The basic
idea is to start with a bounding rectangle and to rotate it at each
step, so we'll change only one point from the polygon's points that
lie on the rect. We do that by calculating the angles for each point
between the rect side that lies on it and the next polygon edge
(clockwise). We rotate the rect in the minimal angle we've
calculated.

The first rect will lie on the most right, most left, most up and most
down points.

For each rect we'll calculate the area and the circumference. This way
we can find the minimum.

This applet is best viewed at 800x600 resolution.

How to use the applet

The complete source of the applet

Back to the Workshop home page