Convex Polygon class

A convex polygon is a simple polygon in which all its interior angles are strictly less than 180°. In the following picture, all polygons are convex, excepting one. Guess which one.

A polygon has n vertices and n edges. A polygon is said to be regular when all edges have the same length. In the picture we have two regular polygons. Can you identify them?

There are several operations that can be done with polygons. Here we mention some examples:

Convex hull: Given a set of points, we can calculate the smallest convex polygon that contains the set.

Intersection: The intersection of two convex polygons is a convex polygon, as shown in the figure.

Convex Union: Given two convex polygons, the convex union is the smallest convex polygon that contains both polygons. Equivalently, it is the convex hull of both polygons.

Bounding box: Given a set of convex polygons, find the smallest bounding box that encloses all polygons.

(notice that polygons with a huge number of vertices look like circles in the figure).

Inside: We can check whether a convex polygon is inside another convex polygon.

Information about polygons

Given a polygon, we may want to obtain information about its properties, for example:

• Number of vertices and edges.
• Length of the perimeter.
• Area.
• Is the polygon regular?
• Coordinates of the centroid.

Some particular cases of polygons

For convenience, we will consider some particular cases of polygons (not always recognized as polygons by mathematicians!):

• Empty polygon: a polygon with zero vertices.
• Monogon: a polygon with one vertex (a point).
• Digon: a polygon with two vertices (a segment).

The remaining polygons are more conventional: triangles, quadrilaterals, pentagons, hexagons, etc.

The Class ConvexPolygon

The project consists of designing a class to represent and manipulate convex polygons. As part of the project, a simple polygon calculator will have to be created.

Several decisions will have to be taken in the design of the class ConvexPolygon:

• Internal representation of a convex polygon.
• Public and private methods.
• Algorithms to perform the required operations efficiently (remember, \(n \log n\) is better than \(n^2\)).
• Specification and documentation of the Application Programming Interface (API).
• Set of test examples to check the functionality of the class.

The Polygon calculator

The Polygon calculator must read commands from the standard input and write their answers to the standard output. In some cases, it also should use some files.

Given that the content of file2.txt is

p2 1 1 0.5 0.1 0 0 1 0
p3 0.1 0.1

the execution of the script using the calculator on the left should produce the output on the right:

# sample script for the polygon calculator polygon p1 0 0 0 1 1 1 print p1 area p1 perimeter p1 vertices p1 centroid p1 save file1.txt p1 load file2.txt list print p1 print p2 print p3 union p3 p1 p2 print p3 inside p1 p3 setcol p1 1 0 0 setcol p2 0 1 0 setcol p3 0 0 1 draw image.png p1 p2 p3 bbox p4 p1 p2 print p4 # some errors foobar print p5

# ok p1 0.000 0.000 0.000 1.000 1.000 1.000 0.500 3.414 3 0.333 0.667 ok ok p1 p2 p3 p1 0.000 0.000 0.000 1.000 1.000 1.000 p2 0.000 0.000 1.000 1.000 1.000 0.000 p3 0.100 0.100 ok p3 0.000 0.000 0.000 1.000 1.000 1.000 1.000 0.000 yes ok ok ok ok ok p4 0.000 0.000 0.000 1.000 1.000 1.000 1.000 0.000 # error: unrecognized command error: undefined identifier

Moreover, the content of file1.txt will be

p1 0.000 0.000 0.000 1.000 1.000 1.000

and image.png will be

Details of the polygon calculator

The specification of the commands is given bellow. Each command is given in a line and produces exactly one line of output.

Comments

Lines starting with a hash sign (#) are comments. Their output is just a hash sign.

Polygon identifiers

All commands include polygon identifiers. These are made by words, such as p, p1, p2, or pol_gr.

Points

Points in the commands are given by two pairs of real numbers, in standard notation, to denote the X and Y coordinates. For instance, 0 0 or 3.14 -5.5. When printed, all real numbers must be formatted with three digits after the decimal dot.

Colors

Colors in the commands are given by three real numbers in [0,1], in standard notation, to denote the RGB color. For instance, 0 0 0 denotes black, 1 0 0 denotes red, and 1 0.64 0 denotes orange.

File names

Filenames in the commands are made up of words, such as f, pol.txt or some_file_name.pol.

The polygon command

The polygon command associates an identifier with a convex polygon made by a set of zero or more points. If the polygon identifier is new, it will create it. If it already existed, it will overwrite the previous polygon. New polygons are black.

The print command

The print command prints the name and the vertices of a vertices of a given polygon. The output must only contain the vertices in the convex hull of the polygon, in clockwise order, starting from the vertex will lower X (and the vertex with lower Y in case of ties). They must be printed in a single line, with one space separating each value.

The area command

The area command prints the area of the given polygon.

The perimeter command

The perimeter command prints the perimeter of the given polygon.

The vertices command

The vertices command prints the number of vertices of the convex hull of the given polygon.

The centroid command

The centroid command prints the centroid of the given polygon.

The list command

The list command lists all polygon identifiers, lexycographically sorted.

The save command

The save command saves the given polygons in a file, overwriting it if it already existed. The contents of the file must be the same as in the print command, with a polygon per line.

The load command

The load command loads the polygons stored in a file, in the same way as polygon, but retrieving the vertices and identifiers from the file.

The setcol command

The setcol command associates a color to the given polygon.

The draw command

The draw command draws a list of polygons in a PNG file, each one with its associated color. The image should be of 500x500 pixels, with white background and the coordinates of the vertices should be scaled to fit in the 498x498 central part of the image, while preserving the original aspect ratio.

The intersection command

This command may receive two or three parameters:

• When receiving two parameters p1and p2, p1should be updated to the

• intersection of the original p1 and p2.

• When receiving three parameters p1, p2 and p3, p1should be updated

• to the intersection of p2 and p3.

Take into account that identifiers may be repeated.

The union command

Just as the intersection command, but with the convex union of polygons.

The inside command

Given two polygons, the inside command prints yes or not to tell whether the first is inside the second or not.

The bbox command

The bbox command creates a new polygon with the four vertices corresponding to the bounding box of the given polygons.

Commands without answer

As seen in the examples, some commands do not really produce an answer. In this case ok must be printed, unless there was some error.

Errors

If any command contains or produces an error, the error must be printed in a line starting with error: and the command must be completely ignored (as if it was not given). Possible errors include:

• invalid command
• command with wrong number or type of arguments
• undefined polygon identifier
• wrong format
• ...

Precision

In order to cope with precision issues of float numbers, use an absolute tolerance of 1e-12 when comparing values.

Instal·lació dependències

git clone https://github.com/pngwriter/pngwriter.git

# entreu al repositori amb el codi font de la llibreria que heu baixat
cd pngwriter

# prepareu la compilació amb algunes opcions
cmake -DPNGwriter_USE_FREETYPE=OFF -DCMAKE_INSTALL_PREFIX=$HOME/libs .

# compileu la llibreria
make

# instal·leu la llibreria
make install

MAC OS X

# instal·la brew
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

# instal·la cmake i libpng
brew install cmake libpng

UBUNTU

sudo apt install cmake libpng16-tools libpng16-devtools

make

./main.exe

i si volem, per exemple, redirigir un arxiu txt amb les comandes al programa:

./main.exe < "nom_arxiu".txt

Makefile

El contingut del makefile és el següent:

CXXFLAGS = -Wall -std=c++11 -O2 -DNO_FREETYPE -I $(HOME)/libs/include 

all: main.exe

clean:
	rm -f main.exe  *.o

main.exe:main.o Point.o ConvexPolygon.o
	$(CXX) $^ -L $(HOME)/libs/lib -l PNGwriter -l png -o $@

main.o: main.cc Point.hh ConvexPolygon.hh


Point.o: Point.cc Point.hh


ConvexPolygon.o: ConvexPolygon.cc ConvexPolygon.hh Point.hh