// 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_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&);
// K_POINT2D :: equal_s(K_POINT2D& x)
// returns 1 if *this and x are equal in the s-coordinate, and
// 0 otherwise.
int K_POINT2D :: equal_s(K_POINT2D& x);
// K_POINT2D :: equal_t(K_POINT2D& x)
// returns 1 if *this and x are equal in the t-coordinate, and
// 0 otherwise.
int K_POINT2D :: 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