00001 /* LIBGUL - Geometry Utility Library 00002 * Copyright (C) 1998-1999 Norbert Irmer 00003 * 00004 * This library is free software; you can redistribute it and/or 00005 * modify it under the terms of the GNU Library General Public 00006 * License as published by the Free Software Foundation; either 00007 * version 2 of the License, or (at your option) any later version. 00008 * 00009 * This library is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 * Library General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU Library General Public 00015 * License along with this library; if not, write to the 00016 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 00017 * Boston, MA 02111-1307, USA. 00018 */ 00019 00020 #ifndef GUGR_TRIANGULATE_H 00021 #define GUGR_TRIANGULATE_H 00022 00023 namespace gugr { 00024 00025 /* ------------------------------------------------------------------------ 00026 Triangulates the regions of a graph. E must be regularized, and V 00027 sorted. For this purpose the graph is divided into monotone chains. 00028 Between two monontone chains lies a monotone polygone. 00029 Only those triangles are calculated, whose edges have a positive face 00030 index on the inward side 00031 ------------------------------------------------------------------------- */ 00032 void Triangulate( graph_edge_list *E, graph_vertex_list *V, 00033 const rational& far_left, triangle_list *T ); 00034 00035 /* ------------------------------------------------------------------------ 00036 Triangulates a monotone polygon 00037 00038 The vertices in V1 and V2, and the edges in E are deleted 00039 in this function! 00040 -------------------------------------------------------------------------- */ 00041 void TriangulateMonotonePolygon( 00042 graph_vertex_list2 *V1, graph_vertex_list2 *V2, 00043 graph_edge_list *E, triangle_list *T ); 00044 00045 } 00046 00047 #endif 00048