You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
208 lines
7.4 KiB
208 lines
7.4 KiB
/***************************************************************************
|
|
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 <config.h>
|
|
#endif
|
|
|
|
#include"mpsymbol.h"
|
|
#include<iostream.h>
|
|
#include<qstring.h>
|
|
|
|
//---------------------------------------------------------------------------------------------//
|
|
|
|
// 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; i<m_edges; i++ ) new_buffer[i] = old_buffer[i];
|
|
delete[] old_buffer;
|
|
m_edge_data = new_buffer;
|
|
}
|
|
|
|
edge_data_t *edge = &m_edge_data[m_edges];
|
|
edge->p1 = 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
|