1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#include <cstddef>
struct STACK_RECORD {
int nAnchorIndex, nFloaterIndex;
STACK_RECORD *precPrev;
} *m_pStack = null;
void StackPush( int nAnchorIndex, int nFloaterIndex );
int StackPop( int *pnAnchorIndex, int *pnFloaterIndex );
void ReducePoints( double *pPointsX, double *pPointsY, int nPointsCount,
int *pnUseFlag,
double dTolerance )
{
int nVertexIndex, nAnchorIndex, nFloaterIndex;
double dSegmentVecLength;
double dAnchorVecX, dAnchorVecY;
double dAnchorUnitVecX, dAnchorUnitVecY;
double dVertexVecLength;
double dVertexVecX, dVertexVecY;
double dProjScalar;
double dVertexDistanceToSegment;
double dMaxDistThisSegment;
int nVertexIndexMaxDistance;
nAnchorIndex = 0;
nFloaterIndex = nPointsCount - 1;
StackPush( nAnchorIndex, nFloaterIndex );
while ( StackPop( &nAnchorIndex, &nFloaterIndex ) ) {
// initialize line segment
dAnchorVecX = pPointsX[ nFloaterIndex ] - pPointsX[ nAnchorIndex ];
dAnchorVecY = pPointsY[ nFloaterIndex ] - pPointsY[ nAnchorIndex ];
dSegmentVecLength = sqrt( dAnchorVecX * dAnchorVecX
+ dAnchorVecY * dAnchorVecY );
dAnchorUnitVecX = dAnchorVecX / dSegmentVecLength;
dAnchorUnitVecY = dAnchorVecY / dSegmentVecLength;
// inner loop:
dMaxDistThisSegment = 0.0;
nVertexIndexMaxDistance = nAnchorIndex + 1;
for ( nVertexIndex = nAnchorIndex + 1; nVertexIndex < nFloaterIndex; nVertexIndex++ ) {
//compare to anchor
dVertexVecX = pPointsX[ nVertexIndex ] - pPointsX[ nAnchorIndex ];
dVertexVecY = pPointsY[ nVertexIndex ] - pPointsY[ nAnchorIndex ];
dVertexVecLength = sqrt( dVertexVecX * dVertexVecX
+ dVertexVecY * dVertexVecY );
//dot product:
dProjScalar = dVertexVecX * dAnchorUnitVecX + dVertexVecY * dAnchorUnitVecY;
if ( dProjScalar < 0.0 )
dVertexDistanceToSegment = dVertexVecLength;
else {
//compare to floater
dVertexVecX = pPointsX[ nVertexIndex ] - pPointsX[ nFloaterIndex ];
dVertexVecY = pPointsY[ nVertexIndex ] - pPointsY[ nFloaterIndex ];
dVertexVecLength = sqrt( dVertexVecX * dVertexVecX
+ dVertexVecY * dVertexVecY );
//dot product:
dProjScalar = dVertexVecX * (-dAnchorUnitVecX) + dVertexVecY * (-dAnchorUnitVecY);
if ( dProjScalar < 0.0 )
dVertexDistanceToSegment = dVertexVecLength;
else //calculate perpendicular distance to line (pythagorean theorem):
dVertexDistanceToSegment =
sqrt( fabs( dVertexVecLength * dVertexVecLength - dProjScalar * dProjScalar ) );
} //else
if ( dMaxDistThisSegment < dVertexDistanceToSegment ) {
dMaxDistThisSegment = dVertexDistanceToSegment;
nVertexIndexMaxDistance = nVertexIndex;
} //if
} //for (inner loop)
if ( dMaxDistThisSegment <= dTolerance ) { //use line segment
pnUseFlag[ nAnchorIndex ] = 1;
pnUseFlag[ nFloaterIndex ] = 1;
} //if use points
else {
StackPush( nAnchorIndex, nVertexIndexMaxDistance );
StackPush( nVertexIndexMaxDistance, nFloaterIndex );
} //else
} //while (outer loop)
} //end of ReducePoints() function
void StackPush( int nAnchorIndex, int nFloaterIndex )
{
STACK_RECORD *precPrev = m_pStack;
m_pStack = (STACK_RECORD *)malloc( sizeof(STACK_RECORD) );
m_pStack->nAnchorIndex = nAnchorIndex;
m_pStack->nFloaterIndex = nFloaterIndex;
m_pStack->precPrev = precPrev;
} //end of StackPush() function
int StackPop( int *pnAnchorIndex, int *pnFloaterIndex )
{
STACK_RECORD *precStack = m_pStack;
if ( precStack == null )
return 0; //false
*pnAnchorIndex = precStack->nAnchorIndex;
*pnFloaterIndex = precStack->nFloaterIndex;
m_pStack = precStack->precPrev;
free( precStack );
return 1; //true
} //end of StackPop() function
|
