Problem Description

We will consider a general method of defining a subdivision of the plane into simple region. The method works not only for simple polygons but for much more general inputs as well.

Let S be a set line segments in the plane such that the segments do not intersect one another, except where the endpoint of one segment intersect the endpoint of another segments. And suppose that no two segment endpoints share the same x-coordinate which implies that there are no vertical segments.

We will produce a subdivision of space that with respect to these line segments. To do so, we start by enclosing all the segments within a large bounding rectangle. Next, imagine shooting a bullet path vertically upwards and downwards from the endpoints of each segment of S until it first hits another segment of S or the top or bottom of the bounding rectangle. The combination of the original segments and these vertical bullet paths defines a subdivision of the bounding rectangle called the trapezoidal map of S.

Algorithm

We could construct the trapezoidal decomposition using general sweep line algorithm. Imagine a vertical line (the sweep line) passing through each vertex in turn, where the vertices are in increasing x-order. At each vertex i.e. event, one or more trapezia are output. The key point here is how to update the even query in the sweep line algorithm to keep the correct ordering. Suppose endpoint v fall between edges a and b and v is a endpoint of c or shared endpoint by c and d. There are 3 types of event happened at each endpoint in our line set.

  • Line c is to the right of our sweep line or line c is to the right and d is to the left. Then delete d and insert c to the proper place in the queue.
  • Line c is to the left of the sweep line or both d and c are to the left of sweep line. Then delete both of them from the queue.
  • Line c is to the right of the sweep line or both d and c are to the right of the sweep line. Then insert c or c and d to the proper place in L.
Runtime Analysis

Since it is a sweep line algorithm, the total running time is O(n log n).

Applet

Instruction

Instruction



Source Code

Source Code for the Applet. This includes the source code to run the applet and some supporting libraries.

Group Members

Individual work:

Mengxue Zhang: Java Applet

Ying Wang: Website and Report

Wenjia Zhang: Applet and Report

Reference