gmake submitand it will package up your files and email them to me.
LOOK CAREFULLY at the list of files it is submitting. It will only pack up the .cc and .h files (and the Makefile). If you've created some other file and used a different extension for it, you must edit the Makefile to make sure it is included. (See the comments in the Makefile.)
$ ./assign1 Problem1.txt ld.so.1: ./assign1: fatal: libCGAL.so: open failed: No such file or directory KilledThe problem is that the program is trying to load the CGAL library dynamically but can't find the file.
I fixed this problem by changing some of the path names in the CGAL "master" makefile. If you have already compiled the support code, you should execute the following commands:
$ gmake clean $ gmakeThis will delete the executable and all object files and then recompile everything. This will include the proper paths so that it can find the CGAL library. (Or, at least it works for me now!)
If you hadn't yet copied or compiled the code, then you do not need to do anything. There is no change to any of the support code files.
Generating the adjacency graph
In class we talked about two approaches to building the adjacency
graph:
I suggested that the first approach is easier, but I am not so sure now after a student pointed me to some web pages on "tesseral addressing" and after an idea I had last night (which I'll describe here).
"Tesseral addressing" can be used to label the cells in a quadtree decomposition. You can find some information (and examples) on this at:
Here's the idea I came up with for generating the adjacency graph after the quadtree has already been generated. It's somewhat similar to the Tesseral addressing idea. Assume that the starting cell of the decomposition has its origin at the lower left (southwest) corner and is scaled (nonuniformly) so that the rectangle is one unit long on each side. Label the height and width of each cell with a fraction of the form A / B.
The interpretation of this fraction would be that the respective dimension of the cell takes up A/B to (A+1)/B of the original cell. For example, suppose you decompose the original cell into four smaller cells. The upper left (i.e. northwest) cell would have the fractions 0/2 for X and 1/2 for Y. This means that the cell contains X coordinates from 0/2 to 1/2, and Y coordinates from 1/2 to 2/2. Suppose you subdivide this cell into four smaller subrectangles. The lower right (i.e. southeast) cell would have the fractions 1/4 for X and 2/4 for Y, meaning that it contains X coordinates from 1/2 to 2/4 and Y coordinates from 2/4 to 3/4. It's of course important not to reduce the fractions because the denominator tells you how small the cell is (or how deep it is in the quadtree.
Finding the neighbors of a given cell would involve determining the appropriate fractions for a cell (of the same size) to the north, south, east, or west. For example for the cell where X=1/4 and Y=2/4, the neighbor(s) to the east would have X=2/4 and Y=2/4. You can then search the quadtree for the neighbors based on these "coordinates". There could be three cases:
The Point type represents a two dimensional point using cartesian coordinates. You can create a point with one of the following constructors:
Point::Point(double x, double y) Point::Point(const Point&)To access the coordinates:
double Point::x() double Point::y()There are also the methods:
Bbox Point::bbox() // returns a bounding box of the point bool Point::operator==(Point) bool Point::operator!=(Point)However, you should be careful about using the equality (and inequality operators) because rounding errors coulde make a coordinate different by, say, 1e-124, so points that you think are equal might actually not be.
CGAL makes a distinction between points and vectors. You cannot add two points together. If you subtract two points, you get a vector. If you add a point and a vector, you get another point. The following operators reflect this idea:
Vector operator-(Point, Point) Point operator+(Point, Vector) Point operator-(Point, Vector)There is a special point which will help you do arithmetic with points and vectors:
CGAL::ORIGIN
The Vector class represents a two dimensional vector in cartesion coordinates. I would suggest creating vectors only as differences of two points (see the Point class above), but the obvious constructors (Vector::Vector(double x, double y) and Vector::Vector(const Vector&)) probably exist.
There are a number of operators defined for vectors:
Vector Vector::operator+(Vector) Vector Vector::operator-(vector) Vector Vector::operator-() // negates the vector double Vector::operator*(vector) // dot product double Vector::operator*(double) // right multiplication by a scalar double Vector::operator/(double) // scalar division
The Bbox class represents a bounding box (i.e. rectangle) in two dimensional cartesian space. You can create a bounding box with the following constructors:
Bbox::Bbox(double xmin, double ymin, double xmax, double ymax) Bbox::Bbox(const Bbox&)Note that this is the same as the lower left hand corner coordinates followed by the upper right hand coordinates. You can access the components of a Bbox with the following methods:
double Bbox::xmin() double Bbox::ymin() double Bbox::xmax() double Bbox::ymax()Two bounding boxes can be combined --- the result is a bounding box that encloses both. The addition operator is used for this:
Bbox Bbox::operator+(Bbox)If you want to know if two bounding boxes overlap, you can use the following method:
bool do_overlap(Bbox, Bbox)
The Polygon class is, in some sense, a wrapper around a container of points. The underlying container I decided to use is an STL vector. (This is "configured" in the cgaldefs.h file.)
You can create a Polygon from any sort of list by giving the constructor iterators pointing to the beginning and end of the list. You can also simply use STL vector operations on the polygon itself. Here's some examples:
#include "cgaldefs.h"
#include <iostream>
#include <list>
int main()
{
CGAL::set_pretty_mode(std::cout);
Polygon pg1;
pg1.push_back(Point(-1,0));
pg1.push_back(Point(0,-3));
pg1.push_back(Point(1,0));
pg1.push_back(Point(0,5));
cout << "Here's one polygon..." << endl << pg1 << endl;
list<Point> p;
p.push_front(Point(2.0,8.4));
p.push_front(Point(1.9,7.9));
p.push_front(Point(9.5,-.4));
Polygon pg2(p.begin(), p.end());
cout << "Here's another polygon..." << endl << pg2 << endl;
Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
Polygon pg3(points, points+4);
cout << "Yet another polygon..." << endl << pg3 << endl;
}
Here are a few of the member functions for polygons:
Bbox Polygon::bbox() double Polygon::area() bool Polygon::is_convex() int Polygon::size() // how many points?You can access the points, either by vertex number:
Point Polygon::vertex(int i) // first point is vertex 0or through an iterator. Here's an example of the latter:
for (Polygon::Vertex_iterator k = pg.vertices_begin();
k != pg.vertices_end(); k++)
cout << "here's a point: " << *k << endl;
There is also a Vertex_const_iterator in case you have a
const Polygon.
You can also get an iterator to the edges:
for (Polygon::Edge_const_iterator ei = pg.edges_begin();
ei != pg.edges_end(); ++ei) {
Segment e = *ei;
...
}
The convex hull algorithm takes a list of points and an inserter. Here's an example:
#include "cgaldefs.h"
#include <list>
#include <iostream>
#include<CGAL/convex_hull_2.h>
int main()
{
list<Point> ptlist;
ptlist.push_back(Point(-1,0));
ptlist.push_back(Point(0,-1));
ptlist.push_back(Point(1,0));
ptlist.push_back(Point(0,1));
ptlist.push_back(Point(0,0));
Polygon pg;
CGAL::convex_hull_2(ptlist.begin(), ptlist.end(),
std::inserter(pg, pg.vertices_begin()));
CGAL::set_pretty_mode(std::cout);
cout << "The convex hull is:" << endl << pg;
}
Note that you have to include an additional CGAL header file. (Since
you won't have to use it often, I didn't include it in the
cgaldefs.h file.)