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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
|
// file: kpoint2d.h
// update: 11/03/02
#ifndef _KPOINT2D_H
#define _KPOINT2D_H
#include <cassert>
#include <cstdlib>
#include <iostream>
#include "bigrational.h"
#include "kratpoly.h"
#include "root1.h"
#include "kpoint1d.h"
#include "kboxco2.h"
using namespace std;
class K_BOXCO2;
class K_PARTITION;
class K_SURF;
class K_PATCH;
class K_POINT2D
{
friend class PTS_CACHE;
friend class K_SEGMENT;
friend class K_CURVE;
friend class PT_SURF_ASSOC;
friend class K_PATCH;
friend class K_PARTITION;
friend class K_SOLID;
mutable unsigned int type; // type == 1 if ROOT1 in s and t
// 2 if ROOT1 in s and bigrational in t
// 3 if bigrational in s and ROOT1 in t
// 4 if bigrational in s and t
mutable ROOT1* PtRs; // the interval for the s-coordinate of *this,
// 0 if type == 3 or 4
mutable ROOT1* PtRt; // the interval for the t-coordinate of *this,
// 0 if type == 2 or 4
mutable bigrational PtBs; // the point for the s-coordinate of *this,
// undefined if type == 1 or 2
mutable bigrational PtBt; // the point for the t-coordinate,
// undefined if type == 1 or 3.
K_RATPOLY* poly1; // polynomials
K_RATPOLY* poly2; // that intersect with each other at *this
mutable K_POINT2D* prev; // the pointers to the neighbors
mutable K_POINT2D* next; // in the linked list of equivalent pts
K_POINT2D* pt_in_other_dom; // the pointer to
// the same pt in the other domain
unsigned long ref_count; // reference counter
// constructors, assignment and destructor
// K_POINT2D(const bigrational& b_s, const K_POINT1D& x_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 3 or 4 instance from
// bigrational b_s, K_POINT1D x_t and K_RATPOLY P1 and P2.
// P1 must intersect with P2 at (b_s, x_t).
K_POINT2D(const bigrational&, const K_POINT1D&,
const K_RATPOLY&, const K_RATPOLY&);
// K_POINT2D(const K_POINT1D& x_s, const bigrational& b_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 2 or 4 instance from
// K_POINT1D x_s, bigrational b_t and K_RATPOLY P1 and P2.
// P1 must intersect with P2 at (x_s, b_t).
K_POINT2D(const K_POINT1D&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&);
// K_POINT2D(const K_POINT1D& x_s, const K_POINT1D& x_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 1 or 2 or 3 or 4 instance from
// K_POINT1D x_s and x_t and K_RATPOLY P1 and P2.
// P1 must intersect with P2 at (x_s, x_t).
K_POINT2D(const K_POINT1D&, const K_POINT1D&,
const K_RATPOLY&, const K_RATPOLY&);
// stream
ostream& output(ostream&) const;
// primitive
// int cut_s(const bigrational& b_s) const
// cut *this by the line s = b_s, i.e.,
// refine the box for *this
// by setting get_low_s() or get_high_s() to be b_s.
int cut_s(const bigrational&) const;
// int cut_t(const bigrational& b_t) const
// cut *this by the line t = b_t, i.e.,
// refine the box for *this
// by setting get_low_t() or get_high_t() to be b_t.
int cut_t(const bigrational&) const;
// int halve_s() const
// cut *this by the line s = half that halves the box for *this, i.e.,
// refine the box for *this
// by setting get_low_s() or get_high_s() to be half.
int halve_s() const;
// int halve_t() const
// cut *this by the line t = half that halves the box for *this, i.e.,
// refine the box for *this
// by setting get_low_t() or get_high_t() to be half.
int halve_t() const;
// int reduce_s(const unsigned long num_bits) const
// reduce *this s.t.
// [get_low_s(), get_high_s()] will contain all the numbers
// approximated by PtRs->float_est to num_bits precision.
// return 1 if some reduction occurs and
// 0 otherwise.
int reduce_s(const unsigned long) const;
// int reduce_t(const unsigned long num_bits) const
// reduce *this s.t.
// [get_low_t(), get_high_t()] will contain all the numbers
// approximated by PtRt->float_est to num_bits precision.
// return 1 if some reduction occurs and
// 0 otherwise.
int reduce_t(const unsigned long) const;
// int reduce(const unsigned long num_bits_s,
// const unsigned long num_bits_t) const
// reduce *this s.t.
// [get_low_s(), get_high_s()] will contain all the numbers
// approximated by PtRs->float_est to num_bits_s precision and
// [get_low_t(), get_high_t()] will contain all the numbers
// approximated by PtRt->float_est to num_bits_t precision.
// return 1 if some reduction occurs and
// 0 otherwise.
int reduce(const unsigned long, const unsigned long) const;
// int contract_s(const bigrational& tol) const
// contract *this s.t.
// [get_low_s(), get_high_s()] will be no larger than tol.
int contract_s(const bigrational&) const;
// int contract_t(const bigrational& tol) const
// contract *this s.t.
// [get_low_t(), get_high_t()] will be no larger than tol.
int contract_t(const bigrational&) const;
// int contract(const bigrational& tol_s, const bigrational& tol_t) const
// contract *this s.t.
// [get_low_s(), get_high_s()] will be no larger than tol_s and
// [get_low_t(), get_high_t()] will be no larger than tol_t.
int contract(const bigrational&, const bigrational&) const;
// int shrink(const bigrational& fac_s, const bigrational& fac_t) const
// shrink *this s.t.
// [get_low_s(), get_high_s()] will become smaller by fac_s and
// [get_low_t(), get_high_t()] will become smaller by fac_t.
int shrink(const bigrational&, const bigrational&) const;
// int K_POINT2D :: separate(const K_POINT2D& x) const
// separate *this and x s.t. they will not overlap.
// POSSIBLY DOES NOT TERMINATE.
int separate(const K_POINT2D&) const;
// K_BOXCO2 bbox() const
// return a bounding box for *this.
K_BOXCO2 bbox() const;
public:
// constructors, assignment and destructor
K_POINT2D();
// K_POINT2D(const bigrational& b_s, const bigrational& b_t)
// construct a type 4 instance from bigrational b_s and b_t.
K_POINT2D(const bigrational&, const bigrational&);
// K_POINT2D(const ROOT1& r_s, const ROOT1& r_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 2 instance from
// ROOT1 r_s and r_t and K_RATPOLY P1 and P2.
// r_s.num_roots and r_t.num_roots must have been 1 and
// P1 must intersect with P2 at (r_s, r_t).
K_POINT2D(const ROOT1&, const ROOT1&,
const K_RATPOLY&, const K_RATPOLY&);
// K_POINT2D(const ROOT1& r_s, const bigrational& b_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 2 instance from
// bigrational b_s, ROOT1 r_t and K_RATPOLY P1 and P2.
// r_s.num_roots must have been 1 and
// P1 must intersect with P2 at (r_s, b_t).
K_POINT2D(const ROOT1&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&);
// K_POINT2D(const bigrational& b_s, const ROOT1& r_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 3 instance from
// bigrational b_s, ROOT1 r_t and K_RATPOLY P1 and P2.
// r_t.num_roots must have been 1 and
// P1 must intersect with P2 at (b_s, r_t).
K_POINT2D(const bigrational&, const ROOT1&,
const K_RATPOLY&, const K_RATPOLY&);
// K_POINT2D(const bigrational& b_s, const bigrational& b_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2)
// construct a type 4 instance from
// bigrational b_s and b_t and K_RATPOLY P1 and P2.
// P1 must intersect with P2 at (b_s, b_t).
K_POINT2D(const bigrational&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&);
K_POINT2D(const K_POINT2D&);
K_POINT2D& operator =(const K_POINT2D&);
~K_POINT2D();
// stream
friend ostream& operator <<(ostream&, const K_POINT2D&);
// primitive
bigrational get_low_s() const;
bigrational get_high_s() const;
bigrational get_low_t() const;
bigrational get_high_t() const;
bigrational_vector get_low() const;
bigrational_vector get_high() const;
// comparison
// int compare_s(const K_POINT2D& x) const
// return 1 if *this > x,
// 0 if *this == x, and
// - 1 if *this < x in the s-coordinate.
int compare_s(const K_POINT2D&) const;
// int compare_t(const K_POINT2D& x) const
// return 1 if *this > x,
// 0 if *this == x, and
// - 1 if *this < x in the t-coordinate.
int compare_t(const K_POINT2D&) const;
// int compare(const K_POINT2D& x, const unsigned long i) const
// return 1 if *this > x,
// 0 if *this == x, and
// - 1 if *this < x in the i-th coordinate.
// int compare(const K_POINT2D&, const unsigned long) const;
//
// // int compare_s(const bigrational& b_s) const
// // return 1 if *this > b_s,
// // 0 if *this == b_s, and
// // - 1 if *this < b_s in the s-coordinate.
int compare_s(const bigrational&) const;
// int compare_t(const bigrational& b_t) const
// return 1 if *this > b_t,
// 0 if *this == b_t, and
// - 1 if *this < b_t in the t-coordinate.
int compare_t(const bigrational&) const;
// // int compare(const bigrational& b, const unsigned long i) const
// // return 1 if *this > b,
// // 0 if *this == b, and
// // - 1 if *this < b in the i-th coordinate.
//
// int compare(const bigrational&, const unsigned long) const;
// int sort_s(K_POINT2D** const X, const unsigned long n)
// insertion-sort the array X of length n in the s-coordinate.
// return 1 if all the elements are distinct in the s-coordinate and
// 0 otherwise.
friend int sort_s(K_POINT2D** const, const unsigned long);
// int sort_t(K_POINT2D** const X, const unsigned long n)
// insertion-sort the array X of length n in the t-coordinate.
// return 1 if all the elements are distinct in the t-coordinate and
// 0 otherwise.
friend int sort_t(K_POINT2D** const, const unsigned long);
// // int sort(K_POINT2D** const X, const unsigned long n,
// // const unsigned long i)
// // insertion-sort the array X of length n in the i-th coordinate.
// // return 1 if all the elements are distinct in the i-th coordinate and
// // 0 otherwise.
//
// friend int sort(K_POINT2D** const, const unsigned long, const unsigned long);
// int overlap(const K_POINT2D& x) const
// return 1 if *this and x overlap, and
// 0 otherwise.
int overlap(const K_POINT2D&) const;
// int equiv(const K_POINT2D& x) const
// return 1 if *this and x are identical or
// have already been identified, and
// 0 otherwise
int equiv(const K_POINT2D&) const;
// int equal(K_POINT2D& x)
// return 1 if the boxes for *this and x are equal, and
// 0 otherwise
int equal(K_POINT2D&);
// int equal_s(K_POINT2D& x)
// returns 1 if *this and x are equal in the s-coordinate, and
// 0 otherwise.
int equal_s(K_POINT2D& x);
// int equal_t(K_POINT2D& x)
// returns 1 if *this and x are equal in the t-coordinate, and
// 0 otherwise.
int equal_t(K_POINT2D& x);
// // int equal_dir(K_POINT2D& x, const unsigned long i)
// // returns 1 if *this and x are equal in the i-th coordinate, and
// // 0 otherwise.
//
// int equal_dir(K_POINT2D&, const unsigned long);
// get_pts(): get algebraic points
// unsigned long get_pts(const bigrational& l_s, const bigrational& h_s,
// const bigrational& l_t, const bigrational& h_t,
// const K_RATPOLY& P1, const K_RATPOLY& P2,
// K_POINT2D**& pts,
// const bigrational& tol, const int count_edges)
// computes the intersections "pts" of 2 bivariate polynomials P1 and P2
// on/in the region [l_s, h_s] x [l_t, h_t].
// returns the number of intersections.
// if tol > 0 then
// a box for each intersection is no larger than tol in any direction.
// if tol = 0 then
// there is no limit on the size of boxes for intersections.
// if count_edges = 1 then
// the intersections on the boundary edges of the region are counted.
// if count_edges = 0 then
// the intersections on the boundary edges of the region are ignored.
friend unsigned long get_pts(const bigrational&, const bigrational&,
const bigrational&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&, const int);
friend unsigned long get_pts_interior(const bigrational&, const bigrational&,
const bigrational&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&);
friend int refine_interior(K_POINT1D* const, K_POINT1D* const,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D*&,
const bigrational&);
friend unsigned long get_pts_proto(const bigrational&, const bigrational&,
const K_RATPOLY&,
const bigrational&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&, const int);
friend unsigned long get_pts_proto(const bigrational&,
const bigrational&, const bigrational&,
const K_RATPOLY&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&, const int);
// unsigned long get_all_pts(const K_RATPOLY& P1, const K_RATPOLY& P2,
// K_POINT2D**& pts,
// const bigrational& tol)
// computes all the intersections "pts" of
// 2 bivariate polynomials P1 and P2.
// returns the number of intersections.
// if tol > 0 then
// a box for each intersection is no larger than tol in any direction.
// if tol = 0 then
// there is no limit on the size of boxes for intersections.
friend unsigned long get_all_pts(const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&);
// gen_curve_topo()
friend unsigned long gen_curve_topo(const K_RATPOLY&,
const bigrational&, const bigrational&,
const bigrational&, const bigrational&,
K_CURVE**&);
friend unsigned long gen_curve_topo_proto(const K_RATPOLY&,
const bigrational&,
const bigrational&,
const bigrational&,
const bigrational&,
K_POINT2D** const,
const unsigned long,
K_POINT2D** const,
const unsigned long,
K_POINT2D** const,
const unsigned long,
K_POINT2D** const,
const unsigned long,
K_POINT2D** const,
const unsigned long,
K_POINT2D** const,
const unsigned long,
K_CURVE**&);
// other
friend int match_pts(K_POINT2D** const, const unsigned long, K_SURF* const,
K_POINT2D** const, const unsigned long, K_SURF* const);
friend int pt_inside_trim_curves(K_POINT2D&,
K_CURVE** const, const unsigned long);
friend int pt_in_on_out_trim_curves(K_POINT2D&,
K_CURVE** const, const unsigned long);
friend unsigned long gen_partitions(K_PATCH* const, K_PARTITION**&);
int get_fp_approx(double*&) const;
};
#endif
|
