void fillEventQueue ( ) { AttributeStreamOfInt32 event_q = new AttributeStreamOfInt32 ( 0 ) ; event_q . reserve ( m_shape . getTotalPointCount ( ) ) ; // temporary structure to // sort and find // clusters EditShape . VertexIterator iter = m_shape . queryVertexIterator ( ) ; for ( int vert = iter . next ( ) ; vert != - 1 ; vert = iter . next ( ) ) { if ( m_shape . getUserIndex ( vert , m_vertex_cluster_index ) != - 1 ) event_q . add ( vert ) ; } // Now we can merge coincident clusters and form the envent structure. // sort vertices lexicographically. m_shape . sortVerticesSimpleByY_ ( event_q , 0 , event_q . size ( ) ) ; // The m_event_q is the event structure for the planesweep algorithm. // We could use any data structure that allows log(n) insertion and // deletion in the sorted order and // allow to iterate through in the sorted order. m_event_q . clear ( ) ; // Populate the event structure m_event_q . setCapacity ( event_q . size ( ) ) ; { // The comparator is used to sort vertices by the m_event_q m_event_q . setComparator ( new QComparator ( m_shape ) ) ; } // create the vertex clusters and fill the event structure m_event_q. // Because most vertices are expected to be non clustered, we create // clusters only for actual clusters to save some memory. Point2D cluster_pt = new Point2D ( ) ; cluster_pt . setNaN ( ) ; int cluster = - 1 ; Point2D pt = new Point2D ( ) ; for ( int index = 0 , nvertex = event_q . size ( ) ; index < nvertex ; index ++ ) { int vertex = event_q . get ( index ) ; m_shape . getXY ( vertex , pt ) ; if ( pt . isEqual ( cluster_pt ) ) { int vertexCluster = m_shape . getUserIndex ( vertex , m_vertex_cluster_index ) ; mergeClusters_ ( cluster , vertexCluster ) ; continue ; } cluster = getClusterFromVertex ( vertex ) ; // add a vertex to the event queue m_shape . getXY ( vertex , cluster_pt ) ; int eventQnode = m_event_q . addBiggestElement ( vertex , - 1 ) ; // this // method // does // not // call // comparator's // compare, // assuming // sorted // order. setClusterEventQNode_ ( cluster , eventQnode ) ; } }
Fills the event queue and merges coincident clusters .