GeoWin

Introduction

A GeoWin is an editor for sets of geometric objects (geo_scenes). It provides an interface for the visualization of the result and progression of geometric algorithms using the window data type of LEDA. A geo_scene maintains a container (a STL or LEDA list) with geometric objects. The GeoWin data type can be used for:

• the construction and display of geometric objects and data structures
• the visualization of geometric algorithms
• writing interactive demos for geometric algorithms
• debugging geometric algorithms.

Let us first have a look at the interactive use of GeoWin. You should open a GeoWin by starting one of the demonstration programs. A window with menus File, Edit, Scenes, Window, Options and Help will pop up with an empty display region and a status line showing the position of the mouse. In the Help menu you will find 3 menu buttons:

• About - a simple about dialog
• News - tells you what's new in the current release
• Buttons - teaches you how to use the mouse buttons in GeoWin.

With the left mouse button you can input a geometric object or scroll the scene by holding the button while moving the mouse. By using the middle mouse button you can select an object by clicking on it or a group of objects by holding the button and moving the mouse (that draws a box, and all objects intersecting this box will be selected). The right mouse button opens a menu by clicking on an object. This menu contains the options setup (setup the properties of the object), select (selection of the object), delete (delete the object), object (change the value of the object) and raise (raise the object). By clicking on the background with the right mouse button you can access the setup dialog of the whole scene, where you can setup some global parameters of the scene (for instance colors and line parameters). Next we give a short description of the menus in GeoWin:

File menu: Here you will find buttons for I/O operations. You can save, load and export (save without header) scenes, and you can also output the contents of scenes in postscipt format and make screenshots. In the File menu you will also find the Quit button.

Edit menu: A menu, where you find buttons for generating, reading, marking, unmarking, copying, deleting, moving and rotating objects.

Scenes menu: A menu with buttons and submenus for opening, closing, clearing and activating (making a scene the current or active scene) scenes. This menu also contains a panel for setting the visibility and other options of a scene. There are also submenus for looking at the contents of the scene.

Window menu: A menu with redraw and zoom (adjusting the window coordinates) operations. Here you can also find a button for showing 3d output (that is only interesting for scenes supporting this output mode).

Options menu: A menu with sub-panels for editing various parameters of GeoWin and for setting the scene defaults.

Done : The Done-button (see the following description of the GeoWin data type).

After discussing the menus of GeoWin let us have a look at the various parameters and attributes controlling the behavior of GeoWin. Every scene defines default attributes for its geometric objects. In editable scenes you can change the attributes for every single object. First, let's have a look at the default attributes of the scene. Open a scene in GeoWin, and then click on the background (or use the options submenu in the Scenes menu) to open a panel, where you can set them. You will find the following options:

• highlight focus: If this option is enabled, the object under the mousepointer will be highlighted. (for highlighting GeoWin will use the color of selected boundaries)

• interior color: An object that has to be filled will be filled with this color.

• boundary color: The default color of the boundary of a non selected object in this scene.

• selected color: The default color of the boundary of a selected object in this scene.

• point style: The point style used in the scene.

• active/non active line width: The default line width in active and non active scenes. Used for painting the boundary of objects.

• line style: The default line style used in the scene (for painting the boundary). Can be solid, dashed or dotted.

• visibility: Here you can set the option 'Always visible'. If you set this option, the scene will still be visible after opening another scene.

Using this panel you can set some default attributes for the whole scene. But in editable scenes it is also possible to change attributes of a single object. Open a scene and paint some objects. Now click with the right mouse button on an object. A little menu appears. Using the setup button in this menu you get a panel on the screen. There you can set the following attributes:

• color of interior: This color is used to paint the interior of the object.

• color of boundary: Boundary color of the object, if it is not selected

• line width: The line width that is used to paint the boundary of the object.

• line style: The line style that is used to paint the boundary of the object.

• object label: An attribute defining the label of an object

Global parameters

A GeoWin has the window parameters background color, background pixmap (pm texture) and the grid parameters (grid style, grid dist and show grid). There are also some additional parameters, that can be set in the panels of the Options menu.

• Show position: This parameter controls whether the mouse coordinates should be shown in the status line.

• Time Outs for Double Click and Dragging, Capture width: Influences the behavior of the mouse input.

• Default precision and Filter: If you are using rational LEDA types in your GeoWin, these options are helpful. They let you set the precision (type: int) that is used when converting floating point types to rational LEDA types and let you switch on (1) and off (0) the floating point filter used by many functions working with rational LEDA types.

• Measure Time: If this flag is true, GeoWin outputs the used time after running a geometric algorithm.

• 3d Output parameters: They are only important for scenes supporting 3d output.

• Eliminate: This flag controls whether hidden lines should be eliminated or not.

• Solid: This flag controls whether the 3d output should be painted solid.

• Speed: A Parameter that defines the speed of the animation when the three-dimensional output is painted.

• Scaling parameters: Here you can set the x and y coordinates of the window display area.

GeoWin data type

#include <CGAL/geowin_support.h>

• Class declaration of GeoWin.

Non-Member Functions

GeoWin*	get_geowin ( geo_scene sc)
		returns a pointer to the GeoWin of scene $$sc.

Registration of types

The following two function templates can be used to register types for usage in edit scenes of GeoWin. To use GeoWin with your own types, the container storing the geometric objects and the type of your geometric objects must fulfill some conditions:

1. The container must provide the functionality of the STL list (especially $$CONTAINER_TYPE::iterator and $$CONTAINER_TYPE::value_type). You can use LEDA lists too.
2. You have to provide a generator function

   void geowin_generate_objects(GeoWin& gw,CONTAINER_TYPE& L);
   

   This generator function can be used to generate input and return it in L.
3. If you don't want to use LEDA lists, you should provide an info function

   leda_string geowin_info_fcn(const CONTAINER_TYPE& L);
   

   This info function should return a string desribing the container.

1. default and copy constructor

   TYPE();
   TYPE(const TYPE&);
   

2. operators for writing to an ostream and reading from an istream

   std::ostream& operator<<(std::ostream&, const TYPE&);
   std::istream operator>>(std::istream&, TYPE&);
   

3. operators for writing to/ reading from a LEDA window

   leda_window& operator<<(leda_window&, const TYPE&);
   leda_window& operator>>(leda_window&, TYPE&);
   

4. an operator for writing to a ps_file for postscript output

   ps_file& operator<<(ps_file&, const TYPE&);
   

5. a function for translating the object by a vector (dx,dy):

   void geowin_Translate(TYPE& obj, double dx, double dy);
   

6. a function for rotating the object about point(dx,dy) by angle a:

   void geowin_Rotate(TYPE& obj,double dx,double dy,double a);
   

7. a function for calculating the bounding box of the object:

   void geowin_BoundingBox(const TYPE& obj, double& x1, 
            double& x2, double& y1, double& y2);
   

   The function has to return the minimal and maximal x and y coordinates of the object $$obj.
8. a function for deciding whether the object intersects a box:

   bool geowin_IntersectsBox(const TYPE& obj, double x1,
           double y1, double x2, double y2,bool f)
   

   This function gets the object obj, the coordinates of the box $$x1,y1,x2,y2 and a parameter $$f (true, if the object is filled, false otherwise). The function should return true if the object intersects the box $$(x1, y1, x2, y2), false otherwise.

   To register an additional type (that means a container class) for usage in edit scenes of GeoWin, you have to call one of the two following functions:

   template<class T> void geowin_init_default_type( T* t, string str);
   template<class T> void geowin_init_basic_type(T* t,string str);
   

   str is a name desribing the container and its storage; it must be unique and is used for instance for saving objects. The first function will register the container class, build a scene prototype and set functions. The second function will do the same, but it will not set an info-, translate-, rotate- and generate function. That means that you have to provide in this case only the remaning functions and operators. Register your additional types before creating a GeoWin.

void	geowin_init_default_type ( T* t, leda_string str)
		registers a type (container including geometric objects) for usage in scenes of GeoWin and links a scene typename $$str with the real type. The container can be a LEDA list or an STL list. Some functions and operators are required (see above).
void	geowin_init_basic_type ( T* t, leda_string str)
		registers a type (container including geometric objects) for usage in scenes of GeoWin and links a scene typename $$str with the real type. The container can be a LEDA list or an STL list. Some functions and operators are required (see above).

For the CGAL kernel types (using STL lists as containers) 2D Point, Line, Ray, Segment, Triangle, Iso Rectangle, Circle and for the 3D Point and the non kernel type Polygon the required functions and operators are already provided in $$geowin_support.h . Note that when you use the GeoWin library in the CGAL namespace (see Implementation), the functions have to be in the CGAL namespace too. It is also possible to encapsulate pointers to the required functions in a traits class.

template<class CONTAINER>
void	geowin_init_default_type ( geo_scene_traits<CONTAINER> tr)
		registers a type (container including geometric objects) for usage in scenes of GeoWin and links a scene typename with the real type. The container can be a LEDA list or an STL list. Some functions and operators are required (see above).

The function pointers and the scene typename gets $$tr in the constructor:

• Class declaration of geo_scene_traits<CONTAINER>.

Examples using the GeoWin data type

In this section two examples will teach you how to use GeoWin for writing interactive demos for geometric algorithms. You will find these (and a lot other) demo programs in the $$demo/GeoWin directory of your CGAL installation. In the following examples a few typedefs from $$geowin_support.h are used. They are all in the form

typedef CGAL::Cartesian<double>  REP;
typedef CGAL::Point_2< REP >     CGALPoint;
typedef std::list<CGALPoint>     CGALPointlist;

typedef CGAL::Circle_2< REP >    CGALCircle;
typedef std::list<CGALCircle>    CGALCirclelist;

typedef CGAL::Line_2< REP >      CGALLine;
typedef std::list<CGALLine>      CGALLinelist;

...

Simple demo demonstrating the minimal enclosing circle algorithm

The following demonstration program first registers lists with CGAL 2D Points, because such a container will be used in the editable scene created shortly afterwards. Then a GeoWin and two geo_scenes are created. The first created scene is an editable scene storing CGAL 2D Points in a list. The second created scene is a result scene. The input for this scene is the contents of scene $$my_scene. For computing the contents of the result scene result the update object $$min_circ is used. GeoWin calls this the update function of the update object every time the input scene $$my_scene changes to update the result scene. The update function gets the current contents of the input scene (a list of CGAL 2D Points) and computes the minimal enclosing circle. After creating the 2 scenes the visibility flag of the result scene is set and the interactive mode of GeoWin is started.

CGALcircle.C :

#include <CGAL/Cartesian.h>
#include <CGAL/Min_circle_2.h>
#include <CGAL/Min_circle_2_traits_2.h>
#include <CGAL/geowin_support.h>

typedef  CGAL::Cartesian<double>         R;
typedef  CGAL::Point_2<R>                Point;
typedef  CGAL::Min_circle_2_traits_2<R>  Traits;
typedef  CGAL::Min_circle_2<Traits>      Min_circle;
typedef  Min_circle::Circle              OptCircle;

class geo_circ : public geowin_update<std::list<CGALPoint>,std::list<CGALCircle> >
{
public:
 void update(const CGALPointlist& L, CGALCirclelist& Cl)
 {
   Cl.clear();
   if (L.size() < 2) return;

   Min_circle  mc1( L.begin(), L.end());
   OptCircle ci= mc1.circle();

   Point ctp=ci.center();
   CGALCircle conv(ctp,ci.squared_radius());
   Cl.push_back(conv); 
 }
};

int main()
{
  geowin_init_default_type((CGALPointlist*)0, leda_string("CGALPointList"));

  CGALPointlist L;
  GeoWin GW("CGAL - Optimisation demo");

  geo_scene my_scene= GW.new_scene(L);  
  GW.set_point_style(my_scene, leda_disc_point);
  
  geo_circ min_circ;
  geo_scene result  = GW.new_scene(min_circ ,my_scene , 
                                   leda_string("Minimal circle"));
  GW.set_color(result,leda_blue);
  GW.set_line_width(result, 3);
  GW.set_visible(result,true);

  GW.edit(my_scene);
}

A Delaunay triangulation demo using redraw and update objects

The second example is a bit more complex. It uses three user editable input scenes:
$$my_scene contains points that are the input for an algorithm computing the Delaunay triangulation. $$line_scene contains lines; these are used for finding triangles of the Delaunay triangulation intersected by these lines. $$pointloc_scene contains points; these are used for locating triangles of the Delaunay triangulation. After the creation of the three edit scenes three result scenes are created. The result scene $$sc1 and $$res3 use classes derived from $$geowin_redraw and $$geowin_update for updating and redrawing. After creating the result scenes we tell GeoWin using the $$add_dependence method, that two result scenes should be updated not only when their input scenes change.

CGALdtfl.C :

#include <CGAL/basic.h>
#include <CGAL/Cartesian.h>
#include <CGAL/squared_distance_2.h>   
#include <CGAL/Point_2.h>
#include <CGAL/predicates_on_points_2.h>
#include <CGAL/Triangulation_euclidean_traits_2.h>
#include <CGAL/Triangulation_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/geowin_support.h>

typedef double coord_type;
typedef CGAL::Cartesian<coord_type>  Rep;
typedef CGAL::Point_2<Rep>  Point;
typedef CGAL::Segment_2<Rep>  Segment;

typedef CGAL::Triangulation_euclidean_traits_2<Rep> Gt;
typedef CGAL::Triangulation_vertex_base_2<Gt> Vb;
typedef CGAL::Triangulation_face_base_2<Gt>  Fb;
typedef CGAL::Triangulation_default_data_structure_2<Gt,Vb,Fb> Tds;
typedef CGAL::Triangulation_2<Gt,Tds>  Triang_2;
typedef CGAL::Delaunay_triangulation_2<Gt,Tds> Delaunay_triang_2;

typedef Delaunay_triang_2::Face::Face_handle Face_handle;
typedef Delaunay_triang_2::Line_face_circulator Line_face_circulator;

typedef Triang_2::Face  Face;
typedef Triang_2::Vertex Vertex;
typedef Triang_2::Edge Edge;
typedef Triang_2::Vertex_handle Vertex_handle;
typedef Triang_2::Edge_iterator  Edge_iterator;


class geo_delau : public geowin_update<std::list<CGALPoint>,std::list<CGALSegment> >
{
public:
 void update(const CGALPointlist& L, CGALSegmentlist& Sl)
 {
  Delaunay_triang_2 dt;    
  Sl.clear();      
  dt.insert(L.begin(),L.end());

  Edge_iterator eit = dt.edges_begin();
  Edge_iterator beyond = dt.edges_end();   
  Edge eact;

  while (eit != beyond) {
       eact = *eit;         
       Sl.push_back(dt.segment(eact));               
       ++eit;  
  }       
 }
};

class geo_triangles : public geowin_redraw, 
    public geowin_update<CGALPointlist, CGALPointlist >
{
public:

  CGALTrianglelist LT;
  geo_scene lines;

  virtual ~geo_triangles() {}

  virtual void draw(leda_window& W, leda_color c1, leda_color c2,
                    double x1,double y1,double x2,double y2)
  {  
    std::list<CGALTriangle>::const_iterator it   = LT.begin(), stop = LT.end();
    leda_color old = W.set_fill_color(leda_green);
    while( it != stop )
    {
       W << convert_to_leda(*it);
       it++;
    }
    W.set_fill_color(old);
  }

  virtual void update(const CGALPointlist& L, CGALPointlist&)
  { 
    Delaunay_triang_2 dt;    
    dt.insert(L.begin(),L.end());
    LT.clear();

    if (dt.dimension() != 2) return;

    GeoWin* gw = get_geowin(lines);

    CGALLinelist LST;
    gw->get_objects(lines,LST);

    std::list<CGALLine>::const_iterator it;
    CGALLine lakt;
    CGALPoint p1,p2; 

    for(it=LST.begin(); it != LST.end(); ++it) { 
       lakt= *it;
       p1=lakt.point(1); p2=lakt.point(2);
       Face_handle f = dt.locate(p1);
      
       Line_face_circulator lfc=dt.line_walk(p1,p2,f), done(lfc);
 
       if (lfc== (CGAL_NULL_TYPE) NULL) continue;

       do {
	  if(! dt.is_infinite( lfc  )){ LT.push_back(dt.triangle(lfc)); }
       }  
       while (++lfc != done); 
      
    }   
  }
};

class geo_triangles2 : public geowin_redraw, 
       public geowin_update<CGALPointlist, CGALPointlist >
{
public:

  CGALTrianglelist LT;
  geo_scene locate_points;

  virtual ~geo_triangles2() {}

  virtual void draw(leda_window& W, leda_color c1, leda_color c2,
                    double x1,double y1,double x2,double y2)
  {  
    std::list<CGALTriangle>::const_iterator it   = LT.begin(), stop = LT.end();
    leda_color old = W.set_fill_color(leda_blue);
    while( it != stop )
    {
       W << convert_to_leda(*it);
       it++;
    }
    W.set_fill_color(old);
  }

  virtual void update(const CGALPointlist& L, CGALPointlist&)
  { 
    Delaunay_triang_2 dt;    
    dt.insert(L.begin(),L.end());

    LT.clear();

    if (dt.dimension() != 2) return;

    GeoWin* gw = get_geowin(locate_points);   

    CGALPointlist LST;
    gw->get_objects(locate_points,LST);

    std::list<CGALPoint>::const_iterator it;
    CGALPoint lakt;

    for(it=LST.begin(); it != LST.end(); ++it) { 
       lakt= *it;
       Face_handle f = dt.locate(lakt);
       if (f != NULL && !dt.is_infinite(f)) LT.push_back(dt.triangle(f));
    }   
  }
};


int main()
{
  geowin_init_default_type((CGALPointlist*)0, leda_string("CGALPointList"));
  geowin_init_default_type((CGALLinelist*)0, leda_string("CGALLineList"));

  CGALPointlist L, LOC;
  CGALLinelist  CGLL;

  GeoWin GW("CGAL - Triangulation demo");
  geo_scene my_scene= GW.new_scene(L); 
  // another input scene for the lines ...
  geo_scene line_scene= GW.new_scene(CGLL);
  GW.set_color(line_scene, leda_grey2);

  // another input scene for the points for location algorithm
  geo_scene pointloc_scene= GW.new_scene(LOC);
  GW.set_color(pointloc_scene, leda_blue);

  geo_triangles TRS;
  geo_scene sc1 = GW.new_scene( TRS, TRS, my_scene, "Triangles"); 
  GW.set_color(sc1, leda_blue);
  GW.set_visible(sc1,true);
  TRS.lines = line_scene;
 
  geo_delau delaunay_triang;
  geo_scene res2 = GW.new_scene(delaunay_triang, my_scene, 
                                leda_string("Delaunay Triangulation"));
  GW.set_color(res2, leda_red);

  geo_triangles2 TPT;
  geo_scene res3 = GW.new_scene( TPT, TPT, my_scene, "Triangles2"); 
  GW.set_color(res3, leda_red);
  TPT.locate_points = pointloc_scene;
  
  GW.add_dependence(line_scene,sc1);
  GW.add_dependence(pointloc_scene,res3);
  GW.set_all_visible(true);

  GW.edit(my_scene);
  return 0;  
}

Implementation