Visibility Graph - Geometric Computing Lab

Report
Visibility Graph
Team 10
NakWon Lee, Dongwoo Kim
Robot Motion Planning
• Consider the case of point robot
• The polygons in S are obstacles, and their total
number of edges is denoted by n
• The point robot can touch obstacles, because
obstacles are open set.
• Start position  . Goal position  .
• Paths do not intersect the interior of any of the
obstacles.
Robot Motion Planning
• Use trapezoidal map ( )of the free
configuration space  .
• Configuration space is the parameter space of a
robot . Denoted by ().
• For a point robot,   was simply the empty
space between obstacles.
Configuration Space
Shortest Paths
• Construct the trapezoidal map ( ) for
configuration space  .
• Construct the load map  .
• Find the trapezoids which have the start point or
end point.
• Find the shortest route in the load map  using
breadth first search algorithm.
Shortest Paths
Shortest Paths
• Shortest path in road map is not a real shortest path
• because some arcs are btw nodes that are far apart, whereas
others are btw nodes that are close to each other.
• It is just minimum number of hop.
• To improve this problem, give each arc a weight
corresponding to the Euclidean length, and use graph
search algorithm that find the shortest path in a
weighted graph.
• Dijkstra's algorithm
• But, it is still not a shortest path.
Shortest Paths
• Think of this path as an elastic
rubber band.
• Fix the endpoints at the start and
goal position.
• Try to tighten the rubber band.
• It will be stopped by the obstacles.
• The new path will follow parts of
the obstacle boundaries and
straight line segments through
open space.
Shortest Paths
• Lemma 15.1 Any shortest path between  and
 among a set  of disjoint polygonal obstacles
is a polygonal path whose inner vertices are
vertices of 
• Inner vertex – A vertex that is not the begin or endpoint
of the path.
Shortest Paths
• Proof.
• Suppose for a contradiction that a shortest path  is not
polygonal.
• Point  on  that lies in the interior of the free space
with the property that no line segment containing  is
contained in .


1
 
2
Shortest Paths
• There is a disc of positive radius centered
at  that is completely contained in the
free space.
• Part of  inside the disk, which is not a
straight line segment, can be shortened
by replacing it with the segment
connecting the points which lie on circle.
• Contradict the theorem “any shortest
path must be locally shortest”.
Shortest Paths
• Now consider a vertex  on . It cannot lies in the interior of the free
space.
• Consider the disc centered at  such that half of the disc is contained in
the free space.
• Can replace the sub path inside the disc with a straight line segment.
• The only possibility left is that  is an obstacle vertex.


short cut

1

2
1
2
Shortest Paths
• Construct a road map with this characterization.
• This road map is visibility graph of , denoted by
 ().
• Its nodes are the vertices of .
• There is an edge between vertices  and  if they
can see each other.
• The segment  dose not intersect the interior of
any obstacle in .
Shortest Paths
• Two vertices that can see each other are called
visible.
• The segment connecting visible two vertices is
called a visibility edge.
• Endpoint of the same obstacle edge always see
each other.
• Hence, the obstacle edges form a subset of the
edges of  ().
Shortest Paths
• To make a complete road map to find shortest path,
add start and goal point as vertices to .
• So we consider the visibility graph of the set
 ∗ ≔  ∪ { ,  }.
• Corollary 15.2 The shortest path between 
and  among a set  of disjoint polygonal
obstacles consists of arcs of the visibility graph
 ( ∗ ), where  ∗ ≔  ∪ { ,  }.
Shortest Paths
Visibility Graph
Definition:
• The visibility graph of s and t and the obstacle set
is a graph whose vertices are s and t the obstacle
vertices, and vertices v and w are joined by an edge
if v and w are either mutually visible or if (v, w) is
an edge of some obstacle.
Visibility Graph
Visible Vertices
Visible Vertices
Visible
Definition
Two points p and q are mutually visible if the open
line segment joining them doesn't intersect the
interior of any obstacle.
Search Tree
Computing the Visibility Graph
• VisibleVertices: () – (sorting)
• Operation on blanced search tree : ()
• For every vertices with Visible Vertices.
• VisibilityGraph – (2 )
Computing the Visibility Graph
• Give an (2 ) procedure for constructing.
•  is the number of line segments in the plane.
• No three vertices are collinear??
• The algorithm is not output sensitive.
• An ( log  + ) algorithm ( is the number of
edges in visibility graph) is existent but quite
complicated.
Computing the Visibility Graph
• The text’s algorithm operates by doing sweep one
vertex at a time.
• New algorithm does the sweep for all vertices
simultaneously.
• When we use the arrangement, angular sort can be
performed for all vertices in (2 ) time.
• If we build the entire arrangement, this sorting
algorithm will involve (2 ) space.
• However it can be implemented in () space
using an algorithm called topological plane sweep.
Computing the Visibility Graph
• First, recall the algorithm for computing trapezoidal
maps.
• Shoot a bullet up and down from every vertex until
it hits its first line segment.
• Angle  continuously sweeps out all slopes from
− ∞ to +∞.
• All bullet lines attached to all the vertices begin to
turn slowly counterclockwise.
Computing the Visibility Graph
• The question is what are the significant event
points, and what happens with each event?
Computing the Visibility Graph
• It is useful to view the problem both in its primal
and dual form.
• 2 ( is the number of segments) segment end
points  = ( ,  ), its dual line  ∗ :  =   −  .
• Significant event occurs whenever a bullet path in
the primal plane jumps from one line segment to
another.
• This occurs when  reaches the slope of the line
joining two visible endpoints  and .
Computing the Visibility Graph
event
event
event
Computing the Visibility Graph
• To keep track of which endpoints are visible and
which are not is complicated.
• Instead we will take events to be all angles 
between two endpoints, whether they are visible
or not.
• By duality, the slope of such an event will
correspond to the -coordinate of the intersection
of dual lines  ∗ and  ∗ in the dual arrangement.
Dual Arrangement
x-coordinate is the slope of dual segment
Dual of point D
Dual of point C
Find Events
• By sweeping the arrangement of the 2 dual lines
from left-to-right, we will enumerate all the slope
events in angular order.
Find Events
Angular order
• By using topological plane sweep,
event do not need to be sorted.
Topological Plane Sweep
• Provides a way to sweep an
arrangement of lines using
a “flexible” sweeping line.
• Because events do not
need to be sorted, we can
avoid (log ) factor.
Topological Plane Sweep
• Upper horizon tree
• Lower horizon tree
Topological Plane Sweep
• Data structure
• [1: ] – array of line equation.   = ( ,  ), if the th line
of ,  , is  =   +  .
• [1: ] – an array representing the upper horizon tree.
[] is a pair ( ,  ) of indices indicating the lines that
delimit the segment of  in the upper horizon tree to the left
and to the right.
•  1:  – represents the lower horizon tree.
•  – a set of integers, represented as a stack. If  is in , then 
and +1 share a common right endpoint.
• [1: ] – an array holding the current sequence of indices
that form the lines 1 , 2 , ⋯ ,  of the cut.
•  1:  – a list of pairs of indices indicating the lines
delimiting each edge of the cut. [] thus encodes the
endpoints of the edge on []. The same convention as that
above is used for missing endpoints.
Topological Plane Sweep
If segment is the rightmost on  ,
set  = 0
If segment is the leftmost on  ,
set  = −1
Topological Plane Sweep
• Algorithm
Initialization:
• 1. Sort the lines of the arrangement by slope.
• 2. Find the leftmost and the rightmost intersection point of the lines. Let the
two points be ( ,  ) and ( ,  ).
• 3. Create vertical lines  =  − 1,  =  + 1 as left boundary and right
boundary. Determine the intersection points of lines 1 , ⋯ ,  with the
boundaries.
• 4. Create upper horizon tree: Insert 1 , ⋯ ,  . Assume 1 , ⋯ ,  have been
inserted. These lines form an upper bay. To insert +1 , begin at its endpoint on
the left boundary. Walk in counter clockwise order around the bay till we find
the intersection point of +1 with an edge.
• 5. Create lower horizon tree similarly by starting the travers at endpoints on the
right boundary.
• 6. Initialize : Let [] = (−1, ) and [] = (−1, ). If  intersects  to
the left of the intersection point of  and  then the right delimiting line of  is
. Otherwise, the right delimiting line of  is .
• 7. Initialize  by scanning .
Topological Plane Sweep
• Algorithm
Elementary Step
• While  = Λ
• 1. Pop  from 
• 2. Swap [], [ + 1] /*lines are going to cross, after the
elementary step*/
• 3.   .  ←   + 1 . ,   + 1 .  ← [].  /*the point of
elementary step becomes the left endpoint of the two new cut
edges */
• 4. Update , .
• 5.   .  ←     . ,    . ,   + 1 .  ←
    + 1 . ,    + 1 .  /* find the new right
endpoints */
• 6. If [ + 1].  = [ + 2] then push  + 1 into . If [].  =
[ − 1] then push  − 1 into . /* push valid vertices formed after
sweeping into I if there is any */
What Happens at Each Event
• For each vertex , there are two bullet paths
growing from  along the line with slope .
• Let () and () denote the line segments that
forward bullet path and backward bullet path hit.
• If either path does not hit any segment then we
store a special null value.
• Each slope is determined by exactly two lines.
What Happens at Each Event
• Possible scenarios
What Happens at Each Event
• Same segment
• If  and  are endpoints of the same segment, then
they are visible, and we add the edge (, ) to the
visibility graph.
• How can I check this?
What Happens at Each Event
• Invisible
• Consider the distance
from  to .
• Compute the contact
point of the bullet path
shot from  in direction
 with segment () or
().
• If  is longer than ,
 and  are not visible.
Calculate the distance of 

Calculate the distance of 
What Happens at Each Event
• Segment entry
• If we are entering the segment, then we set () or
() to this segment.
•  can be a visibility edge.
What Happens at Each Event
• Segment exit
• The bullet path will need to
shoot out and find the next
segment that it hits.
• It is available in (1) time.
• Since we are sweeping over 
at the same time that we are
sweeping over .
• We know that the bullet
extension from  hits   .
• So, new () is same as ().
()
Thank You
Q&A

similar documents