/*************************************************************************** ksdelunay.h ------------------- begin : copyright : (C) 2001 by Kamil Dobkowski email : kamildobk@poczta.onet.pl ***************************************************************************/ /*************************************************************************** * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * ***************************************************************************/ #ifndef KSDELUNAY_H #define KSDELUNAY_H #ifdef HAVE_CONFIG_H #include #endif #include"mpsymbol.h" #include #include //---------------------------------------------------------------------------------------------// // input point buffer struct point_data_t { int index; double x, y; inline bool operator<( const point_data_t& p ) const { return x == p.x ? y < p.y : x < p.x; } inline bool operator==( const point_data_t& p ) const { return x == p.x && y == p.y; } }; // circum circle for each triangle struct triangle_data_t { double r2; double xc; double yc; }; struct edge_data_t { int p1; int p2; }; //---------------------------------------------------------------------------------------------// /** * Performs delunay triangulation. * @author Kamil Dobkowski */ class MPDelunay : public MPSymbol { public: /** * Constructor */ MPDelunay( MPSymbolList *args, int columnFrom, int columnTo, const char *id ); /** * Destructor */ ~MPDelunay(); void checkArgs( MPError& error ); double value( int row, int col ); protected: /** * Performs triangulation. Returns NULL if x and y have a different number of rows or * operation was canceled. Returns matrix Nx3 with indicies to rows of x and y. If * 'neighbours' is not NULL returns the second matrix with the same size as result, * wich contains indexes to neighbouring triangles for each edge. It is optimized for * large difference between x values. If your points differs mostly by y value you * can invoke this method like that: result = triangulation( yColumn, xColumn ). */ void triangulation( MPSymbol *xColumn, MPSymbol *yColumn, bool useLargeBuffers = true ); /** * Returns an error string ( if triangulation returned NULL ) or warnings. */ QString error() const { return m_error; } private: QString m_error; int m_triangle_buff_len; long int *m_triangle_buff; int m_edges; int m_points; int m_edge_buffer_capacity; edge_data_t *m_edge_data; // buffer for edges point_data_t *m_point_data; // buffer for input points triangle_data_t *m_triangle_data; // additional triangle data when using large buffers int m_triangles; int m_active_triangles; long int *m_p1; // m_p1[n] points to the first vertex of triangle n long int *m_p2; // m_p2[n] points to the second vertex of triangle n long int *m_p3; // m_p3[n] points to the third vertex of triangle n bool *m_complete; // m_complete[n] - if triangle should be considered when searching for triangles long int *m_result; // buffer for all vertices: m_p1, m_p2, m_p3 points to its contents void stop(); void set_error( const QString& message ); inline void add_triangle( int p1, int p2, int p3 ); inline void del_triangle( int index ); inline void add_edge( int p1, int p2 ); inline void put_at_end( int triangle ); bool point_in_circum_circle( double x, double y, int triangle ); }; //---------------------------------------------------------------------------------------------// inline void MPDelunay::add_edge( int p1, int p2 ) { // resize edge buffer if ( m_edges >= m_edge_buffer_capacity ) { m_edge_buffer_capacity = m_edge_buffer_capacity * 2 + 8; edge_data_t *old_buffer = m_edge_data; edge_data_t *new_buffer = new edge_data_t[m_edge_buffer_capacity]; for( int i=0; ip1 = p1; edge->p2 = p2; m_edges++; } //---------------------------------------------------------------------------------------------// inline void MPDelunay::add_triangle( int p1, int p2, int p3 ) // remember to keep order - all completed triangles must be // at the end of the list { // move first completed triangle to the end of the list m_p1[m_triangles] = m_p1[m_active_triangles]; m_p2[m_triangles] = m_p2[m_active_triangles]; m_p3[m_triangles] = m_p3[m_active_triangles]; m_complete[m_triangles] = true; // put a new (uncompleted) triangle at this place m_p1[m_active_triangles] = p1; m_p2[m_active_triangles] = p2; m_p3[m_active_triangles] = p3; m_complete[m_active_triangles] = false; // do not copy data of completed triangles - it won't be needed anymore if ( m_triangle_data ) { m_triangle_data[m_active_triangles].r2 = -1.0; } m_triangles++; m_active_triangles++; } //---------------------------------------------------------------------------------------------// inline void MPDelunay::del_triangle( int index ) // remeber to keep order - all completed triangles must be // at the end of the list // deletes only uncompleted triangle, in the other case, // screws the list { // put the last active triangle at freed place m_p1[index] = m_p1[m_active_triangles-1]; m_p2[index] = m_p2[m_active_triangles-1]; m_p3[index] = m_p3[m_active_triangles-1]; m_complete[index] = false; // put the last complete triangle at the place freed by the last active triangle m_p1[m_active_triangles-1] = m_p1[m_triangles-1]; m_p2[m_active_triangles-1] = m_p2[m_triangles-1]; m_p3[m_active_triangles-1] = m_p3[m_triangles-1]; m_complete[m_active_triangles-1] = true; // do not copy the data of completed triangle if ( m_triangle_data ) { m_triangle_data[index] = m_triangle_data[m_active_triangles-1]; } m_triangles--; m_active_triangles--; } //---------------------------------------------------------------------------------------------// inline void MPDelunay::put_at_end( int triangle ) // put completed triangle at the end of the list, decrease active triangle count // remeber to keep order - all completed triangles must be // at the end of the list { int p1 = m_p1[triangle]; m_p1[triangle] = m_p1[m_active_triangles-1]; m_p1[m_active_triangles-1] = p1; int p2 = m_p2[triangle]; m_p2[triangle] = m_p2[m_active_triangles-1]; m_p2[m_active_triangles-1] = p2; int p3 = m_p3[triangle]; m_p3[triangle] = m_p3[m_active_triangles-1]; m_p3[m_active_triangles-1] = p3; m_complete[triangle] = false; m_complete[m_active_triangles-1] = true; if ( m_triangle_data ) { triangle_data_t *d1 = &m_triangle_data[triangle]; triangle_data_t *d2 = &m_triangle_data[m_active_triangles-1]; triangle_data_t temp = *d1; *d1 = *d2; *d2 = temp; } m_active_triangles--; } #endif