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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
// File: polyfill.cxx
// Created: Thu Jun 12 16:46:18 1997
// Author: Prihodyko Michael
// <mpo@maniax>
// Modified by mpo, Tue Jul 8 15:45:06 1997
/*
// Description:
// Fill closed polygon with rotated lines
// Some about algorithm:
// rotate everything so that lines become horizontal,
// seek intersections of each line with each side of polygon
// then sort this array and each two points describe one part of line
// when doing it some special cases need to be resolved
// And then rotate it all in other direction
// Some about using it:
// With InitFillPolygon() intitialize computations
// Using GetLineOfFilledPolygon() you can get each line of filling
// Call of DoneFillPolygon() will free all allocated memory and will end your computations
// double *X, *Y - coordinates of a points of a polygon
// n = count of points
// Point(X[0],Y[0]) = Point(X[n-1],Y[n-1]) (if no return 0)
// step - step of filling
// gamma -- angle of rotating filling
// Returns 0 if failts
// else return number of lines
int __InitFillPolygon(double* X, double* Y, int n, double step = 1, double gamma = 0);
// Input: n = n-th point 0 <= n < number_of_lines
// Output: coordinates of a lines
// N - number of lines
// (X[2*i],Y[2*i+1]) - the i-th line , 0 <= i < N
// Return 0 if error
int __GetLineOfFilledPolygon (int n, int &N, double* &X, double* &Y);
// Done job and free allocated memory
void __DoneFillPolygon(void);
*/
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////// EXAMPLE OF USE //////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
/*
Standard_Integer count;
static double Xx[1024], Yy[1024];
// Fill Xx and Yy by the points
...
// Filling of polygon by lines
count = __InitFillPolygon(Xx, Yy, n, 0.25);
for (Standard_Integer j = 0; j < count; j++) {
Standard_Integer N;
double *Xxx, *Yyy;
if (__GetLineOfFilledPolygon(j, N, Xxx, Yyy))
for (int k = 0; k < N; k += 2)
DrawSegment(Xxx[k], Yyy[k], Xxx[k+1], Yyy[k+1]);
}
if (count) __DoneFillPolygon();
*/
//------------------ Implementation -----------------------
#include <stdlib.h>
#include <math.h>
#include <Standard_Stream.hxx>
#include <PlotMgt_fill.hxx>
double mpo_Xmin, mpo_Xmax, mpo_Ymin, mpo_Ymax; // BBox for polygon
double mpo_step; // step of filling
int mpo_size; // number of lines of filling (levels)
double **mpo_Xs, **mpo_Ys; // pointer to array of arrays
int *mpo_sizes; // mpo_sizes[i] number of points on level i
double *Xpts, *Ypts; //internal service
//
int mpo_sign(double a)
{
if (a>0) return 1;
else if (a == 0) return 0;
else return -1;
}
//
int mpo_next_sign(int j, int n)
{
j++;
while (mpo_sign(Ypts[j+1] - Ypts[j]) == 0)
if (j == n - 1) j = 0;
else j++;
// cout << mpo_sign(Ypts[j+1] - Ypts[j]) << "\t" << j << endl << flush;
return mpo_sign(Ypts[j+1] - Ypts[j]);
}
//
double mpo_min(double a, double b)
{
if (a > b) return b;
else return a;
}
//
double mpo_max(double a, double b)
{
if (a > b) return a;
else return b;
}
int __InitFillPolygon(double* X, double* Y, int n, double step, double gamma)
{
int i ;
int j ;
// checking
if ((n < 2) || (X[0] != X[n-1]) || (Y[0] != Y[n-1])) return 0;
mpo_step = step;
// create local variables
Xpts = (double*)malloc(sizeof(double)*(n+1));
Ypts = (double*)malloc(sizeof(double)*(n+1));
for ( i = 0; i < n; i++) Xpts[i] = X[i], Ypts[i] = Y[i];
Xpts[n] = X[1]; Ypts[n] = Y[1];
// rotate on gamma...
for (i = 0; i < n; i++)
{
double Yt = Ypts[i], Xt = Xpts[i];
Xpts[i] = Xt*cos(gamma) + Yt*sin(gamma);
Ypts[i] = -Xt*sin(gamma) + Yt*cos(gamma);
}
// allocating variables
mpo_Xmin = mpo_Xmax = Xpts[0];
mpo_Ymin = mpo_Ymax = Ypts[0];
for (i = 1; i < n; i++)
{
if (mpo_Xmin > Xpts[i]) mpo_Xmin = Xpts[i];
if (mpo_Xmax < Xpts[i]) mpo_Xmax = Xpts[i];
if (mpo_Ymin > Ypts[i]) mpo_Ymin = Ypts[i];
if (mpo_Ymax < Ypts[i]) mpo_Ymax = Ypts[i];
}
mpo_size = int( floor((mpo_Ymax - mpo_Ymin)/step) );
mpo_Xs = (double **)malloc(sizeof(double)*mpo_size);
mpo_Ys = (double **)malloc(sizeof(double)*mpo_size);
mpo_sizes = (int *)malloc(sizeof(int)*mpo_size);
for (i = 0; i < mpo_size; i++)
{
int k = 0;
double level = mpo_Ymax - step*i;
for ( j = 0; j < n-1; j++)
if (Ypts[j] - Ypts[j+1] != 0)
{
if (((level > mpo_min(Ypts[j], Ypts[j+1])) && (level < mpo_max(Ypts[j], Ypts[j+1])))
|| (level == Ypts[j])) k++;
if (level == Ypts[j+1])
if (mpo_sign(Ypts[j] - Ypts[j+1]) == mpo_next_sign(j, n)) k++;
}
mpo_Xs[i] = (double *)malloc(sizeof(double)*k);
mpo_Ys[i] = (double *)malloc(sizeof(double)*k);
for (j = 0; j < k; j++) mpo_Ys[i][j] = level;
mpo_sizes[i] = k;
}
// evaluating variables
for (i = 0; i < mpo_size; i++)
{
int k = 0;
double level = mpo_Ymax - step*i;
for ( j = 0; j < n-1; j++)
if (Ypts[j] - Ypts[j+1] != 0)
{
if (((level > mpo_min(Ypts[j], Ypts[j+1])) && (level < mpo_max(Ypts[j], Ypts[j+1])))
|| (level == Ypts[j]))
{
if (Ypts[j+1] - Ypts[j] == 0) mpo_Xs[i][k] = Xpts[j];
else mpo_Xs[i][k] = Xpts[j] + (Xpts[j+1] - Xpts[j])*(level - Ypts[j])/(Ypts[j+1] - Ypts[j]);
k++;
}
if (level == Ypts[j+1])
if (mpo_sign(Ypts[j] - Ypts[j+1]) == mpo_next_sign(j, n))
{
mpo_Xs[i][k] = Xpts[j+1]; k++;
}
}
if (k != mpo_sizes[i])
{
cout << "Number mismatch: k = " << k << "\tsizes[i] = " << mpo_sizes[i] << endl << flush;
free(Xpts); free(Ypts);
return 0;
}
}
// sorting
for (int m = 0; m < mpo_size; m++)
for (i = 0; i < mpo_sizes[m]-1; i++)
for ( j = 0; j < mpo_sizes[m]-1; j++)
if (mpo_Xs[m][j] > mpo_Xs[m][j+1])
{
double tmp;
tmp = mpo_Xs[m][j+1]; mpo_Xs[m][j+1] = mpo_Xs[m][j]; mpo_Xs[m][j] = tmp;
tmp = mpo_Ys[m][j+1]; mpo_Ys[m][j+1] = mpo_Ys[m][j]; mpo_Ys[m][j] = tmp;
}
// rotate on -gamma
for (i = 0; i < mpo_size; i++)
for ( j = 0; j < mpo_sizes[i]; j++)
{
double Yt = mpo_Ys[i][j], Xt = mpo_Xs[i][j];
mpo_Xs[i][j] = Xt*cos(gamma) - Yt*sin(gamma);
mpo_Ys[i][j] = Xt*sin(gamma) + Yt*cos(gamma);
}
// end
free(Xpts); free(Ypts);
return mpo_size;
}
int __GetLineOfFilledPolygon (int n, int &N, double* &X, double* &Y)
{
// cout << "GetLineOfFilledPolygon -- n = " << n << endl << flush;
if ((n < 0) || (n >= mpo_size)) return 0;
N = mpo_sizes[n];
X = mpo_Xs[n]; Y = mpo_Ys[n];
return 1;
}
void __DoneFillPolygon(void)
{
for (int i = 0; i < mpo_size; i++)
{
free(mpo_Xs[i]); free(mpo_Ys[i]);
}
free(mpo_sizes);
}
|
