CSC 378: Data Structures and Algorithm Analysis

BINARY SPACE PARTITIONS

A 'scene' is a set of line segments in the plane. They could represent building walls. Each segment has a height :
 

Solution I
Draw the walls in arbitrary order.

But - hidden walls might be drawn after visible walls, and hence drawn over them.

Solution II
Draw the walls in order of decreasing distance.

Idea
Partition the plane in two!

1. First draw things on the side of the partition not containing the viewpoint ( v ).
2. Then draw things on the side containing the viewpoint.

Step 1 draws distant walls first.
Step 2 requires a recursive subdivision of the side containing the viewpoint.

Algorithm
Make a cut, then recursively partition the two sides.
Where a partition line intersects a segment, split the segment and put the pieces on either side.

There's a tree structure here!
A node represents a partition line.
Left and right subtrees are the partitions on either side.

Definition

A partition has a positive side (which does not include the origin) and a negative side (which does include it).

Let's put the  side in a partition node's left subtree, and the  side in the right.

From before -

And to display our walls -

Note that each node stores the wall that defines that node's partition line, and also that 'v' denotes the viewpoint.

Draw(v,root)
if v is on the  side of partition(root)
Draw(v,right(root))
Draw wall(root)
Draw(v,left(root))
Else
Draw(v,left(root))
Draw wall(root)
Draw(v,right(root))

Insert the walls into the tree one-by-one -

Insert(w,root)
if w is on the  side of root partition
Insert(w,left(root))
else if w is on the  side
Insert(w,right(root))
else if w is cut by root partition
split w into w+ and w-
Insert(w-,left(root))
Insert(w+,right(root))

Example



In order to insert D as shown -

- we take the following steps:

Insert( D, A )
  split D into D+ and D-
Insert( D-, left( A ) )
Insert( D+, right( A ) )

Insert( D-, C )
  becomes right child of C

Insert( D+, B )
  Split D+ into D+- and D+ +
Insert( D+-, left( B ) )
Insert( D+ +, right( B ) )- these become L and R children

Result :

Leaves, if present, represent regions of the plane, as indicated in the following diagram :

Draw( ) visits every node once.

T( Draw )  O( # nodes in the BSP )
- where # nodes in BSP = n + # cuts
- where n is the original number of edges (i.e. walls).

But # of cuts  , since each edge might cut O( n ) other edges, like so:

Theorem
If edges are inserted in random order, E( # nodes )  !

Conclusion
It is better to read the edges, randomize their order, then insert them.

Theorem
Let 
be a random permutation of 

Insert segments of 
in order 

The expected BSP size is in O( n log n ).

Proof

size = n + E( # of cuts )

When does an edge u cut an edge v?
  u must already be in the tree when v is inserted
and 

Suppose we have :

Then u cuts v if u was inserted before  ,  ,  , and v
- otherwise, line( u ) stops at the already-inserted edge.

i.e. In the subsequence of  containing u, v,  . . .  , u must be first.

Let index( u, v ) = # of other edges that intersect line( u ) between u and v (in the illustration ablove, there are three).

Then P( u cuts v ) = P( u is first in the subsequence containing   . . .  u v )
= 

Note that 'index' means -

Expected Size

 
 

 


 

 

drawing takes expected O( n log n ) time!