一个平面网格划分的算法，只包含部分类型的图元。
一共包含四个文件：
1.文件HIFPoint.h
1
#pragma once
2
3#define DOUBLE_ZERO 0.01
4
5class HIFPoint
6
{
7
public:
8
HIFPoint(){}
9 HIFPoint(double a, double b) : x(a), y(b){}
10 HIFPoint(const HIFPoint& pt) : x(pt.x), y(pt.y){}
11
12 bool operator>(const HIFPoint& pt);
13 bool operator<(const HIFPoint& pt);
14 bool operator==(const HIFPoint& pt);
15 bool operator!=(const HIFPoint& pt);
16 bool operator>=(const HIFPoint& pt);
17 bool operator<=(const HIFPoint& pt);
18
19 void set(const double& a, const double& b);
20
21 void swap(HIFPoint& pt);
22
23public:
24 static void swap(HIFPoint& pt1, HIFPoint& pt2)
25 {
26 HIFPoint pt = pt1;
27 pt1 = pt2;
28 pt2 = pt;
29
}
30
31 static HIFPoint interpolate(double para, const HIFPoint& pt1, const HIFPoint& pt2)
32 {
33 return HIFPoint((1 - para) * pt1.x + para * pt2.x, (1 - para) * pt1.y + para * pt2.y);
34 }
35
36public:
37 double x;
38 double y;
39
};
40
41
42//计算由三点确定圆的圆心
43bool Get3PointCirCenter(const HIFPoint& pt1, const HIFPoint& pt2, const HIFPoint& pt3, HIFPoint& ptCenter);
2.文件HIFPoint.cpp
1#include "HIFPoint.h"
2#include <math.h>
3
4bool HIFPoint::operator>(const HIFPoint& pt)
5{
6 if (x > pt.x && y > pt.y)
7 {
8 return true;
9 }
10 else
11 {
12 return false;
13 }
14}
15
16bool HIFPoint::operator<(const HIFPoint& pt)
17{
18 if (x < pt.x && y < pt.y)
19 {
20 return true;
21 }
22 else
23 {
24 return false;
25 }
26}
27
28bool HIFPoint::operator==(const HIFPoint& pt)
29{
30 if (fabs(x - pt.x) < DOUBLE_ZERO &&
31 fabs(y - pt.y) < DOUBLE_ZERO)
32 {
33 return true;
34 }
35 else
36 {
37 return false;
38 }
39}
40
41bool HIFPoint::operator!=(const HIFPoint& pt)
42{
43 if (fabs(x - pt.x) > DOUBLE_ZERO ||
44 fabs(y - pt.y) > DOUBLE_ZERO)
45 {
46 return true;
47 }
48 else
49 {
50 return false;
51 }
52}
53
54bool HIFPoint::operator>=(const HIFPoint& pt)
55{
56 if (pt.x - x < DOUBLE_ZERO &&
57 pt.y - y < DOUBLE_ZERO)
58 {
59 return true;
60 }
61 else
62 {
63 return false;
64 }
65}
66
67bool HIFPoint::operator<=(const HIFPoint& pt)
68{
69 if (x - pt.x < DOUBLE_ZERO &&
70 y - pt.y < DOUBLE_ZERO)
71 {
72 return true;
73 }
74 else
75 {
76 return false;
77 }
78}
79
80void HIFPoint::set(const double& a, const double& b)
81{
82 x = a;
83 y = b;
84}
85
86void HIFPoint::swap(HIFPoint& pt)
87{
88 HIFPoint pointTemp;
89 pointTemp = pt;
90
91 pt.x = x;
92 pt.y = y;
93
94 x = pointTemp.x;
95 y = pointTemp.y;
96}
97
98bool Get3PointCirCenter(const HIFPoint& pt1, const HIFPoint& pt2, const HIFPoint& pt3, HIFPoint& ptCenter)
99{
100 double d1 = (pt1.y - pt2.y) * (pt2.x - pt3.x);
101 double d2 = (pt2.y - pt3.y) * (pt1.x - pt2.x);
102 if (fabs(d1 - d2) < DOUBLE_ZERO || fabs(d1 + d2) < DOUBLE_ZERO)
103 {
104 return false;
105 }
106
107 double dA1 = 2 * (pt1.x - pt2.x);
108 double dB1 = 2 * (pt1.y - pt2.y);
109 double dC1 = (pt2.y + pt1.y) * (pt2.y - pt1.y) + (pt2.x + pt1.x) * (pt2.x - pt1.x);
110
111 double dA2 = 2 * (pt2.x - pt3.x);
112 double dB2 = 2 * (pt2.y - pt3.y);
113 double dC2 = (pt3.y + pt2.y) * (pt3.y - pt2.y) + (pt3.x + pt2.x) * (pt3.x - pt2.x);
114
115 ptCenter.x = (dB1 * dC2 - dB2 * dC1)/(dA1 * dB2 - dA2 * dB1);
116 ptCenter.y = (dA2 * dC1 - dA1 * dC2)/(dA1 * dB2 - dA2 * dB1);
117
118 return true;
119}
3.文件HIFGridGenerator.h
1#pragma once
2#include "HIFPoint.h"
3
4#include <set>
5#include <vector>
6using namespace std;
7
8class HIFGridGenerator
9{
10public:
11 HIFGridGenerator(void);
12 ~HIFGridGenerator(void);
13
14 void SetRegion(const HIFPoint& pointMin, const HIFPoint& pointMax);
15 void GetRegion(HIFPoint& pointMin, HIFPoint& pointMax) const;
16
17 void SetColRowNum(const int& iCol, const int& iRow);
18 int GetColNum() const{ return m_iColNum; }
19 int GetRowNum() const{ return m_iRowNum; }
20
21 /**///////////////////////////////////////////////////////////////////////////
22 //处理图元，返回与它们相交的网格编号，编号：从左至右，由下到上，从0开始
23 void ProcessLineseg(HIFPoint ptStart, HIFPoint ptEnd, set<int>& setGridNum);//函数中有swap,所以没有用HIFPoint&
24 void ProcessPolyline(vector<HIFPoint>& vecPoint, set<int>& setGridNum);
25 void ProcessPolygon(vector<HIFPoint>& vecPoint, set<int>& setGridNum);
26 void ProcessCircle(const HIFPoint& ptCenter, double dRadius, set<int>& setGridNum);
27 void ProcessCircle(const HIFPoint& ptCenter, const HIFPoint& pt, set<int>& setGridNum);
28 void ProcessCircularArc(const HIFPoint& pt1, const HIFPoint& pt2, const HIFPoint& pt3, set<int>& setGridNum);//pt1, pt3是弧的两个端点
29
30 /**///////////////////////////////////////////////////////////////////////////
31 void FillParallelogram(const HIFPoint& ptUp, const HIFPoint& ptLeft, const HIFPoint& ptRight, set<int>& setGridNum);
32
33public:
34 HIFPoint m_pointMin;
35 HIFPoint m_pointMax;
36
37 int m_iColNum;//划分网格的行数
38 int m_iRowNum;//划分网格的列数
39
40 double m_dHoriUnit;
41 double m_dVertUnit;
42};
4.文件HIFGridGenerator.cpp
1#include "HIFGridGenerator.h"
2#include <math.h>
3#include <assert.h>
4
5
6HIFGridGenerator::HIFGridGenerator(void)
7{
8 m_iColNum = 0;
9 m_iRowNum = 0;
10 m_dHoriUnit = 0.0;
11 m_dVertUnit = 0.0;
12}
13
14HIFGridGenerator::~HIFGridGenerator(void)
15{
16}
17
18void HIFGridGenerator::SetRegion(const HIFPoint& pointMin, const HIFPoint& pointMax)
19{
20 m_pointMin.x = pointMin.x < pointMax.x ? pointMin.x : pointMax.x;
21 m_pointMin.y = pointMin.y < pointMax.y ? pointMin.y : pointMax.y;
22 m_pointMax.x = pointMin.x > pointMax.x ? pointMin.x : pointMax.x;
23 m_pointMax.y = pointMin.y > pointMax.y ? pointMin.y : pointMax.y;
24}
25
26void HIFGridGenerator::GetRegion(HIFPoint& pointMin, HIFPoint& pointMax) const
27{
28 pointMin = m_pointMin;
29 pointMax = m_pointMax;
30}
31
32void HIFGridGenerator::SetColRowNum(const int& iCol, const int& iRow)
33{
34 m_iColNum = iCol;
35 m_iRowNum = iRow;
36
37 m_dHoriUnit = (m_pointMax.x - m_pointMin.x)/m_iRowNum;
38 m_dVertUnit = (m_pointMax.y - m_pointMin.y)/m_iColNum;
39}
40
41void HIFGridGenerator::ProcessLineseg(HIFPoint ptStart, HIFPoint ptEnd, set<int>& setGridNum)
42{
43 assert(ptStart >= m_pointMin && ptStart <= m_pointMax);
44 assert(ptEnd >= m_pointMin && ptEnd <= m_pointMax);
45
46 //setGridNum.clear();
47
48 double dx = ptEnd.x - ptStart.x;
49 double dy = ptEnd.y - ptStart.y;
50
51 int iGridNum = 0;
52
53 if (fabs(dx) < DOUBLE_ZERO)
54 {
55 //线段与Y轴平行
56 if (ptStart.y > ptEnd.y)
57 {
58 HIFPoint::swap(ptStart, ptEnd);
59 }
60
61 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
62 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
63 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
64 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
65
66 if (iStartY == iEndY)
67 {
68 if (fabs(ptStart.x - m_pointMax.x) < DOUBLE_ZERO)
69 {
70 if (fabs(ptStart.y - m_pointMax.y) < DOUBLE_ZERO)
71 {
72 iGridNum = iStartX - 1 + (iEndY - 1) * m_iRowNum;
73 setGridNum.insert(iGridNum);
74 return;
75 }
76 else
77 {
78 iGridNum = iStartX - 1 + iEndY * m_iRowNum;
79 setGridNum.insert(iGridNum);
80 return;
81 }
82 }
83 else
84 {
85 iGridNum = iStartX + iEndY * m_iRowNum;
86 setGridNum.insert(iGridNum);
87 return;
88 }
89 }
90
91 for (int i = iStartY; i < iEndY; i++)
92 {
93 if (fabs(ptStart.x - m_pointMax.x) < DOUBLE_ZERO)
94 {
95 iGridNum = iStartX - 1 + i * m_iRowNum;
96 setGridNum.insert(iGridNum);
97 }
98 else
99 {
100 iGridNum = iStartX + i * m_iRowNum;
101 setGridNum.insert(iGridNum);
102 }
103 }
104
105 if (fabs(ptEnd.y - iEndY * m_dVertUnit) < DOUBLE_ZERO)
106 {
107 if (fabs(ptStart.x - m_pointMax.x) < DOUBLE_ZERO)
108 {
109 iGridNum = iEndX - 1 + (iEndY - 1) * m_iRowNum;
110 setGridNum.insert(iGridNum);
111 }
112 else
113 {
114 iGridNum = iEndX + (iEndY - 1) * m_iRowNum;
115 setGridNum.insert(iGridNum);
116 }
117 }
118 }
119 else if (fabs(dy) < DOUBLE_ZERO)
120 {
121 //线段与X轴平行
122 if (ptStart.x > ptEnd.x)
123 {
124 HIFPoint::swap(ptStart, ptEnd);
125 }
126
127 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
128 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
129 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
130 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
131
132 if (iStartX == iEndX)
133 {
134 if (fabs(ptStart.y - m_pointMax.y) < DOUBLE_ZERO)
135 {
136 if (fabs(ptStart.x - m_pointMax.x) < DOUBLE_ZERO)
137 {
138 iGridNum = iStartX - 1 + (iEndY - 1) * m_iRowNum;
139 setGridNum.insert(iGridNum);
140 return;
141 }
142 else
143 {
144 iGridNum = iStartX + (iEndY - 1) * m_iRowNum;
145 setGridNum.insert(iGridNum);
146 return;
147 }
148 }
149 else
150 {
151 iGridNum = iStartX + iEndY * m_iRowNum;
152 setGridNum.insert(iGridNum);
153 return;
154 }
155 }
156
157 for (int i = iStartX; i < iEndX; i++)
158 {
159 if (fabs(ptStart.y - m_pointMax.y) < DOUBLE_ZERO)
160 {
161 iGridNum = i + (iStartY - 1) * m_iRowNum;
162 setGridNum.insert(iGridNum);
163 }
164 else
165 {
166 iGridNum = i + iStartY * m_iRowNum;
167 setGridNum.insert(iGridNum);
168 }
169 }
170
171 if (abs(ptEnd.x - iEndX * m_dHoriUnit) < DOUBLE_ZERO)
172 {
173 if (fabs(ptStart.y - m_pointMax.y) < DOUBLE_ZERO)
174 {
175 iGridNum = iEndX - 1 + (iEndY - 1) * m_iRowNum;
176 setGridNum.insert(iGridNum);
177 }
178 else
179 {
180 iGridNum = iEndX - 1 + iEndY * m_iRowNum;
181 setGridNum.insert(iGridNum);
182 }
183 }
184 }
185 else
186 {
187 //直线与X\Y轴都不平行
188 double dSlope = dy/dx;
189 int m = fabs(ptStart.x - ptEnd.x)/m_dHoriUnit;
190 int n = fabs(ptStart.y - ptEnd.y)/m_dVertUnit;
191
192 if (dSlope > 0 && m >= n)
193 {
194 if (ptStart.x > ptEnd.x)
195 {
196 HIFPoint::swap(ptStart, ptEnd);
197 }
198
199 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
200 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
201 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
202 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
203
204 iGridNum = iStartX + iStartY * m_iRowNum;
205 setGridNum.insert(iGridNum);
206
207 double dSeg1LenHori = m_dHoriUnit - (ptStart.x - iStartX * m_dHoriUnit);//起始点网格中那段线的水平长度
208 HIFPoint ptNext(ptStart.x + dSeg1LenHori, ptStart.y + dSeg1LenHori * dSlope);//直线与竖向网格的第一个交点
209
210 double dDeltaY = dSlope * m_dHoriUnit;
211 int iPtNextX ,iPtNextY;
212 while (ptNext.x < ptEnd.x)
213 {
214 iPtNextX = (ptNext.x - m_pointMin.x)/m_dHoriUnit;
215 iPtNextY = (ptNext.y - m_pointMin.y)/m_dVertUnit;
216
217 if (fabs(ptNext.y - iPtNextY * m_dVertUnit) < DOUBLE_ZERO)
218 {
219 //ptNext在网格点上
220 iGridNum = iPtNextX + iPtNextY * m_iRowNum;
221 setGridNum.insert(iGridNum);
222 }
223 else
224 {
225 iGridNum = iPtNextX + iPtNextY * m_iRowNum - 1;
226 setGridNum.insert(iGridNum);
227 iGridNum++;
228 setGridNum.insert(iGridNum);
229 }
230
231 ptNext.x += m_dHoriUnit;
232 ptNext.y += dDeltaY;
233 }
234
235 if (ptNext == ptEnd)
236 {
237 if (fabs(ptEnd.y - iEndY * m_dVertUnit) < DOUBLE_ZERO)
238 {
239 iGridNum = iEndX - 1 + (iEndY - 1) * m_iRowNum;
240 setGridNum.insert(iGridNum);
241 }
242 else
243 {
244 iGridNum = iEndX - 1 + iEndY * m_iRowNum;
245 setGridNum.insert(iGridNum);
246 }
247 }
248 else
249 {
250 if (fabs(ptEnd.y - iEndY * m_dVertUnit) < DOUBLE_ZERO)
251 {
252 iGridNum = iEndX + (iEndY - 1) * m_iRowNum;
253 setGridNum.insert(iGridNum);
254 }
255 else
256 {
257 iGridNum = iEndX + iEndY * m_iRowNum;
258 setGridNum.insert(iGridNum);
259 }
260 }
261 }
262 else if (dSlope < 0 && m >= n)
263 {
264 if (ptStart.x > ptEnd.x)
265 {
266 HIFPoint::swap(ptStart, ptEnd);
267 }
268
269 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
270 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
271 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
272 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
273
274 if (fabs(ptStart.y - iStartY * m_dVertUnit) < DOUBLE_ZERO)
275 {
276 iGridNum = iStartX + (iStartY - 1) * m_iRowNum;
277 setGridNum.insert(iGridNum);
278 }
279 else
280 {
281 iGridNum = iStartX + iStartY * m_iRowNum;
282 setGridNum.insert(iGridNum);
283 }
284
285 double dSeg1LenHori = m_dHoriUnit - (ptStart.x - iStartX * m_dHoriUnit);
286 HIFPoint ptNext(ptStart.x + dSeg1LenHori, ptStart.y + dSeg1LenHori * dSlope);
287
288 double dDeltaY = dSlope * m_dHoriUnit;
289 int iPtNextX ,iPtNextY;
290 while (ptNext.x < ptEnd.x)
291 {
292 iPtNextX = (ptNext.x - m_pointMin.x)/m_dHoriUnit;
293 iPtNextY = (ptNext.y - m_pointMin.y)/m_dVertUnit;
294
295 if (fabs(ptNext.y - iPtNextY * m_dVertUnit) < DOUBLE_ZERO)
296 {
297 //ptNext在网格点上
298 iGridNum = iPtNextX - 1 + iPtNextY * m_iRowNum;
299 setGridNum.insert(iGridNum);
300 }
301 else
302 {
303 iGridNum = iPtNextX + iPtNextY * m_iRowNum - 1;
304 setGridNum.insert(iGridNum);
305 iGridNum++;
306 setGridNum.insert(iGridNum);
307 }
308
309 ptNext.x += m_dHoriUnit;
310 ptNext.y += dDeltaY;
311 }
312
313 if (ptNext == ptEnd)
314 {
315 iGridNum = iEndX - 1 + iEndY * m_iRowNum;
316 setGridNum.insert(iGridNum);
317 }
318 else
319 {
320 iGridNum = iEndX + iEndY * m_iRowNum;
321 setGridNum.insert(iGridNum);
322 }
323 }
324 else if (dSlope > 0 && m < n)
325 {
326 if (ptStart.y > ptEnd.y)
327 {
328 HIFPoint::swap(ptStart, ptEnd);
329 }
330
331 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
332 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
333 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
334 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
335
336 iGridNum = iStartX + iStartY * m_iRowNum;
337 setGridNum.insert(iGridNum);
338
339 double dSeg1LenVert = m_dVertUnit - (ptStart.y - iStartY * m_dVertUnit);
340 HIFPoint ptNext(ptStart.x + dSeg1LenVert/dSlope, ptStart.y + dSeg1LenVert);
341
342 double dDeltaX = m_dVertUnit/dSlope;
343 int iPtNextX ,iPtNextY;
344 while (ptNext.y < ptEnd.y)
345 {
346 iPtNextX = (ptNext.x - m_pointMin.x)/m_dHoriUnit;
347 iPtNextY = (ptNext.y - m_pointMin.y)/m_dVertUnit;
348
349 if (fabs(ptNext.y - iPtNextY * m_dHoriUnit) < DOUBLE_ZERO)
350 {
351 //ptNext在网格点上
352 iGridNum = iPtNextX + iPtNextY * m_iRowNum;
353 setGridNum.insert(iGridNum);
354 }
355 else
356 {
357 iGridNum = iPtNextX + (iPtNextY - 1) * m_iRowNum;
358 setGridNum.insert(iGridNum);
359 iGridNum += m_iRowNum;
360 setGridNum.insert(iGridNum);
361 }
362
363 ptNext.x += dDeltaX;
364 ptNext.y += m_dVertUnit;
365 }
366
367 if (ptNext == ptEnd)
368 {
369 if (fabs(ptEnd.x - iEndX * m_dHoriUnit) < DOUBLE_ZERO)
370 {
371 iGridNum = iEndX - 1 + (iEndY - 1) * m_iRowNum;
372 setGridNum.insert(iGridNum);
373 }
374 else
375 {
376 iGridNum = iEndX + (iEndY - 1) * m_iRowNum;
377 setGridNum.insert(iGridNum);
378 }
379 }
380 else
381 {
382 if (fabs(ptEnd.x - iEndX * m_dHoriUnit) < DOUBLE_ZERO)
383 {
384 iGridNum = iEndX - 1 + iEndY * m_iRowNum;
385 setGridNum.insert(iGridNum);
386 }
387 else
388 {
389 iGridNum = iEndX + iEndY * m_iRowNum;
390 setGridNum.insert(iGridNum);
391 }
392 }
393 }
394 else if (dSlope < 0 && m < n)
395 {
396 if (ptStart.y > ptEnd.y)
397 {
398 HIFPoint::swap(ptStart, ptEnd);
399 }
400
401 int iStartX = (ptStart.x - m_pointMin.x)/m_dHoriUnit;
402 int iStartY = (ptStart.y - m_pointMin.y)/m_dVertUnit;
403 int iEndX = (ptEnd.x - m_pointMin.x)/m_dHoriUnit;
404 int iEndY = (ptEnd.y - m_pointMin.y)/m_dVertUnit;
405
406 if (fabs(ptStart.x - iStartX * m_dHoriUnit) < DOUBLE_ZERO)
407 {
408 iGridNum = iStartX - 1 + iStartY * m_iRowNum;
409 setGridNum.insert(iGridNum);
410 }
411 else
412 {
413 iGridNum = iStartX + iStartY * m_iRowNum;
414 setGridNum.insert(iGridNum);
415 }
416
417 double dSeg1LenVert = m_dVertUnit - (ptStart.y - iStartY * m_dVertUnit);
418 HIFPoint ptNext(ptStart.x + dSeg1LenVert/dSlope, ptStart.y + dSeg1LenVert);
419
420 double dDeltaX = m_dVertUnit/dSlope;
421 int iPtNextX ,iPtNextY;
422 while (ptNext.y < ptEnd.y)
423 {
424 iPtNextX = (ptNext.x - m_pointMin.x)/m_dHoriUnit;
425 iPtNextY = (ptNext.y - m_pointMin.y)/m_dVertUnit;
426
427 if (fabs(ptNext.x - iPtNextX * m_dHoriUnit) < DOUBLE_ZERO)
428 {
429 //ptNext在网格点上
430 iGridNum = iPtNextX - 1 + iPtNextY * m_iRowNum;
431 setGridNum.insert(iGridNum);
432 }
433 else
434 {
435 iGridNum = iPtNextX + (iPtNextY - 1) * m_iRowNum;
436 setGridNum.insert(iGridNum);
437 iGridNum += m_iRowNum;
438 setGridNum.insert(iGridNum);
439 }
440
441 ptNext.x += dDeltaX;
442 ptNext.y += m_dVertUnit;
443 }
444
445 if (ptNext == ptEnd)
446 {
447 iGridNum = iEndX + (iEndY - 1) * m_iRowNum;
448 setGridNum.insert(iGridNum);
449 }
450 else
451 {
452 iGridNum = iEndX + iEndY * m_iRowNum;
453 setGridNum.insert(iGridNum);
454 }
455 }
456 }
457}
458
459void HIFGridGenerator::ProcessPolyline(vector<HIFPoint>& vecPoint, set<int>& setGridNum)
460{
461 int iCount = vecPoint.size() - 1;
462 for (int i = 0; i < iCount; i++)
463 {
464 ProcessLineseg(vecPoint[i], vecPoint[i+1], setGridNum);
465 }
466}
467
468void HIFGridGenerator::ProcessPolygon(vector<HIFPoint>& vecPoint, set<int>& setGridNum)
469{
470 int iCount = vecPoint.size() - 1;
471 for (int i = 0; i < iCount; i++)
472 {
473 ProcessLineseg(vecPoint[i], vecPoint[i+1], setGridNum);
474 }
475
476 ProcessLineseg(vecPoint[iCount], vecPoint[0], setGridNum);
477}
478
479void HIFGridGenerator::ProcessCircle(const HIFPoint& ptCenter, double dRadius, set<int>& setGridNum)
480{
481 assert(ptCenter.x - dRadius >= m_pointMin.x && ptCenter.x + dRadius <= m_pointMax.x);
482 assert(ptCenter.y - dRadius >= m_pointMin.y && ptCenter.y + dRadius <= m_pointMax.y);
483
484 HIFPoint ptLeft(ptCenter.x - dRadius, ptCenter.y);
485 HIFPoint ptRight(ptCenter.x + dRadius, ptCenter.y);
486 HIFPoint ptUp(ptCenter.x, ptCenter.y + dRadius);
487 HIFPoint ptDown(ptCenter.x, ptCenter.y - dRadius);
488
489 int iGridNum = 0;
490
491 int iLeftX = (ptLeft.x - m_pointMin.x)/m_dHoriUnit;
492 int iRightX = (ptRight.x - m_pointMin.x)/m_dHoriUnit;
493 int iDownY = (ptDown.y - m_pointMin.y)/m_dVertUnit;
494 int iUpY = (ptUp.y - m_pointMin.y)/m_dVertUnit;
495
496 double dDeltaX, dDeltaY, dX, dY;
497 HIFPoint pt1, pt2;
498 int iPt1X, iPt2X, iPt1Y, iPt2Y;
499
500 for (int i = iLeftX + 1; i < iRightX; i++)
501 {
502 dX = i * m_dHoriUnit;
503 dDeltaY = sqrt(dRadius * dRadius - pow(ptCenter.x - dX, 2));
504 pt1 = HIFPoint(dX, ptCenter.y - dDeltaY);
505 pt2 = HIFPoint(dX, ptCenter.y + dDeltaY);
506
507 iPt1X = (pt1.x - m_pointMin.x)/m_dHoriUnit;
508 iPt2X = (pt2.x - m_pointMin.x)/m_dHoriUnit;
509 iPt1Y = (pt1.y - m_pointMin.y)/m_dVertUnit;
510 iPt2Y = (pt2.y - m_pointMin.y)/m_dVertUnit;
511
512 if (fabs(pt1.y - iPt1Y * m_dVertUnit) < DOUBLE_ZERO)
513 {
514 if (fabs(pt1.x - ptCenter.x) < DOUBLE_ZERO)
515 {
516 iGridNum = iPt1X + iPt1Y * m_iRowNum;
517 setGridNum.insert(iGridNum);
518 iGridNum--;
519 setGridNum.insert(iGridNum);
520 }
521 else if (pt1.x < ptCenter.x)
522 {
523 iGridNum = iPt1X - 1 + iPt1Y * m_iRowNum;
524 setGridNum.insert(iGridNum);
525 iGridNum = iPt1X + (iPt1Y - 1) * m_iRowNum;
526 setGridNum.insert(iGridNum);
527 }
528 else
529 {
530 iGridNum = iPt1X + iPt1Y * m_iRowNum;
531 setGridNum.insert(iGridNum);
532 iGridNum = iPt1X - 1 + (iPt1Y - 1) * m_iRowNum;
533 setGridNum.insert(iGridNum);
534 }
535 }
536 else
537 {
538 iGridNum = iPt1X + iPt1Y * m_iRowNum;
539 setGridNum.insert(iGridNum);
540 iGridNum--;
541 setGridNum.insert(iGridNum);
542 }
543
544 if (fabs(pt2.y - iPt2Y * m_dVertUnit) < DOUBLE_ZERO)
545 {
546 if (fabs(pt2.x - ptCenter.x) < DOUBLE_ZERO)
547 {
548 iGridNum = iPt2X + (iPt2Y - 1) * m_iRowNum;
549 setGridNum.insert(iGridNum);
550 iGridNum--;
551 setGridNum.insert(iGridNum);
552 }
553 else if (pt2.x < ptCenter.x)
554 {
555 iGridNum = iPt2X + iPt2Y * m_iRowNum;
556 setGridNum.insert(iGridNum);
557 iGridNum = iPt2X - 1 + (iPt2Y - 1) * m_iRowNum;
558 setGridNum.insert(iGridNum);
559 }
560 else
561 {
562 iGridNum = iPt2X - 1 + iPt2Y * m_iRowNum;
563 setGridNum.insert(iGridNum);
564 iGridNum = iPt2X + (iPt2Y - 1) * m_iRowNum;
565 setGridNum.insert(iGridNum);
566 }
567 }
568 else
569 {
570 iGridNum = iPt2X + iPt2Y * m_iRowNum;
571 setGridNum.insert(iGridNum);
572 iGridNum--;
573 setGridNum.insert(iGridNum);
574 }
575 }
576
577 for (int i = iDownY + 1; i < iUpY; i++)
578 {
579 dY = i * m_dVertUnit;
580 dDeltaX = sqrt(dRadius * dRadius - pow(ptCenter.y - dY, 2));
581 pt1 = HIFPoint(ptCenter.x - dDeltaX, dY);
582 pt2 = HIFPoint(ptCenter.x + dDeltaX, dY);
583
584 iPt1X = (pt1.x - m_pointMin.x)/m_dHoriUnit;
585 iPt2X = (pt2.x - m_pointMin.x)/m_dHoriUnit;
586 iPt1Y = (pt1.y - m_pointMin.y)/m_dVertUnit;
587 iPt2Y = (pt2.y - m_pointMin.y)/m_dVertUnit;
588
589 if (fabs(pt1.x - iPt1X * m_dHoriUnit) < DOUBLE_ZERO)
590 {
591 if (fabs(pt1.y - ptCenter.y) < DOUBLE_ZERO)
592 {
593 iGridNum = iPt1X + iPt1Y * m_iRowNum;
594 setGridNum.insert(iGridNum);
595 iGridNum = iPt1X + (iPt1Y - 1) * m_iRowNum;
596 setGridNum.insert(iGridNum);
597 }
598 else if (pt1.y < ptCenter.y)
599 {
600 iGridNum = iPt1X - 1 + iPt1Y * m_iRowNum;
601 setGridNum.insert(iGridNum);
602 iGridNum = iPt1X + (iPt1Y - 1) * m_iRowNum;
603 setGridNum.insert(iGridNum);
604 }
605 else
606 {
607 iGridNum = iPt1X + iPt1Y * m_iRowNum;
608 setGridNum.insert(iGridNum);
609 iGridNum = iPt1X - 1 + (iPt1Y - 1) * m_iRowNum;
610 setGridNum.insert(iGridNum);
611 }
612 }
613 else
614 {
615 iGridNum = iPt1X + iPt1Y * m_iRowNum;
616 setGridNum.insert(iGridNum);
617 iGridNum = iPt1X + (iPt1Y - 1) * m_iRowNum;
618 setGridNum.insert(iGridNum);
619 }
620
621 if (fabs(pt2.x - iPt2X * m_dHoriUnit) < DOUBLE_ZERO)
622 {
623 if (fabs(pt2.y - ptCenter.y) < DOUBLE_ZERO)
624 {
625 iGridNum = iPt2X - 1 + iPt2Y * m_iRowNum;
626 setGridNum.insert(iGridNum);
627 iGridNum = iPt2X - 1 + (iPt2Y - 1) * m_iRowNum;
628 setGridNum.insert(iGridNum);
629 }
630 else if (pt2.y < ptCenter.y)
631 {
632 iGridNum = iPt2X + iPt2Y * m_iRowNum;
633 setGridNum.insert(iGridNum);
634 iGridNum = iPt2X - 1 + (iPt2Y - 1) * m_iRowNum;
635 setGridNum.insert(iGridNum);
636 }
637 else
638 {
639 iGridNum = iPt2X - 1 + iPt2Y * m_iRowNum;
640 setGridNum.insert(iGridNum);
641 iGridNum = iPt2X + (iPt2Y - 1) * m_iRowNum;
642 setGridNum.insert(iGridNum);
643 }
644 }
645 else
646 {
647 iGridNum = iPt2X + iPt2Y * m_iRowNum;
648 setGridNum.insert(iGridNum);
649 iGridNum = iPt2X + (iPt2Y - 1) * m_iRowNum;
650 setGridNum.insert(iGridNum);
651 }
652 }
653}
654
655void HIFGridGenerator::ProcessCircle(const HIFPoint& ptCenter, const HIFPoint& pt, set<int>& setGridNum)
656{
657 double dRadius = sqrt(pow(ptCenter.x - pt.x, 2) + pow(ptCenter.y - pt.y, 2));
658
659 ProcessCircle(ptCenter, dRadius, setGridNum);
660}
661
662void HIFGridGenerator::ProcessCircularArc(const HIFPoint& pt1, const HIFPoint& pt2, const HIFPoint& pt3, set<int>& setGridNum)
663{
664 HIFPoint ptCenter;
665 bool bRet = Get3PointCirCenter(pt1, pt2, pt3, ptCenter);
666 if (!bRet)
667 {
668 return;
669 }
670
671 double dTheta1 = asin((pt1.y - ptCenter.y)/(pt1.x - ptCenter.x));
672 double dTheta2 = asin((pt2.y - ptCenter.y)/(pt2.x - ptCenter.x));
673 double dTheta3 = asin((pt3.y - ptCenter.y)/(pt3.x - ptCenter.x));
674
675}
676
677void HIFGridGenerator::FillParallelogram(const HIFPoint& ptUp, const HIFPoint& ptLeft, const HIFPoint& ptRight, set<int>& setGridNum)
678{
679 HIFPoint ptUpRight(ptUp.x + ptRight.x - ptLeft.x, ptUp.y + ptRight.y - ptLeft.y);
680
681 ProcessLineseg(ptUp, ptLeft, setGridNum);
682 ProcessLineseg(ptLeft, ptRight, setGridNum);
683 ProcessLineseg(ptRight, ptUpRight, setGridNum);
684 ProcessLineseg(ptUp, ptUpRight, setGridNum);
685
686 double dLength1 = sqrt(pow(ptUp.x - ptLeft.x, 2) + pow(ptUp.y - ptLeft.y, 2));
687 double dMinUnit = m_dHoriUnit < m_dVertUnit ? m_dHoriUnit : m_dVertUnit;
688 double dMultiple = dLength1/dMinUnit;
689 int n = dMultiple;
690
691 HIFPoint pt1, pt2;
692 double para;
693 for (int i = 1; i < n; i++)
694 {
695 para = (double)i/n;
696 pt1 = HIFPoint::interpolate(para, ptUp, ptLeft);
697 pt2 = HIFPoint::interpolate(para, ptUpRight, ptRight);
698 ProcessLineseg(pt1, pt2, setGridNum);
699 }
700}
701