|
inlib
1.2.0
|
|
inlib
1.2.0
|
Public Types | |
| enum | side { right, left } |
| typedef unsigned int | index_t |
Public Member Functions | |
| alg (std::ostream &a_out) | |
| virtual | ~alg () |
| bool | process (const std::vector< std::pair< real, real > > &a_data) |
| std::vector< triangle > | get_triangles () |
| void | print_triangles () |
| void | divide (point *p_sorted[], index_t l, index_t r, edge **l_ccw, edge **r_cw) |
| typedef unsigned int inlib::dct::alg::index_t |
| inlib::dct::alg::alg | ( | std::ostream & | a_out | ) | [inline] |
| virtual inlib::dct::alg::~alg | ( | ) | [inline, virtual] |
| void inlib::dct::alg::divide | ( | point * | p_sorted[], |
| index_t | l, | ||
| index_t | r, | ||
| edge ** | l_ccw, | ||
| edge ** | r_cw | ||
| ) | [inline] |
Definition at line 214 of file dct.
{
unsigned int n;
index_t split;
edge *l_ccw_l, *r_cw_l, *l_ccw_r, *r_cw_r, *l_tangent;
edge *a, *b, *c;
real c_p;
n = r - l + 1;
if (n == 2) {
/* Bottom of the recursion. Make an edge */
*l_ccw = *r_cw = make_edge(p_sorted[l], p_sorted[r]);
} else if (n == 3) {
/* Bottom of the recursion. Make a triangle or two edges */
a = make_edge(p_sorted[l], p_sorted[l+1]);
b = make_edge(p_sorted[l+1], p_sorted[r]);
splice(a, b, p_sorted[l+1]);
c_p = Cross_product_3p(p_sorted[l], p_sorted[l+1], p_sorted[r]);
if (c_p > 0.0)
{
/* Make a triangle */
c = join(a, p_sorted[l], b, p_sorted[r], right);
*l_ccw = a;
*r_cw = b;
} else if (c_p < 0.0) {
/* Make a triangle */
c = join(a, p_sorted[l], b, p_sorted[r], left);
*l_ccw = c;
*r_cw = c;
} else {
/* Points are collinear, no triangle */
*l_ccw = a;
*r_cw = b;
}
} else if (n > 3) {
/* Continue to divide */
/* Calculate the split point */
split = (l + r) / 2;
/* Divide */
divide(p_sorted, l, split, &l_ccw_l, &r_cw_l);
divide(p_sorted, split+1, r, &l_ccw_r, &r_cw_r);
/* Merge */
merge(r_cw_l, p_sorted[split], l_ccw_r, p_sorted[split+1], &l_tangent);
/* The lower tangent added by merge may have invalidated
l_ccw_l or r_cw_r. Update them if necessary. */
if (Org(l_tangent) == p_sorted[l])
l_ccw_l = l_tangent;
if (Dest(l_tangent) == p_sorted[r])
r_cw_r = l_tangent;
/* Update edge refs to be passed back */
*l_ccw = l_ccw_l;
*r_cw = r_cw_r;
}
}
| std::vector<triangle> inlib::dct::alg::get_triangles | ( | ) | [inline] |
Definition at line 145 of file dct.
{
std::vector<triangle> ts;
// Print the ring of triangles about each vertex.
edge *e_start, *e, *next;
point *u, *v, *w;
index_t i;
point *t;
for (i = 0; i < p_number; i++) {
u = &p_array[i];
e_start = e = u->entry_pt;
do
{
v = Other_point(e, u);
if (u < v) {
next = Next(e, u);
w = Other_point(next, u);
if (u < w)
if (Identical_refs(Next(next, w), Prev(e, v))) {
/* Triangle. */
if (v > w) { t = v; v = w; w = t; }
ts.push_back(triangle((unsigned int)(u - p_array),
(unsigned int)(v - p_array),
(unsigned int)(w - p_array)));
}
}
/* Next edge around u. */
e = Next(e, u);
} while (!Identical_refs(e, e_start));
}
return ts;
}
| void inlib::dct::alg::print_triangles | ( | ) | [inline] |
Definition at line 181 of file dct.
{
// Print the ring of triangles about each vertex.
edge *e_start, *e, *next;
point *u, *v, *w;
index_t i;
point *t;
for (i = 0; i < p_number; i++) {
u = &p_array[i];
e_start = e = u->entry_pt;
do
{
v = Other_point(e, u);
if (u < v) {
next = Next(e, u);
w = Other_point(next, u);
if (u < w)
if (Identical_refs(Next(next, w), Prev(e, v))) {
/* Triangle. */
if (v > w) { t = v; v = w; w = t; }
m_out << (unsigned long)(u - p_array)
<< " " << (unsigned long)(v - p_array)
<< " " << (unsigned long)(w - p_array)
<< std::endl;
}
}
/* Next edge around u. */
e = Next(e, u);
} while (!Identical_refs(e, e_start));
}
}
Definition at line 84 of file dct.
{
delete [] p_array;
delete [] e_array;
delete [] free_list_e;
p_number = a_data.size();
//alloc :
p_array = new point[p_number];
// edges :
n_free_e = 3 * p_number; /* Eulers relation */
e_array = new edge[n_free_e];
if(!e_array) {
panic("Not enough memory\n");
return false;
}
typedef edge* ept;
free_list_e = new ept[n_free_e];
if(!free_list_e) {
panic("Not enough memory\n");
return false;
}
{edge* e = e_array;
for(unsigned int i=0;i<n_free_e;i++,e++) free_list_e[i] = e;}
point* pos = p_array;
std::vector< std::pair<real,real> >::const_iterator it;
for (it=a_data.begin();it!=a_data.end();++it,++pos) {
(*pos).x = (*it).first;
(*pos).y = (*it).second;
(*pos).entry_pt = 0;
}
// sort :
typedef point* ppt;
ppt* p_sorted = new ppt[p_number];
if(!p_sorted) {
panic("Not enough memory\n");
return false;
}
ppt* p_temp = new ppt[p_number];
if(!p_temp) {
panic("Not enough memory\n");
return false;
}
{for (unsigned int i = 0; i < p_number; i++) p_sorted[i] = p_array + i;}
merge_sort(p_sorted, p_temp, 0, p_number-1);
delete [] p_temp;
// triangulate :
edge* l_cw;
edge* r_ccw;
divide(p_sorted, 0, p_number-1, &l_cw, &r_ccw);
delete [] p_sorted;
return true;
}
1.7.5.1