SHOW:
|
|
- or go back to the newest paste.
1 | #include "Graphics.h" | |
2 | #include "StdAfx.h" | |
3 | #include "GF.h" | |
4 | #include <functional> | |
5 | #include <vector> | |
6 | #include <algorithm> | |
7 | #include <bitset> | |
8 | #include <cstdlib> | |
9 | #include <cstring> | |
10 | #include <string> | |
11 | #include <string.h> | |
12 | #include <random> | |
13 | #include <iostream> | |
14 | ||
15 | #define all(x) (x).begin(),(x).end() | |
16 | ||
17 | #ifndef M_PI | |
18 | const double M_PI = 3.1415926535897932384626433832795; | |
19 | #endif | |
20 | ||
21 | const char CONVEX = 1; | |
22 | const char COMPLEX = 2; | |
23 | const char NONCONVEX = 3; | |
24 | ||
25 | std::mt19937 rng(39); | |
26 | ||
27 | class TPoint; | |
28 | void DrawLine(TPoint a, TPoint b, const RGBPIXEL& color); | |
29 | void DrawLine(int x0, int y0, int x1, int y1, const RGBPIXEL& color); | |
30 | bool Intersect(const TPoint& a, const TPoint& b, const TPoint& c, const TPoint& d); | |
31 | int SignArea(const TPoint& a, const TPoint& b, const TPoint& c); | |
32 | ||
33 | class TPoint { | |
34 | public: | |
35 | int x, y; | |
36 | TPoint(int x = 0, int y = 0) | |
37 | : x(x) | |
38 | , y(y) | |
39 | { | |
40 | } | |
41 | ||
42 | TPoint(const TPoint& a, const TPoint& b) | |
43 | : x(b.x - a.x) | |
44 | , y(b.y - a.y) | |
45 | { | |
46 | } | |
47 | ||
48 | double Length() { | |
49 | return hypot(x, y); | |
50 | } | |
51 | ||
52 | TPoint operator + (const TPoint& o) { | |
53 | return TPoint(x + o.x, y + o.y); | |
54 | } | |
55 | ||
56 | TPoint operator - (const TPoint& o) { | |
57 | return TPoint(x - o.x, y - o.y); | |
58 | } | |
59 | ||
60 | bool operator < (const TPoint& o) { | |
61 | return x < o.x || x == o.x && y < o.y; | |
62 | } | |
63 | ||
64 | bool operator == (const TPoint& o) { | |
65 | return x == o.x && y == o.y; | |
66 | } | |
67 | ||
68 | bool operator != (const TPoint& o) { | |
69 | return !(*this == o); | |
70 | } | |
71 | ||
72 | private: | |
73 | ||
74 | }; | |
75 | ||
76 | class TPoint3D { | |
77 | public: | |
78 | int x, y, z; | |
79 | TPoint3D(int x = 0, int y = 0, int z = 0) | |
80 | : x(x) | |
81 | , y(y) | |
82 | , z(z) | |
83 | { | |
84 | } | |
85 | ||
86 | TPoint3D(const TPoint3D& a, const TPoint3D& b) | |
87 | : x(b.x - a.x) | |
88 | , y(b.y - a.y) | |
89 | , z(b.z - a.z) | |
90 | { | |
91 | } | |
92 | ||
93 | double Length() { | |
94 | return std::sqrt(x * x + y * y + z * z); | |
95 | } | |
96 | ||
97 | TPoint3D operator + (const TPoint3D& o) { | |
98 | return TPoint3D(x + o.x, y + o.y, z + o.z); | |
99 | } | |
100 | ||
101 | TPoint3D operator - (const TPoint3D& o) { | |
102 | return TPoint3D(x - o.x, y - o.y, z - o.z); | |
103 | } | |
104 | ||
105 | bool operator < (const TPoint3D& o) { | |
106 | if (x != o.x) return x < o.x; | |
107 | if (y != o.y) return y < o.y; | |
108 | return z < o.z; | |
109 | } | |
110 | ||
111 | bool operator == (const TPoint3D& o) { | |
112 | return x == o.x && y == o.y && z == o.z; | |
113 | } | |
114 | ||
115 | bool operator != (const TPoint3D& o) { | |
116 | return !(*this == o); | |
117 | } | |
118 | }; | |
119 | ||
120 | class TPolygon { | |
121 | public: | |
122 | TPolygon(int n) | |
123 | : n(n) | |
124 | , p(std::vector<TPoint>(n)) | |
125 | { | |
126 | } | |
127 | ||
128 | void SetRandomPoint(int index, int w, int h) { | |
129 | if (index >= 0 && index < n) { | |
130 | p[index].x = rng() % w; | |
131 | p[index].y = rng() % h; | |
132 | } | |
133 | } | |
134 | ||
135 | void SetRandom(int w, int h) { | |
136 | for (int i = 0; i < n; i++) { | |
137 | SetRandomPoint(i, w, h); | |
138 | } | |
139 | } | |
140 | ||
141 | void Draw(const RGBPIXEL& color) { | |
142 | for (int i = 0; i < n; i++) { | |
143 | DrawLine(p[i].x, p[i].y, p[(i + 1) % n].x, p[(i + 1) % n].y, color); | |
144 | } | |
145 | } | |
146 | ||
147 | // should be with multithreading | |
148 | void Fill(TPoint minPoint, TPoint maxPoint, RGBPIXEL color, const std::function<bool(TPoint)>& f) { | |
149 | for (int x = minPoint.x; x <= maxPoint.x; x++) { | |
150 | for (int y = minPoint.y; y <= maxPoint.y; y++) { | |
151 | if (f({ x, y })) { | |
152 | gfSetPixel(x, y, color); | |
153 | } | |
154 | } | |
155 | } | |
156 | } | |
157 | ||
158 | int Size() const { | |
159 | return n; | |
160 | } | |
161 | ||
162 | TPoint& operator [] (int i) { | |
163 | i %= n; | |
164 | if (i < 0) i += n; | |
165 | return p[i]; | |
166 | }; | |
167 | ||
168 | TPoint* begin() { | |
169 | return &p[0]; | |
170 | } | |
171 | ||
172 | TPoint* end() { | |
173 | return std::next(&p.back()); | |
174 | } | |
175 | ||
176 | bool IsComplex() { | |
177 | n = p.size(); | |
178 | if (n <= 3) { | |
179 | return false; | |
180 | } | |
181 | for (int i = 0; i < n; i++) { | |
182 | for (int j = i + 2; j < n; j++) { | |
183 | if (j == n - 1 && i == 0) continue; | |
184 | if (Intersect(p[i], p[(i + 1) % n], p[j], p[(j + 1) % n])) { | |
185 | return true; | |
186 | } | |
187 | } | |
188 | } | |
189 | return false; | |
190 | } | |
191 | ||
192 | bool IsConvex() { | |
193 | n = p.size(); | |
194 | if (n <= 3) { | |
195 | return true; | |
196 | } | |
197 | if (IsComplex()) { | |
198 | return false; | |
199 | } | |
200 | int pos = 0; | |
201 | int neg = 0; | |
202 | for (int i = 0; i < n; i++) { | |
203 | const int s = SignArea(p[(i - 1 + n) % n], p[i], p[(i + 1) % n]); | |
204 | if (s > 0) { | |
205 | pos++; | |
206 | } | |
207 | if (s < 0) { | |
208 | neg++; | |
209 | } | |
210 | if (pos > 0 && neg > 0) { | |
211 | return false; | |
212 | } | |
213 | } | |
214 | if (pos > 0 && neg > 0) { | |
215 | return false; | |
216 | } | |
217 | return true; | |
218 | } | |
219 | ||
220 | char Classify() { | |
221 | if (IsConvex()) { | |
222 | return CONVEX; | |
223 | } | |
224 | else if (IsComplex()) { | |
225 | return COMPLEX; | |
226 | } | |
227 | else { | |
228 | return NONCONVEX; | |
229 | } | |
230 | } | |
231 | ||
232 | void MakeConvex() { | |
233 | sort(all(p)); | |
234 | auto cw = [&](const TPoint & a, const TPoint & b) { | |
235 | return a.x * b.y - a.y * b.x; | |
236 | }; | |
237 | auto norm = [&](const TPoint& a) { | |
238 | return 1ll * a.x * a.x + 1ll * a.y * a.y; | |
239 | }; | |
240 | p.erase(unique(all(p)), p.end()); | |
241 | sort(p.begin() + 1, p.end(), [&](TPoint& a, TPoint& b) { | |
242 | long long val = cw(a - p[0], b - p[0]); | |
243 | if (val != 0) return val < 0; | |
244 | return norm(a - p[0]) < norm(b - p[0]); | |
245 | }); | |
246 | const int n = p.size(); | |
247 | if (n <= 2) { | |
248 | this->n = n; | |
249 | return; | |
250 | } | |
251 | std::vector<TPoint> ans = { p[0], p[1] }; | |
252 | int sz = 2; | |
253 | for (int i = 2; i < n; i++) { | |
254 | while (sz >= 2 && cw(ans[sz - 1] - ans[sz - 2], p[i] - ans[sz - 1]) >= 0) { | |
255 | ans.pop_back(); | |
256 | sz--; | |
257 | } | |
258 | sz++; | |
259 | ans.push_back(p[i]); | |
260 | } | |
261 | while (sz >= 2 && cw(ans[sz - 1] - ans[sz - 2], ans[0] - ans[sz - 1]) >= 0) { | |
262 | ans.pop_back(); | |
263 | sz--; | |
264 | } | |
265 | p = ans; | |
266 | this->n = p.size(); | |
267 | } | |
268 | ||
269 | private: | |
270 | int n; | |
271 | std::vector<TPoint> p; | |
272 | }; | |
273 | ||
274 | void DrawLine(int x0, int y0, int x1, int y1, const RGBPIXEL& color) { | |
275 | const int deltaX = abs(x0 - x1); | |
276 | const int deltaY = abs(y0 - y1); | |
277 | const int signX = x0 < x1 ? 1 : -1; | |
278 | const int signY = y0 < y1 ? 1 : -1; | |
279 | int d = deltaX - deltaY; | |
280 | gfSetPixel(x1, y1, color); | |
281 | while (x0 != x1 || y0 != y1) { | |
282 | gfSetPixel(x0, y0, color); | |
283 | const int d2 = d << 1; | |
284 | if (d2 > -deltaY) { // d > -dy / 2 | |
285 | d -= deltaY; | |
286 | x0 += signX; | |
287 | } | |
288 | if (d2 < deltaX) { | |
289 | d += deltaX; | |
290 | y0 += signY; | |
291 | } | |
292 | } | |
293 | } | |
294 | ||
295 | void DrawLine(TPoint a, TPoint b, const RGBPIXEL& color) { | |
296 | DrawLine(a.x, a.y, b.x, b.y, color); | |
297 | } | |
298 | ||
299 | inline bool cw(const TPoint& a, const TPoint& b, const TPoint& c) { // clockwise | |
300 | return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0; | |
301 | } | |
302 | ||
303 | int sign(long long a) { | |
304 | if (a > 0) return 1; | |
305 | if (a < 0) return -1; | |
306 | return 0; | |
307 | } | |
308 | ||
309 | inline int SignArea(const TPoint& a, const TPoint& b, const TPoint& c) { | |
310 | return sign(static_cast<long long>(b.x - a.x) * (c.y - a.y) - static_cast<long long>(b.y - a.y) * (c.x - a.x)); | |
311 | } | |
312 | ||
313 | inline int Area(const TPoint& a, const TPoint& b) { | |
314 | return a.x * b.y - a.y * b.x; | |
315 | } | |
316 | ||
317 | inline bool Intersect_1(int a, int b, int c, int d) { | |
318 | if (a > b) std::swap(a, b); | |
319 | if (c > d) std::swap(c, d); | |
320 | return max(a, c) <= min(b, d); | |
321 | } | |
322 | ||
323 | bool Intersect(const TPoint& a, const TPoint& b, const TPoint& c, const TPoint& d) { | |
324 | return Intersect_1(a.x, b.x, c.x, d.x) | |
325 | && Intersect_1(a.y, b.y, c.y, d.y) | |
326 | && SignArea(a, b, c) * SignArea(a, b, d) <= 0 | |
327 | && SignArea(c, d, a) * SignArea(c, d, b) <= 0; | |
328 | } | |
329 | ||
330 | inline RGBPIXEL RandColor() { | |
331 | return RGBPIXEL(rand() % 256, rand() % 256, rand() % 256); | |
332 | } | |
333 | ||
334 | bool PointInPolygonWithEvenOddRule(TPolygon& p, const TPoint& a) { | |
335 | bool counter = 0; | |
336 | const int inf = 2000; | |
337 | TPoint b = { a.x, a.y - inf }; | |
338 | bool pre = false; | |
339 | bool cur = false; | |
340 | const int n = p.Size(); | |
341 | for (int i = 0; i < n; i++) { | |
342 | cur = Intersect(p[i], p[(i + 1) % n], a, b); | |
343 | if (cur && pre && p[i].x == a.x) { | |
344 | if ((p[(i - 1 + n) % n].x > a.x) ^ (p[(i + 1) % n].x > a.x)) { | |
345 | continue; | |
346 | } | |
347 | } | |
348 | counter ^= cur; | |
349 | pre = cur; | |
350 | } | |
351 | return counter; | |
352 | } | |
353 | ||
354 | bool PointInPolygonWithNonZeroWindingRule(TPolygon& p, const TPoint& a) { | |
355 | int counter = 0; | |
356 | const int inf = 9000; | |
357 | TPoint b = { a.x, a.y + inf }; | |
358 | bool pref = false; | |
359 | bool cur = false; | |
360 | const int n = p.Size(); | |
361 | for (int i = 0; i < n; i++) { | |
362 | if (cur = Intersect(p[i], p[(i + 1) % n], a, b)) { | |
363 | if (cur && pref && p[i].x == a.x) { | |
364 | if ((p[(i - 1 + n) % n].x - a.x) * (p[(i + 1) % n].x - a.x) < 0) { | |
365 | continue; | |
366 | } | |
367 | } | |
368 | counter += SignArea(p[i], p[(i + 1) % n], a); | |
369 | } | |
370 | pref = cur; | |
371 | } | |
372 | return counter; | |
373 | } | |
374 | ||
375 | const TCHAR* GetTextForDraw(const std::string& s) { | |
376 | char* answer = new char[s.size() + 1]; | |
377 | for (int i = 0; i < s.size(); i++) { | |
378 | answer[i] = s[i]; | |
379 | } | |
380 | answer[s.size()] = '\0'; | |
381 | return answer; | |
382 | } | |
383 | ||
384 | template<typename T> | |
385 | const TCHAR* GetTextForDraw(const T& value) { | |
386 | return GetTextForDraw(std::to_string(value)); | |
387 | } | |
388 | ||
389 | std::pair<TPoint, TPoint> MinMaxBorders(TPolygon& polygon) { | |
390 | const int inf = 1 << 30; | |
391 | TPoint minPoint = { inf, inf }; | |
392 | TPoint maxPoint = { -inf, -inf }; | |
393 | for (const auto& p : polygon) { | |
394 | minPoint.x = min(minPoint.x, p.x); | |
395 | minPoint.y = min(minPoint.y, p.y); | |
396 | maxPoint.x = max(maxPoint.x, p.x); | |
397 | maxPoint.y = max(maxPoint.y, p.y); | |
398 | } | |
399 | return { minPoint, maxPoint }; | |
400 | } | |
401 | ||
402 | long long DistQrt(const TPoint& a, const TPoint& b) { | |
403 | return static_cast<long long>(a.x - b.x) * (a.x - b.x) + static_cast<long long>(a.y - b.y) * (a.y - b.y); | |
404 | } | |
405 | ||
406 | double C(int n, int m) { | |
407 | double answer = 1; | |
408 | for (int i = 1; i <= n; i++) { | |
409 | answer *= i; | |
410 | } | |
411 | for (int i = 1; i <= m; i++) { | |
412 | answer /= i; | |
413 | } | |
414 | for (int i = 1; i <= n - m; i++) { | |
415 | answer /= i; | |
416 | } | |
417 | return answer; | |
418 | } | |
419 | ||
420 | void DrawBezierLine(std::vector<TPoint>& arr, const RGBPIXEL& color) { | |
421 | const int n = arr.size(); | |
422 | if (n <= 2) { | |
423 | DrawLine(arr[0], arr.back(), color); | |
424 | return; | |
425 | } | |
426 | auto dist = [&](const TPoint& a) { | |
427 | return abs(a.x) + abs(a.y); | |
428 | }; | |
429 | long long D = 0; | |
430 | for (int i = 2; i < n; i++) { | |
431 | D = max(D, dist(arr[i - 2] - arr[i - 1] - arr[i - 1] + arr[i])); | |
432 | } | |
433 | double N = 1 + sqrt(n * D); | |
434 | double dt = 1 / N; | |
435 | auto R = [&](double t) { | |
436 | double x = 0; | |
437 | double y = 0; | |
438 | for (int i = 0; i < n; i++) { | |
439 | double p = C(n - 1, i) * pow(t, i) * pow(1 - t, n - 1 - i); | |
440 | x += arr[i].x * p; | |
441 | y += arr[i].y * p; | |
442 | } | |
443 | return TPoint(x + 0.5, y + 0.5); | |
444 | }; | |
445 | std::vector<TPoint> a; | |
446 | int q = 1 / dt + 1; | |
447 | for (int i = 0; i < q; i++) { | |
448 | a.push_back(R(i * 1.0 / q)); | |
449 | } | |
450 | a.push_back(arr.back()); | |
451 | for (int i = 1; i < a.size(); i++) { | |
452 | DrawLine(a[i - 1], a[i], color); | |
453 | } | |
454 | } | |
455 | ||
456 | ||
457 | std::vector<TPoint> GetBezierLine(std::vector<TPoint>& arr, const RGBPIXEL& color) { | |
458 | const int n = arr.size(); | |
459 | if (n <= 2) { | |
460 | DrawLine(arr[0], arr.back(), color); | |
461 | return arr; | |
462 | } | |
463 | auto dist = [&](const TPoint& a) { | |
464 | return abs(a.x) + abs(a.y); | |
465 | }; | |
466 | long long D = 0; | |
467 | for (int i = 2; i < n; i++) { | |
468 | D = max(D, dist(arr[i - 2] - arr[i - 1] - arr[i - 1] + arr[i])); | |
469 | } | |
470 | double N = 1 + sqrt(n * D); | |
471 | double dt = 1 / N; | |
472 | auto R = [&](double t) { | |
473 | double x = 0; | |
474 | double y = 0; | |
475 | for (int i = 0; i < n; i++) { | |
476 | double p = C(n - 1, i) * pow(t, i) * pow(1 - t, n - 1 - i); | |
477 | x += arr[i].x * p; | |
478 | y += arr[i].y * p; | |
479 | } | |
480 | return TPoint(x + 0.5, y + 0.5); | |
481 | }; | |
482 | std::vector<TPoint> a; | |
483 | int q = 1 / dt + 1; | |
484 | for (int i = 0; i < q; i++) { | |
485 | a.push_back(R(i * 1.0 / q)); | |
486 | } | |
487 | a.push_back(arr.back()); | |
488 | return a; | |
489 | } | |
490 | ||
491 | /* | |
492 | de Kasteljo | |
493 | */ | |
494 | void DrawBezierLine2(std::vector<TPoint>& arr, const RGBPIXEL& color) { | |
495 | const int n = arr.size(); | |
496 | if (n <= 2) { | |
497 | DrawLine(arr[0], arr.back(), color); | |
498 | return; | |
499 | } | |
500 | const int bits = 7; | |
501 | const int size = 1 << bits; | |
502 | const int halfsize = 1 << (bits - 1); | |
503 | std::function<TPoint(const TPoint&, const TPoint&, int)> get = [&](const TPoint& a, const TPoint& b, int pr) { | |
504 | return TPoint(a.x + (pr * (b.x - a.x) + halfsize >> bits), a.y + (pr * (b.y - a.y) + halfsize >> bits)); | |
505 | }; | |
506 | ||
507 | std::function<TPoint(std::vector<TPoint>, int)> findPoint = [&](std::vector<TPoint> a, int pr) { | |
508 | if (a.size() <= 2) { | |
509 | return get(a[0], a.back(), pr); | |
510 | } | |
511 | else { | |
512 | for (int i = 0; i + 1 < a.size(); i++) { | |
513 | a[i] = get(a[i], a[i + 1], pr); | |
514 | } | |
515 | a.pop_back(); | |
516 | return findPoint(a, pr); | |
517 | } | |
518 | }; | |
519 | ||
520 | std::vector<TPoint> result; | |
521 | ||
522 | for (int t = 0; t <= size; t++) { | |
523 | result.push_back(findPoint(arr, t)); | |
524 | } | |
525 | for (int i = 0; i + 1 < result.size(); i++) { | |
526 | DrawLine(result[i], result[i + 1], color); | |
527 | } | |
528 | } | |
529 | ||
530 | int ClipLine(TPoint& a, TPoint& b, TPolygon& arr) { | |
531 | ||
532 | double t0 = 0, t1 = 1, t; | |
533 | TPoint s = TPoint(b.x - a.x, b.y - a.y); // vector colinear with current | |
534 | long long nx, ny, num, denom, x1, y1, x2, y2; | |
535 | const int n = arr.Size(); | |
536 | if (n <= 2 || !arr.IsConvex()) { | |
537 | return 1; | |
538 | } | |
539 | bool isCw = false; | |
540 | for (int i = 0; i + 2 < n; i++) { | |
541 | isCw |= SignArea(arr[i + 0], arr[i + 1], arr[i + 2]) < 0; // polygon contains edges in clock wise order | |
542 | } | |
543 | ||
544 | for (int i = (isCw ? 0 : n - 1); (isCw ? i < n : i >= 0); (isCw ? i++ : i--)) { | |
545 | nx = arr[i + (isCw ? 1 : -1)].y - arr[i].y; | |
546 | ny = arr[i].x - arr[i + (isCw ? 1 : -1)].x; | |
547 | denom = nx * s.x + ny * s.y; | |
548 | num = nx * (a.x - arr[i].x) + ny * (a.y - arr[i].y); | |
549 | if (abs(denom) > 1e-9) { | |
550 | t = -num * 1.0 / denom; | |
551 | if (denom > 0) { | |
552 | if (t > t0) { | |
553 | t0 = t; | |
554 | } | |
555 | } | |
556 | else { | |
557 | if (t < t1) { | |
558 | t1 = t; | |
559 | } | |
560 | } | |
561 | } | |
562 | else { | |
563 | if (num < 0) { | |
564 | return 1; | |
565 | } | |
566 | } | |
567 | } | |
568 | if (t0 <= t1) { | |
569 | x1 = a.x + t0 * (b.x - a.x); | |
570 | y1 = a.y + t0 * (b.y - a.y); | |
571 | x2 = a.x + t1 * (b.x - a.x); | |
572 | y2 = a.y + t1 * (b.y - a.y); | |
573 | a = TPoint(x1 + 0.5, y1 + 0.5); // update values | |
574 | b = TPoint(x2 + 0.5, y2 + 0.5); | |
575 | return 0; | |
576 | } | |
577 | return 1; // no visible part | |
578 | } | |
579 | ||
580 | bool PointIntoTriangle(TPoint a, TPoint b, TPoint c, TPoint x) { | |
581 | return SignArea(a, b, x) * SignArea(a, x, c) <= 0 && SignArea(b, c, x) * SignArea(b, x, a) <= 0 && SignArea(c, a, x) * SignArea(c, x, b) <= 0; | |
582 | } | |
583 | ||
584 | bool PointIntoConvexPolygon(TPolygon p, TPoint x) { | |
585 | bool ans = false; | |
586 | const int n = p.Size(); | |
587 | if (n <= 2) return false; | |
588 | for (int i = 2; !ans && i < n; i++) { | |
589 | ans |= PointIntoTriangle(p[i - 2], p[i - 1], p[0], x); | |
590 | } | |
591 | return ans; | |
592 | } | |
593 | ||
594 | int Y = 15; | |
595 | int Dy = 20; | |
596 | ||
597 | std::vector<TPolygon> BuildProjectionOfParallelepiped(const std::vector<std::vector<TPoint3D>>& p) { | |
598 | const int n = p.size(); | |
599 | int ITR = 0; | |
600 | ||
601 | auto isInvisible = [&](TPoint3D& pt, int index) { | |
602 | for (int i = 0; i < n; i++) { | |
603 | if (i == index) continue; | |
604 | TPolygon cur(p[i].size()); | |
605 | for (int j = 0; j < p[i].size(); j++) { | |
606 | cur[j] = TPoint(p[i][j].x, p[i][j].y); | |
607 | } | |
608 | if (!PointIntoConvexPolygon(cur, TPoint(pt.x, pt.y))) continue; | |
609 | TPoint X = TPoint(pt.x, pt.y) - cur[0]; | |
610 | TPoint A = cur[1] - cur[0]; | |
611 | TPoint B = cur[2] - cur[0]; | |
612 | int dZ1 = p[i][1].z - p[i][0].z; | |
613 | int dZ2 = p[i][2].z - p[i][0].z; | |
614 | int dZ = pt.z - p[i][0].z; | |
615 | double t2 = static_cast<double>(X.x * A.y - A.x * X.y) / (A.y * B.x - A.x * B.y); | |
616 | double t1 = static_cast<double>(X.x - B.x * t2) / A.x; | |
617 | double curX = t1 * A.x + t2 * B.x; | |
618 | double curY = t1 * A.y + t2 * B.y; | |
619 | double curZ = dZ1 * t1 + dZ2 * t2 + p[i][0].z; | |
620 | auto myCeil = [&](double x) { | |
621 | if (x < 0) return static_cast<int>(x - 0.5); | |
622 | return static_cast<int>(x + 0.5); | |
623 | }; | |
624 | curX = myCeil(curX); | |
625 | curY = myCeil(curY); | |
626 | curZ = myCeil(curZ); | |
627 | ||
628 | if (curZ < pt.z) { | |
629 | return true; | |
630 | } | |
631 | } | |
632 | return false; | |
633 | }; | |
634 | std::vector<TPolygon> res; | |
635 | for (int i = 0; i < n; i++) { | |
636 | TPoint3D mnPt = p[i][0]; | |
637 | for (auto& pt : p[i]) { | |
638 | if (pt.z < mnPt.z) { | |
639 | mnPt = pt; | |
640 | } | |
641 | } | |
642 | if (isInvisible(mnPt, i)) { | |
643 | res.emplace_back(p[i].size()); | |
644 | for (int j = 0; j < p[i].size(); j++) { | |
645 | res.back()[j] = TPoint(p[i][j].x, p[i][j].y); | |
646 | } | |
647 | } | |
648 | } | |
649 | return res; | |
650 | } | |
651 | ||
652 | ||
653 | std::vector<bool> BuildProjectionOfParallelepiped2(const std::vector<std::vector<TPoint3D>>& p) { | |
654 | std::vector<bool> result(p.size(), true); | |
655 | int itr = 0; | |
656 | for (const auto& v : p) { | |
657 | const int n = v.size(); | |
658 | bool isInvisible = false; | |
659 | for (int i = 0; !isInvisible && i < n; i++) { | |
660 | TPoint a{ v[i].x, v[i].y }; | |
661 | TPoint b{ v[(i + 1) % n].x, v[(i + 1) % n].y }; | |
662 | TPoint c{ v[(i + 2) % n].x, v[(i + 2) % n].y }; | |
663 | isInvisible = Area(b - a, c - b) > 0; | |
664 | } | |
665 | result[itr++] = !isInvisible; | |
666 | } | |
667 | return result; | |
668 | } | |
669 | ||
670 | ||
671 | std::vector<bool> BuildPointProjection(std::vector<std::vector<TPoint3D>>& p, int k) { | |
672 | for (auto& v : p) { | |
673 | for (auto& pt : v) { | |
674 | ||
675 | } | |
676 | } | |
677 | return BuildProjectionOfParallelepiped2(p); | |
678 | } | |
679 | ||
680 | std::vector<std::vector<TPoint3D>> p; | |
681 | double phi = M_PI / 20; | |
682 | double x = 6; | |
683 | double y = 1; | |
684 | double z = 9; | |
685 | double angle = 0; | |
686 | ||
687 | std::vector<RGBPIXEL> colors = { | |
688 | RGBPIXEL::White(), | |
689 | RGBPIXEL::Red(), | |
690 | RGBPIXEL::Green(), | |
691 | RGBPIXEL::Blue(), | |
692 | RGBPIXEL::DkMagenta(), | |
693 | RGBPIXEL::Yellow(), | |
694 | }; | |
695 | ||
696 | const int WINDOW_H = 900; | |
697 | const int WINDOW_W = 1.5 * 900; | |
698 | ||
699 | ||
700 | bool gfInitScene() { | |
701 | try { | |
702 | const int WINDOW_SIZE = 900; | |
703 | gfSetWindowSize(WINDOW_W, WINDOW_H); | |
704 | const int A = 180; | |
705 | const int B = 100; | |
706 | const int C = 150; | |
707 | int Norm = x * x + y * y + z * z; | |
708 | x /= sqrt(Norm); | |
709 | y /= sqrt(Norm); | |
710 | z /= sqrt(Norm); | |
711 | p = { | |
712 | { { 0, 0, 0 },{ 0, B, 0 },{ 0, B, C },{ 0, 0, C } }, | |
713 | { { A, 0, C },{ A, B, C },{ A, B, 0 },{ A, 0, 0 } }, | |
714 | ||
715 | { { 0, 0, 0 },{ 0, 0, C },{ A, 0, C },{ A, 0, 0 } }, | |
716 | { { A, B, 0 },{ A, B, C },{ 0, B, C },{ 0, B, 0 } }, | |
717 | ||
718 | { { A, 0, 0 },{ A, B, 0 },{ 0, B, 0 },{ 0, 0, 0 } }, | |
719 | { { 0, 0, C },{ 0, B, C },{ A, B, C },{ A, 0, C } } | |
720 | }; | |
721 | ||
722 | for (auto& v : p) { | |
723 | for (auto& pt : v) { | |
724 | pt.x += 300; | |
725 | pt.y += 300; | |
726 | } | |
727 | } | |
728 | double xyAngle = 45.0 / 180.0 * M_PI; | |
729 | double xzAngle = 45.0 / 180.0 * M_PI; | |
730 | double yzAngle = 0 / 180.0 * M_PI; | |
731 | double cosxy = cos(xyAngle); | |
732 | double cosxz = cos(xzAngle); | |
733 | double cosyz = cos(yzAngle); | |
734 | ||
735 | double sinxy = sin(xyAngle); | |
736 | double sinxz = sin(xzAngle); | |
737 | double sinyz = sin(yzAngle); | |
738 | ||
739 | ||
740 | // xy | |
741 | for (auto& v : p) { | |
742 | for (auto& pt : v) { | |
743 | TPoint3D nxt; | |
744 | nxt.x = cosxy * pt.x - sinxy * pt.y; | |
745 | nxt.y = sinxy * pt.x + cosxy * pt.y; | |
746 | nxt.z = pt.z; | |
747 | pt = nxt; | |
748 | } | |
749 | } | |
750 | ||
751 | // xz | |
752 | for (auto& v : p) { | |
753 | for (auto& pt : v) { | |
754 | TPoint3D nxt; | |
755 | nxt.x = cosxz * pt.x - sinxz * pt.z; | |
756 | nxt.z = sinxz * pt.x + cosxz * pt.z; | |
757 | nxt.y = pt.y; | |
758 | pt = nxt; | |
759 | } | |
760 | } | |
761 | ||
762 | // yz | |
763 | for (auto& v : p) { | |
764 | for (auto& pt : v) { | |
765 | TPoint3D nxt; | |
766 | nxt.y = cosyz * pt.y - sinyz * pt.z; | |
767 | nxt.z = sinyz * pt.y + cosyz * pt.z; | |
768 | nxt.x = pt.x; | |
769 | pt = nxt; | |
770 | } | |
771 | } | |
772 | ||
773 | int mnX = 1e9; | |
774 | int mnY = 1e9; | |
775 | int mnZ = 1e9; | |
776 | for (auto& v : p) { | |
777 | for (auto& pt : v) { | |
778 | mnX = min(mnX, pt.x); | |
779 | mnY = min(mnY, pt.y); | |
780 | mnZ = min(mnZ, pt.z); | |
781 | } | |
782 | } | |
783 | ||
784 | for (auto& v : p) { | |
785 | for (auto& pt : v) { | |
786 | pt.x -= mnX - 100; | |
787 | pt.y -= mnY - 100; | |
788 | pt.z -= mnZ - 100; | |
789 | } | |
790 | } | |
791 | ||
792 | for (auto v : p) { | |
793 | int dx = 0; | |
794 | for (int i = 0; i < v.size(); i++) { | |
795 | DrawLine(TPoint(v[i].x + dx, v[i].y), TPoint(v[(i + 1) % v.size()].x + dx, v[(i + 1) % v.size()].y), RGBPIXEL::Green()); | |
796 | } | |
797 | } | |
798 | ||
799 | auto cur = BuildProjectionOfParallelepiped2(p); | |
800 | for (int i = 0; i < cur.size(); i++) { | |
801 | if (cur[i]) { | |
802 | TPolygon x(p[i].size()); | |
803 | for (int j = 0; j < p[i].size(); j++) { | |
804 | x[j] = TPoint(p[i][j].x, p[i][j].y); | |
805 | } | |
806 | x.Draw(RGBPIXEL::White()); | |
807 | } | |
808 | } | |
809 | const int DX = 500; | |
810 | auto myWay = BuildProjectionOfParallelepiped(p); | |
811 | for (auto& v : myWay) { | |
812 | for (auto& pt : v) { | |
813 | pt.x += DX; | |
814 | } | |
815 | v.Draw(RGBPIXEL::Red()); | |
816 | } | |
817 | TPoint3D mxPt = p[0][0]; | |
818 | for (auto& v : p) { | |
819 | for (auto& pt : v) { | |
820 | if (pt.z > mxPt.z) { | |
821 | mxPt = pt; | |
822 | } | |
823 | } | |
824 | } | |
825 | gfDrawRectangle(mxPt.x - 5, mxPt.y - 5, mxPt.x + 5, mxPt.y + 5, RGBPIXEL::Red()); | |
826 | gfDrawRectangle(mxPt.x - 5 + DX, mxPt.y - 5, mxPt.x + 5 + DX, mxPt.y + 5, RGBPIXEL::Red()); | |
827 | } | |
828 | catch (...) { | |
829 | return false; | |
830 | } | |
831 | return true; | |
832 | } | |
833 | ||
834 | int dx = 10; | |
835 | int dy = 15; | |
836 | int sx = 0; | |
837 | int sy = 0; | |
838 | int ITR = 0; | |
839 | ||
840 | void gfDrawScene() | |
841 | { | |
842 | gfClearScreen(RGBPIXEL::Black()); | |
843 | angle += phi; | |
844 | double s = sin(angle); | |
845 | double c = cos(angle); | |
846 | ||
847 | ||
848 | const int Y1 = 50; | |
849 | const int X1 = 100; | |
850 | ITR++; | |
851 | ITR %= 500; | |
852 | std::string str1 = "спокойствие..."; | |
853 | std::string str2 = "блаженство..."; | |
854 | if (ITR < 250) { | |
855 | ||
856 | gfDrawText(X1, Y1, GetTextForDraw(str1), RGBPIXEL::White()); | |
857 | } | |
858 | else { | |
859 | gfDrawText(X1 + 50, Y1 + 50, GetTextForDraw(str2), RGBPIXEL::White()); | |
860 | } | |
861 | ||
862 | std::vector<std::vector<TPoint3D>> cur; | |
863 | for (auto& v : p) { | |
864 | cur.emplace_back(); | |
865 | for (auto& pt : v) { | |
866 | TPoint3D nxt; | |
867 | ||
868 | double cx = (c + (1 - c) * x * x) * pt.x + ((1 - c) * x * y - s * z) * pt.y + ((1 - c) * x * z + s * y) * pt.z; | |
869 | double cy = ((1 - c) * y * x + s * z) * pt.x + (c + (1 - c) * y * y) * pt.y + ((1 - c) * y * z - s * x) * pt.z; | |
870 | double cz = ((1 - c) * z * x - s * y) * pt.x + ((1 - c) * z * y + s * x) * pt.y + (c + (1 - c) * z * z) * pt.z; | |
871 | ||
872 | - | int k = 100; //with point projection |
872 | + | int k = 0; |
873 | - | double H = cz / k + 1; |
873 | + | k = 125; |
874 | - | nxt.x = cx / H; |
874 | + | if (k > 0) { |
875 | - | nxt.y = cy / H; |
875 | + | double H = cz / k + 1; |
876 | - | nxt.z = k / H; |
876 | + | nxt.x = cx / H; |
877 | nxt.y = cy / H; | |
878 | - | /*nxt.x = cx; //without point projection |
878 | + | nxt.z = k / H; |
879 | - | nxt.y = cy; |
879 | + | } else { |
880 | - | nxt.z = cz; */ |
880 | + | nxt.x = cx; |
881 | nxt.y = cy; | |
882 | nxt.z = cz; | |
883 | } | |
884 | ||
885 | cur.back().push_back(nxt); | |
886 | } | |
887 | } | |
888 | auto kek = BuildProjectionOfParallelepiped2(cur); | |
889 | for (int i = 0; i < kek.size(); i++) { | |
890 | if (kek[i]) { | |
891 | TPolygon curp(cur[i].size()); | |
892 | for (int j = 0; j < curp.Size(); j++) { | |
893 | curp[j] = TPoint(cur[i][j].x + 500, cur[i][j].y + 500); | |
894 | } | |
895 | curp.Draw(RGBPIXEL::White()); | |
896 | } | |
897 | } | |
898 | // | |
899 | } | |
900 | ||
901 | void gfCleanupScene() { | |
902 | } | |
903 | ||
904 | void gfOnLMouseClick(int x, int y) { | |
905 | } | |
906 | ||
907 | void gfOnRMouseClick(int x, int y) { | |
908 | } | |
909 | ||
910 | void gfOnKeyDown(UINT key) { | |
911 | } | |
912 | ||
913 | void gfOnKeyUp(UINT key) | |
914 | { | |
915 | } |