- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiál2 Line Segment Intersection
Thematic Map Overlay
When you are visiting a country, maps are an invaluable source of information.
They tell you where tourist attractions are located, they indicate the roads and
railway lines to get there, they show small lakes, and so on. Unfortunately,
they can also be a source of frustration, as it is often difficult to find the right
information: even when you know the approximate position of a small town,
Figure 2.1
Cities, rivers, railroads, and their
overlay in western Canada
it can still be difficult to spot it on the map. To make maps more readable,
geographic information systems split them into several layers. Each layer is a
thematic map, that is, it stores only one type of information. Thus there will
be a layer storing the roads, a layer storing the cities, a layer storing the rivers,
Chanter 2
and so on. The theme of a layer can also be more abstract. For instance, there
- --
I -- -
.INE SEGMENT INTERSECTION could be a layer for the population density, for average precipitation, habitat of
the grizzly bear, or for vegetation. The type of geometric information stored
in a layer can be very different: the layer for a road map could store the roads
as collections of line segments (or curves, perhaps), the layer for cities could
contain points labeled with city names, and the layer for vegetation could store
a subdivision of the map into regions labeled with the type of vegetation.
Users of a geographic information system can select one of the thematic
maps for display. To find a small town you would select the layer storing cities,
and you would not be distracted by information such as the names of rivers
and lakes. After you have spotted the town, you probably want to know how to
get there. To this end geographic information systems allow users to view an
overlay of several maps-see Figure 2.1. Using an overlay of the road map and
the map storing cities you can now figure out how to get to the town. When two
or more thematic map layers are shown together, intersections in the overlay
are positions of special interest. For example, when viewing the overlay of
the layer for the roads and the layer for the rivers, it would be useful if the
intersections were clearly marked. In this example the two maps are basically
networks, and the intersections are points. In other cases one is interested in
the intersection of complete regions. For instance, geographers studying the
climate could be interested in finding regions where there is pine forest and the
annual precipitation is between 1000 mm and 1500 mm. These regions are the
intersections of the regions labeled "pine forest" in the vegetation map and the
regions labeled "1000-1500" in the precipitation map.
2.1 Line Segment Intersection
won't be interested in the regions induced by these line segments. Later we
shall look at the more complex situation where the maps are not just networks,
but subdivisions of the plane into regions that have an explicit meaning. To
solve the network overlay problem we first have to state it in a geometric set-
ting. For the overlay of two networks the geometric situation is the following:
given two sets of line segments, compute all intersections between a segment
from one set and a segment from the other. This problem specification is not
quite precise enough yet, as we didn't define when two segments intersect. In
particular, do two segments intersect when an endpoint of one of them lies on
the other? In other words, we have to specify whether the input segments are
open or closed. To make this decision we should go back to the application,
the network overlay problem. Roads in a road map and rivers in a river map
are represented by chains of segments, so a crossing of a road and a river cor-
responds to the interior of one chain intersecting the interior of another chain.
This does not mean that there is an intersection between the interior of two
segments: the intersection point could happen to coincide with an endpoint of
a segment of a chain. In fact, this situation is not uncommon because windy
rivers are represented by many small segments and coordinates of endpoints
may have been rounded when maps are digitized. We conclude that we should
define the segments to be closed, so that an endpoint of one segment lying on
another segment counts as an intersection.
To simplify the description somewhat we shall put the segments from the two
sets into one set, and compute all intersections among the segments in that set.
This way we certainly find all the intersections we want. We may also find
intersections between segments from the same set. Actually, we certainly will,
because in our application the segments from one set form a number of chains,
and we count coinciding endpoints as intersections. These other intersections
can be filtered out afterwards by simply checking for each reported intersection
whether the two segments involved belong to the same set. So our problem
specification is as follows: given a set S of n closed segments in the plane,
report all intersection points among the segments in S.
This doesn't seem like a challenging problem: we can simply take each
pair of segments, compute whether they intersect, and, if so, report their in-
tersection point. This brute-force algorithm clearly requires 0(n2) time. In a
sense this is optimal: when each pair of segments intersects any algorithm must
take L2(n2) time, because it has to report all intersections. A similar example
can be given when the overlay of two networks is considered. In practical sit-
uations, however, most segments intersect no or only a few other segments, so
the total number of intersection points is much smaller than quadratic. It would
be nice to have an algorithm that is faster in such situations. In other words,
we want an algorithm whose running time depends not only on the number of
segments in the input, but also on the number of intersection points. Such an
algorithm is called an output-sensitive algorithm: the running time of the algo-
rithm is sensitive to the size of the output. We could also call such an algorithm
intersection-sensitive, since the number of intersections is what determines the
size of the output.
How can we avoid testing all pairs of segments for intersection? Here we
must make use of the geometry of the situation: segments that are close to-
gether are candidates for intersection, unlike segments that are far apart. Be-
low we shall see how we can use this observation to obtain an output-sensitive
algorithm for the line segment intersection problem.
Let S := {sl ,s2,. . . ,sn) be the set of segments for which we want to compute
all intersections. We want to avoid testing pairs of segments that are far apart.
But how can we do this? Let's first try to rule out an easy case. Define the
y-interval of a segment to be its orthogonal projection onto the y-.axis. When
the y-intervals of a pair of segments do not overlap--we could say that they are
far apart in the y-direction-then they cannot intersect. Hence, we only need to
test pairs of segments whose y-intervals overlap, that is, pairs for which there
exists a horizontal line that intersects both segments. To find these pairs we
Section 2.1
LINE SEGMENT INTERSECTION
ye--
This type of algorithm is called aplane sweep algorithm and the line C is called
event oint
the sweep line. The status of the sweep line is the set of segmenGtersecting
it. The status changes while the sweep line moves downwards, but not contin-
f
uously. Only at particular points is an update of the status required. We call
these points the event points of the plane sweep algorithm. In this algorithm
the event points are the endpoints of the segments.
The moments at which the sweep line reaches an event point are the only
moments when the algorithm actually does something: it updates the status of
the sweep line and performs some intersection tests. In particular, if the event
point is the upper endpoint of a segment, then a new segment starts intersecting
the sweep line and must be added to the status. This segment is tested for
intersection against the ones already intersecting the sweep line. If the event
point is a lower endpoint, a segment stops intersecting the sweep line and must
be deleted from the status. This way we only test pairs of segments for which
there is a horizontal line that intersects both segments. Unfortunately, this is
not enough: there are still situations where we test a quadratic number of pairs,
whereas there is only a small number of intersection points. A simple example
is a set of vertical segments that all intersect the x-axis. So the algorithm is
not output-sensitive. The problem is that two segments that intersect the sweep
line can still be far apart in the horizontal direction.
Let's order the segments from left to right as they intersect the sweep line,
to include the idea of being close in the horizontal direction. We shall only
test segments when they are adjacent in the horizontal ordering. This means
that we only test any new segment against two segments, namely, the ones
immediately left and right of the upper endpoint. Later, when the sweep line
has moved downwards to another position, a segment can become adjacent
to other segments against which it will be tested. Our new strategy should
be reflected in the status of our algorithm: the status now corresponds to the
ordered sequence of segments intersecting the sweep line. The new status not
only changes at endpoints of segments; it also changes at intersection points,
where the order of the intersected segments changes. When this happens we
must test the two segments that change position against their new neighbors.
This is a new type of event point.
Before trying to turn these ideas into an efficient algorithm, we should con-
vince ourselves that the approach is correct. We have reduced the number of
pairs to be tested, but do we still find all intersections? In other words, if
two segments si and sj intersect, is there always a position of the sweep line t
where si and sj are adjacent along l? Let's first ignore some nasty cases: as-
sume that no segment is horizontal, that any two segments intersect in at most
one point-they do not overlap-, and that no three segments meet in a com-
mon point. Later we shall see that these cases are easy to handle, but for now
it is convenient to forget about them. The intersections where an endpoint of
a segment lies on another segment can easily be detected when the sweep line
reaches the endpoint. So the only question is whether intersections between
the interiors of segments are always detected.
Lemma 2.1
Pro05 Lett be a horizontal line slightly above p. If !? is close enough to p then
si and sj. must be adjacent along C. (To be precise, we should take I such that
there is no event point on I, nor in between l and the horizontal Iine through
p.) In other words, there is a position of the sweep line where si and sj are
adjacent. On the other hand, si and sj are not yet adjacent when the algorithm
starts, because the sweep Iine starts above all line segments and the status is
empty. Hence, there must be an event point q where si and sj become adjacent
and are tested for intersection. el
So our approach is correct, at least when we forget about the nasty cases men-
tioned earlier. Now we can proceed with the development of the plane sweep
algorithm. Let's briefly recap the overall approach. We imagine moving a hor-
izontal sweep line t downwards over the plane. The sweep line halts at certain
event points; in our case these are the endpoints of the segments, which we
know beforehand, and the intersection points, which are computed on the fly.
While the sweep line moves we maintain the ordered sequence of segments
intersected by it. When the sweep line halts at an event point the sequence of
segments changes and, depending on the type of event point, we have to take
several actions to update the status and detect intersections.
When the event point is the upper endpoint of a segment, there is a new seg-
I
I
ment intersecting the sweep line. This segment must be tested for intersection
against its two neighbors along the sweep line. Only intersection points below
I
the sweep line are important; the ones above the sweep line have been detected
I
already. For example, if segments si and sk are adjacent on the sweep line, and
1
a new upper endpoint of a segment sj appears in between, then we have to test
Sj for intersection with s, and sk. If we find an intersection below the sweep
1
line, we have found a new event point. After the upper endpoint is handled we
I
continue to the next event point.
When the event point is an intersection, the two segments that intersect
1.
change their order. Each of them gets (at most) one new neighbor against
which it is tested for intersection. Again, only intersections below the sweep
I
line are still interesting. Suppose that four segments sj, sk, sr, and s, appear in
I
this order on the sweep line when the
1
Then sk and sl switch position and we
the sweep line, and also*
I course, also new event points for the algorithm.
When the event point is the lower endpoint of a segment, its two neighbors
now become adjacent and must be tested for intersection. If they intersect
I
Section 2.1
LINE SEGMENT INTERSECTION
Chapter 2
below the sweep line, then their intersection point is a new event point. Assume
LINE SEGMENT INTERSECTION three segments sk, si, and s, appear in this order on the sweep line when the
lower endpoint of sl is encountered. Then sk and s, will become adjacent and
we test them for intersection.
After we have swept the whole plane-more precisely, after we have treated
the last event point-we have computed all intersection points. This is guar-
anteed by the following invariant, which holds at any time during the plane
sweep: all intersection points above the sweep line have been computed cor-
After this sketch of the algorithm, it's time to go into more detail. It's also time
to look at the degenerate cases that can arise, like three or more segments meet-
ing in a point. We should first specify what we expect from the algorithm in
these cases. We could require the algorithm to simply report each intersection
point once, but it seems more useful if it reports for each intersection point a
list of segments that pass through it or have it as an endpoint. There is another
special case for which we should define the required output more carefully,
namely that of two partially overlapping segments, but for simplicity we shall
ignore this case in the rest of this section.
I
1
We start by describing the data structures the algorithm uses.
First of all we need a data structure-called thcvent -that stores
I
the events. We denote the event queue by Q. We need an operation that re-
I
moves the next event that will occur from Q, and returns it so that it can be i
treated. This event is the highest event below the sweep line. If two event
points have the same y-coordinate, then the one with smaller x-coordinate will
I_
be returned. In other words, event points on the same horizontal line are treated
I
from left to right. This implies that we should consider the left endpoint of a ,
horizontal segment to be its upper endpoint, and its right endpoint to be its
lower endpoint. You can also think about our convention as follows: instead of
1
having a horizontal sweep line, imagine it is sloping just a tiny bit upward. As
a result the sweep line reaches the left endpoint of a horizontal segment just be-
!
e
. .{.. .- -----
__ _________...--.-----
fore reaching the right endpoint. The event queue should allow for insertions,
'
because new events will be computed on the fly. Notice that two event points i
can coincide. For example, the upper endpoints of two distinct segments may
,
coincide. It is convenient to treat this as one event point. Hence, an insertion
i
must be able to check whether an event is already present in Q.
I
We implement the event queue as follows. Define an order 4 on the event
points that represents the order in which they will be handled. Hence, if p t
and q are two event points then we have p 4 q if and only if p, > qy holds
or p, = q, and p, < q, holds. We store the event points in a balanced binary
search tree, ordered according to 4. With each event point p in Q we will store
I
the segments starting at p, that is, the segments whose upper endpoint is p. This
information will be needed to handle the event. Both operations-fetching the
next event and inserting an event-take O(1ogm) time, where m is the number I
of events in Q. (We do not use a heap to implement the event queue, because
we have to be able to test whether a given event is already present in Q.) i
Second, we need to maintain the status of the algorithm. This is the or-
Section 2.1
dered sequence of segments intersecting the sweep line. The status structure, LINE SEGMENT INTERSECTION
denoted by I, is used to access the neighbors of a given segment s, so that they
can be tested for intersection with s. The status structure must be dynamic: as
segments start or stop to intersect the sweep line, they must be inserted into or
YL-- -
deleted from the structure. Because there is a well-defined order on the seg-
ments in the status structure we can use a balanced binary search tree as status
'-1
this may be surprising. But binary search trees can store any set of elements, i
\ ;_II_;
structure. When you are only used to binary search trees that store numbers,
I
as long as there is an order on the elements.
\\
Si Sm /
I
In more detail, we store the segments intersecting the sweep line ordered ; Si sk
in the leaves of a balanced binary search tree I. The left-to-right order of
':- ----,/---a- ...-
'---/
the segments along the sweep line corresponds to the left-to-right order of the
leaves in I. We must also store information in the internal nodes to guide the
search down the tree to the leaves. At each internal node, we store the segment
segments only in interior nodes. This will save some storage. However, it is
s/--..:
from the rightmost leaf in its left subtree. (Alternatively, we could store the
-------- ---------- ---------- ----- ---------..--
t
conceptually simpler to think about the segments in interior nodes as values
to guide the search, not as data items. Storing the segments in the leaves also
makes some algorithms simpler to describe.) Suppose we search in I for the
segment immediately to the left of some point p which lies on the sweep line.
At each internal nodev we simply test whether p lies left or right of the segment
stored at v. Depending on the outcome we descend to the left or right subtree I
of v, eventually ending up in a leaf. Either this leaf, or the leaf immediately to I
the left of it, stores the segment we are searching for. In a similar way we can
find the segment immediately to the right of p, or the segments containing p.
It follows that each update and neighbor search operation takes O(1ogn) time.
The event queue Q and the status structure I are the only two data struc-
1
tures we need. The global algorithm can now be described as follows.
Algorithm FINDINTERSECTIONS(S) I
inuutkA set S of line segments in the plane.
I
-The set of intersection points among the segments in S, with for each
intersection point the segments that contain it.
1. Initialize an empty event queue Q. Next, insert the segment endpoints
into Q; when an upper endpoint is inserted, the corresponding segment
should be stored with it.
. Initialize an empty status structure I.
. while Q is not empty
. do Determine the next event point p in Q and delete it.
HANDLE EVENT POINT(^)
We have already seen how events are handled: at endpoints of segments we
have to insert or delete segments from the status structure I, and at intersection
points we have to change the order of two segments. In both cases we also
have to do intersection tests between segments that become neighbors after the
event. In degenerate cases-where several segments are involved in one event 25
Chapter 2 soint-the details are a little bit more tricky. The next procedure describes how 1
1 LINE SEGMENT INTERSECTION to handle event points correctly; it is illustrated in Figure 2.2.
1
J
1 Figure 2.2
11 event point and the changes in the
status structure
Note that in lines 8-16 we assume that s~ and s, actually exist. If they do not Section 2.1
exist the corresponding steps should obviously not be performed. LINE SEGMENT INTERSECTION
The procedures for finding the new intersections are easy: they simply test two
segments for intersection. The only thing we need to be careful about is, when
we find an intersection, whether this intersection has already been handled ear-
lier or not. When there are no horizontal segments, then the intersection has
not been handled yet when the intersection point lies below the sweep line.
But how should we deal with horizontal segments? Recall our convention that
events with the same y-coordinate are treated from left to right. This implies
that we are still interested in intersection poin
Vloženo: 26.04.2009
Velikost: 12,18 MB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz