monoTriangulationBackend.cc [plain text]
#include "monoTriangulation.h"
#include "polyUtil.h"
#include "backend.h"
#include "arc.h"
void reflexChain::outputFan(Real v[2], Backend* backend)
{
Int i;
backend->bgntfan();
backend->tmeshvert(v[0], v[1]);
if(isIncreasing) {
for(i=0; i<index_queue; i++)
{
backend->tmeshvert(queue[i][0], queue[i][1]);
}
}
else {
for(i=index_queue-1; i>=0; i--)
{
backend->tmeshvert(queue[i][0], queue[i][1]);
}
}
backend->endtfan();
}
void reflexChain::processNewVertex(Real v[2], Backend* backend)
{
Int i,j,k;
Int isReflex;
if(index_queue <=1){
insert(v);
return;
}
j=index_queue-1;
for(i=j; i>=1; i--) {
if(isIncreasing) {
isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
}
else {
isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
}
if(isReflex) {
break;
}
}
if(i<j)
{
backend->bgntfan();
backend->tmeshvert(v[0], v[1]);
if(isIncreasing) {
for(k=i; k<=j; k++)
{
backend->tmeshvert(queue[k][0], queue[k][1]);
}
}
else {
for(k=j; k>=i; k--)
{
backend->tmeshvert(queue[k][0], queue[k][1]);
}
}
backend->endtfan();
}
index_queue = i+1;
insert(v);
}
void monoTriangulationRec(Real* topVertex, Real* botVertex,
vertexArray* inc_chain, Int inc_current,
vertexArray* dec_chain, Int dec_current,
Backend* backend)
{
assert( inc_chain != NULL && dec_chain != NULL);
assert( ! (inc_current>=inc_chain->getNumElements() &&
dec_current>=dec_chain->getNumElements()));
Int inc_nVertices;
Int dec_nVertices;
Real** inc_array ;
Real** dec_array ;
Int i;
assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
if(inc_current>=inc_chain->getNumElements())
{
dec_array = dec_chain->getArray();
dec_nVertices = dec_chain->getNumElements();
reflexChain rChain(20,0);
rChain.processNewVertex(topVertex, backend);
for(i=dec_current; i<dec_nVertices; i++){
rChain.processNewVertex(dec_array[i], backend);
}
rChain.processNewVertex(botVertex, backend);
}
else if(dec_current>= dec_chain->getNumElements())
{
inc_array = inc_chain->getArray();
inc_nVertices= inc_chain->getNumElements();
reflexChain rChain(20,1);
rChain.processNewVertex(topVertex, backend);
for(i=inc_current; i<inc_nVertices; i++){
rChain.processNewVertex(inc_array[i], backend);
}
rChain.processNewVertex(botVertex, backend);
}
else
{
inc_array = inc_chain -> getArray();
dec_array = dec_chain -> getArray();
inc_nVertices= inc_chain->getNumElements();
dec_nVertices= dec_chain->getNumElements();
if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
{
reflexChain rChain(20, 0);
rChain.processNewVertex(topVertex, backend);
for(i=dec_current; i<dec_nVertices; i++)
{
if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
rChain.processNewVertex(dec_array[i], backend);
else
break;
}
rChain.outputFan(inc_array[inc_current], backend);
monoTriangulationRec(dec_array[i-1], botVertex,
inc_chain, inc_current,
dec_chain, i,
backend);
}
else
{
reflexChain rChain(20, 1);
rChain.processNewVertex(topVertex, backend);
for(i=inc_current; i<inc_nVertices; i++)
{
if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
rChain.processNewVertex(inc_array[i], backend);
else
break;
}
rChain.outputFan(dec_array[dec_current], backend);
monoTriangulationRec(inc_array[i-1], botVertex,
inc_chain, i,
dec_chain, dec_current,
backend);
}
}
}
void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
{
Int i;
Arc_ptr tempV;
Arc_ptr topV;
Arc_ptr botV;
topV = botV = loop;
for(tempV = loop->next; tempV != loop; tempV = tempV->next)
{
if(compFun(topV->tail(), tempV->tail())<0) {
topV = tempV;
}
if(compFun(botV->tail(), tempV->tail())>0) {
botV = tempV;
}
}
vertexArray inc_chain(20);
for(i=1; i<=topV->pwlArc->npts-2; i++) {
inc_chain.appendVertex(topV->pwlArc->pts[i].param);
}
for(tempV = topV->next; tempV != botV; tempV = tempV->next)
{
for(i=0; i<=tempV->pwlArc->npts-2; i++){
inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
}
}
vertexArray dec_chain(20);
for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
{
for(i=tempV->pwlArc->npts-2; i>=0; i--){
dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
}
}
for(i=botV->pwlArc->npts-2; i>=1; i--){
dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
}
monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
}
void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
vertexArray* inc_chain, Int inc_current,
vertexArray* dec_chain, Int dec_current,
Int (*compFun)(Real*, Real*),
Backend* backend)
{
assert( inc_chain != NULL && dec_chain != NULL);
assert( ! (inc_current>=inc_chain->getNumElements() &&
dec_current>=dec_chain->getNumElements()));
Int inc_nVertices;
Int dec_nVertices;
Real** inc_array ;
Real** dec_array ;
Int i;
assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
if(inc_current>=inc_chain->getNumElements())
{
dec_array = dec_chain->getArray();
dec_nVertices = dec_chain->getNumElements();
reflexChain rChain(20,0);
rChain.processNewVertex(topVertex, backend);
for(i=dec_current; i<dec_nVertices; i++){
rChain.processNewVertex(dec_array[i], backend);
}
rChain.processNewVertex(botVertex, backend);
}
else if(dec_current>= dec_chain->getNumElements())
{
inc_array = inc_chain->getArray();
inc_nVertices= inc_chain->getNumElements();
reflexChain rChain(20,1);
rChain.processNewVertex(topVertex, backend);
for(i=inc_current; i<inc_nVertices; i++){
rChain.processNewVertex(inc_array[i], backend);
}
rChain.processNewVertex(botVertex, backend);
}
else
{
inc_array = inc_chain -> getArray();
dec_array = dec_chain -> getArray();
inc_nVertices= inc_chain->getNumElements();
dec_nVertices= dec_chain->getNumElements();
if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
{
reflexChain rChain(20, 0);
rChain.processNewVertex(topVertex, backend);
for(i=dec_current; i<dec_nVertices; i++)
{
if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
rChain.processNewVertex(dec_array[i], backend);
else
break;
}
rChain.outputFan(inc_array[inc_current], backend);
monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
inc_chain, inc_current,
dec_chain, i,
compFun,
backend);
}
else
{
reflexChain rChain(20, 1);
rChain.processNewVertex(topVertex, backend);
for(i=inc_current; i<inc_nVertices; i++)
{
if(compFun(inc_array[i], dec_array[dec_current]) >0)
rChain.processNewVertex(inc_array[i], backend);
else
break;
}
rChain.outputFan(dec_array[dec_current], backend);
monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
inc_chain, i,
dec_chain, dec_current,
compFun,
backend);
}
}
}