00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef TRIANGULATOR_H
00016 #define TRIANGULATOR_H
00017
00018 #include "pandabase.h"
00019 #include "luse.h"
00020 #include "vector_int.h"
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 class EXPCL_PANDA_MATHUTIL Triangulator {
00039 PUBLISHED:
00040 Triangulator();
00041
00042 void clear();
00043 int add_vertex(const LPoint2d &point);
00044 INLINE int add_vertex(double x, double y);
00045
00046 INLINE int get_num_vertices() const;
00047 INLINE const LPoint2d &get_vertex(int n) const;
00048 MAKE_SEQ(get_vertices, get_num_vertices, get_vertex);
00049
00050 void clear_polygon();
00051 void add_polygon_vertex(int index);
00052 INLINE bool is_left_winding() const;
00053
00054 void begin_hole();
00055 void add_hole_vertex(int index);
00056
00057 void triangulate();
00058
00059 int get_num_triangles() const;
00060 int get_triangle_v0(int n) const;
00061 int get_triangle_v1(int n) const;
00062 int get_triangle_v2(int n) const;
00063
00064 private:
00065 typedef pvector<LPoint2d> Vertices;
00066 Vertices _vertices;
00067
00068 vector_int _polygon;
00069
00070 typedef pvector<vector_int> Holes;
00071 Holes _holes;
00072
00073 class Triangle {
00074 public:
00075 INLINE Triangle(Triangulator *t, int v0, int v1, int v2);
00076 int _v0, _v1, _v2;
00077 };
00078
00079 typedef pvector<Triangle> Result;
00080 Result _result;
00081
00082
00083 typedef struct {
00084 double x, y;
00085 } point_t, vector_t;
00086
00087
00088 struct segment_t {
00089 INLINE segment_t();
00090 INLINE segment_t(Triangulator *t, int v0_i, int v1_i, int prev, int next);
00091
00092 point_t v0, v1;
00093 int is_inserted;
00094 int root0, root1;
00095 int next;
00096 int prev;
00097 int v0_i;
00098 };
00099
00100 typedef pvector<segment_t> Segments;
00101 Segments seg;
00102 vector_int permute;
00103 int choose_idx;
00104
00105
00106
00107 typedef struct {
00108 int lseg, rseg;
00109 point_t hi, lo;
00110 int u0, u1;
00111 int d0, d1;
00112 int sink;
00113 int usave, uside;
00114 int state;
00115 } trap_t;
00116
00117
00118
00119
00120 typedef struct {
00121 int nodetype;
00122 int segnum;
00123 point_t yval;
00124 int trnum;
00125 int parent;
00126 int left, right;
00127 } node_t;
00128
00129
00130 typedef struct {
00131 int vnum;
00132 int next;
00133 int prev;
00134 int marked;
00135 } monchain_t;
00136
00137
00138 typedef struct {
00139 point_t pt;
00140 int vnext[4];
00141 int vpos[4];
00142 int nextfree;
00143 int user_i;
00144 } vertexchain_t;
00145
00146
00147 typedef pvector<node_t> QueryStructure;
00148 QueryStructure qs;
00149 typedef pvector<trap_t> TrapezoidStructure;
00150 TrapezoidStructure tr;
00151
00152
00153
00154
00155 pvector<monchain_t> mchain;
00156
00157
00158
00159
00160
00161
00162
00163 pvector<vertexchain_t> vert;
00164
00165
00166
00167 vector_int mon;
00168
00169 vector_int visited;
00170
00171 bool check_left_winding(const vector_int &range) const;
00172 void make_segment(const vector_int &range, bool want_left_winding);
00173
00174 int choose_segment();
00175 static double math_log2(double v);
00176 static int math_logstar_n(int n);
00177 static int math_N(int n, int h);
00178
00179 int newnode();
00180 int newtrap();
00181 int _max(point_t *yval, point_t *v0, point_t *v1);
00182 int _min(point_t *yval, point_t *v0, point_t *v1);
00183 int _greater_than(point_t *v0, point_t *v1);
00184 int _equal_to(point_t *v0, point_t *v1);
00185 int _greater_than_equal_to(point_t *v0, point_t *v1);
00186 int _less_than(point_t *v0, point_t *v1);
00187 int init_query_structure(int segnum);
00188 int is_left_of(int segnum, point_t *v);
00189 int inserted(int segnum, int whichpt);
00190 int locate_endpoint(point_t *v, point_t *vo, int r);
00191 int merge_trapezoids(int segnum, int tfirst, int tlast, int side);
00192 int add_segment(int segnum);
00193 int find_new_roots(int segnum);
00194 int construct_trapezoids(int nseg);
00195
00196 int inside_polygon(trap_t *t);
00197 int newmon();
00198 int new_chain_element();
00199 double get_angle(point_t *vp0, point_t *vpnext, point_t *vp1);
00200 int get_vertex_positions(int v0, int v1, int *ip, int *iq);
00201 int make_new_monotone_poly(int mcur, int v0, int v1);
00202 int monotonate_trapezoids(int n);
00203 int traverse_polygon(int mcur, int trnum, int from, int dir);
00204 void triangulate_monotone_polygons(int nvert, int nmonpoly);
00205 void triangulate_single_polygon(int nvert, int posmax, int side);
00206
00207 friend class Triangle;
00208 friend struct segment_t;
00209 };
00210
00211 #include "triangulator.I"
00212
00213 #endif
00214