tailieunhanh - Effective Computational Geometry for Curves & Surfaces - Boissonnat & Teillaud Part 2

Tham khảo tài liệu 'effective computational geometry for curves & surfaces - boissonnat & teillaud part 2', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 1 Arrangements 15 that all algebraic numbers we obtain as the x-coordinates of either one-curve or of two-curve events are comparable. Whenever we have an interval representation l r of a simple root a we know that the generating polynomial is square-free. Thus we can refine the isolating interval by iteratively halving it and examining at the signs of l l 2r and r until we finally obtain that a G l r c l r where r1 l1 is arbitrarily small. We are now ready to devise a framework for the implementation of the rest of the sweep-line predicates and constructions. We denote by C a sweepable x-monotone conic arc supported by the curve C where we can write using the notation of Equation that either C x y1 x or C x y2 x . Intersections Let Cl and C2 be the supporting conics of the two given x-monotone conic arcs Cl and C 2 and let i x be the resultant of C1 and C2 with respect to y. The only x-coordinates at which an intersection between the supporting conic curves can take place are the real roots of j . Let a be a real root of j . We show how to decide whether the two arcs J1 and C2 intersect at x a. If a is a simple root of i then the sweepable arcs J1 and C2 intersect transversally at x a if they intersect there at all. Let al ar be the isolating interval of a. We refine this interval until it contains no x-coordinate of any one-curve event of the supporting conics C1 or C2. Now our two x-monotone arcs are defined on the entire refined interval a a r and they intersect at most once in this interval. It is sufficient to check whether the signs of J1 a l C2 a and J1 a r C2 a r differ. We therefore need to compute the signs of one-root numbers in this case since al a r G Q. On the other hand if a is a one-root number we simply have to check whether the y-values Ci a and C2 a are equal note that J1 a. J2 a. G IF . We still have to determine the multiplicity of the relevant intersection point s . Let a be a root of i of multiplicity m. The case m 1 is easy because we .