Homework Assignment # 3

due Monday, October 30, 1995

by: George North

439-68-5643

Computational Geometry

CSCI 6640

Fall 1995

Dr. N. Adla A. DePano

If a line L intersects two edges of convex polygon P then L intersects P . Line L does not intersect P if it touches only 1 vertex. Line L does not intersect P if it touches two consecutive vertexes ( L is on an edge of P ). For the purposes of this algorithm, it will be assumes that a vertex of P belongs to its counter clockwise edge. This allows the algorithm to be defined in terms of edges. Each edge, e , has two vertices, e v1 and e v2 .

[1,2], [1,3], ... , [1,n], [2,n], [3,n], ... , [n-1,n]

>> [2,3], [2,4], ... , [2,n-1], [3,n-1], [3,n-1], ... , [n-2,n-1]

>> [3,4], [3,5], ... , [3,n-2], [4,n-2], [4,n-2], ... , [n-3,n-2]

>> ...

for example: n=7

The algorithm will be in two parts.

The complexity of both first and second part is O (lg n). Algorithm complexity is O (lg n).

continues next page ---

E = 1, 2, 3, ... , n . Find the edge pair (i, j) in E that is intersected by a line L .

EdgeClockWise( e i ), returns TRUE if edge i is clockwise to line L

Initialize: i = 1 (1st edge), j= n

Loop

Edges i and j are checked for intersection with L . -- O (1)

If BOTH edges are intersected by L ... FINISHED

If edge j = i + 1, the other edge is j ... FINISHED

If "one edge intersection is found" then

"

i = i + 1; j = j - 1;

if i = j then " L does NOT intersect P" ... FINISHED

end Loop

Step 1 -->

-- i.e. if L intersects either edge 2 or 6, the remaining possible edges are 3, 4, 5.

i = i + 1; j = j - 1;

Loop

k = median edge between i and j -- (j-i)/2

if EdgeIntersect( k ) = true then " k is the other intersected edge" ... FINISHED

if EdgeClockWise( k ) then j = k else i = k

-- each loop interation cuts in half the # of edges left to search

end Loop

Step 2 -->

Each iteration in step 1 eliminates half the remaining edges. Step 2 need only look at the edges not processed in Step 1. Each iteration in step 2 eliminates half the remaining edges.

-- >

min|x-y|:x OE P, y OE P,

x,y

line L does not intersect polygon P .

min|x-y|:x OE P, y OE P is a line [x,y] from a vertex of P perpendicular to L .

x,y

this same vertex will be on the Convex Hull of P .

1). Find Convex Hull H (of m vertices) of P . H is a counter clockwise ordered set. -->

2). Find one antipodal pair of Hull vertices, v a and v b . These are opposing vertices, and divide H about in half.

-->

j = v b

calculate perpendicular distance (d i and d j ) to L of vertices i , j --> O (1)

if ( i + 1) = j then "minimum (d i , d j ) is minimum distance to L " ... FINISHED

if d i < d j then "minimum distance vertex lies clockwise of i "

j = median value clockwise of i , j

else "minimum distance vertex lies counter clockwise between i and j"

i = median value counter clockwise of i , j

-->

Each iteration of Step 1 divides the number of vertices remaining to examine in half.

Construct data structure DA , with integer index. DA ( i ) is an integer initialized to 0. For each interval in I , add 1 to each D A ( i ) for a <= i <= b .

loop for each interval [ a , b ] in I

j = a

loop while j <= b

j = j + 1

end loop

end loop

-->

DA ( i ) > 0 if there exist any interval [ a , b ], such that a <= i <= b .

DA ( i ) = "the number of intervals in I that contain integer value i "

... can be accomplished by checking if DA ( x ) > 0. If x is an integer. If x is a real, then it is necessary to first coerce x to integer.

-->

... number of intervals in I = DA ( x ) > 0. If x is an integer. If x is a real, then it is necessary to first coerce x to integer.

-->

... can be accomplished by checking if EITHER DA ( r ) > 0 OR DA ( s ) > 0.

- -->

Construct an A-V-L tree, A a , ordered such that: O ( n lg n)

i) using the a component of intervals [ a , b ]: left children are less then right children, and ii) equal a components are ordered by length ( | b-a | ), shortest as left child.

Construct an A-V-L tree, A b , ordered such that: O ( n lg n)

i) using the b component of intervals [ a , b ]: left children are less then right children, and ii) equal b components are ordered by length ( | b-a | ), shortest as left child.

NOTE: an A-V-L tree is a balanced binary tree with search complexity of O ( lg n).

Search_a( x ) : ... binary search (i.e. using recursion) A a tree comparing x to a components, return(TRUE) if a >= x <= b, else return(FALSE).

-->

Search_b( x ) : ... binary search (i.e. using recursion) A b tree comparing x to b components, return(TRUE) if b <= x >= a, else return(FALSE).

-->

isIn( x ) : ... return(TRUE) if either Search_a( x ) or Search_b( x ) returns true, else return(FALSE).

-->

... can be accomplished by using function : isIn( x )

-->

... can be accomplished by searching every interval in I for a >= x <= b, and counting the number of matches.

-->

... can be accomplished by using function : isIn( x ) --

return(TRUE) if isIN( r ) or if isIN( s );

- -->

Approach II, Algorithm 3b with complexity of O (n) needs improvement. Approach I would be preferred if repeated calls were expected to Algorithm 3b. When the number of calls to Algorithm 3b nears n , the number of intervals ... then Approach I would provide better performance. Approach I would be practical when the maximum length of a very large majority of intervals was less than some small value k , so that preprocessing was complexity O ( n k ) ... and the number of calls to Algorithm 3b was greater than k.

1. As seen in class, O (1) time is required for point location in a triangle.

2. As seen in class, O (n) time is required for point location in a n-gon.

3. Point location inside a circle can be done in O (1) time -- i.e. is the distance to point p from center of circle > it radius?

As n approaches infinity, an n-gon is a circle. From 1. and 2. above, it could be assumed that complexity for a circle would also be infinity. --> ??????

*Original file name: HW3rtf*

*This file was converted with TextToHTML - (c) Logic n.v.*