This project contains all the sources of the scenario week dedicated to solving the Art Gallery Problem.
It also provides, as a part of the development, the source of the
framework for generation of random polygons with specific "features"
and QuickCheck-style testing of geometric procedures. For more
examples, check the test
files (for instance,
src/test/scala/ucl/scenario/geometry/VisibilityCheckerTests.scala)
and the section Generating random polygons below.
The overall experience of organising the competition and using the testing framework is described in the ICFP'16 experience report Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms.
Some relevant reading includes the following books, papers and links:
See the folder docs.
- Art Gallery Problem
- Art Gallery Book
- Visibility of Simple Polygon from a Point
- Computational Geometry: Algorithms and Applications
- Scala Programming Language
- Scala Building Tool (SBT)
- ScalaCheck
- ScalaTest
- Spray Framework
- SBT Revolver
Requirements: sbt (version >0.13.0), JDK 1.8.
To compile and test, execute
sbt test
To run the visualizer, execute
sbt "runMain ucl.scenario.geometry.runners.ArtGalleryPainter filepath"
where filepath points to a test file, e.g.,
sbt "runMain ucl.scenario.geometry.runners.ArtGalleryPainter ./src/test/resources/testdata/lshaped.agp"
If the set of guards (blue dots) doesn't cover the whole gallery with their visibility areas (yellow), a counterexample position will be located (red dot).
Check ucl.scenario.geometry.ArtGalleryPainter object for details.
The files are formatted as follows:
comma-separated list of polygon vertices in a counter-clockwise order
###
comma-separated list of guards
In the counter-clockwise order the polygon stays on the left while walking its the boundary. For instance:
(0, 0), (5, 0), (5, 2), (4, 1), (1, 1), (0, 2)
###
(0, 2), (5, 2)
The following extended format allows to input the auxiliary triangulation:
(0, 0), (5, 0), (5, 2), (4, 1), (1, 1), (0, 2)
###
(0, 2), (5, 2)
###
true
More examples can be found in ./src/test/resources/testdata/.
To run the server with the simple test scenario project locally (located in ./instances/test), run the following command from terminal:
sbt "runMain ucl.scenario.server.Boot ./instances/test"
You can change some parameters of the scenario (e.g., host address or port) by modifying the config file in the root
of the folder instance, passed as an argument to Boot.
To check the stub page, navigate to http://127.0.0.1:8083 (or the host you put in the config file).
You can add your email address by changing some of the emails files of the test instances. For example, you can add
your email into ./instances/test/teams/albatros, therefore getting all notifications for the albatros team to your
email address.
You can find some examples of good and bad solutions for different teams for this specific test scenario instance
in the folders ./resources/test_scenarios/test/solutions.
All necessary instances of the scenario are already create, but if you want to create a new one, run
sbt "runMain ucl.scenario.util.SetupScenario <filepath> <scnearioname>"
where filepath will be the root folder of your scenario, for instance
sbt "runMain ucl.scenario.util.SetupScenario ./instances myscenario"
This will create team accounts, default task files and confing file.
In order to generate series of different random polygons, run one of the following scripts:
For rectilinear polygons:
sbt "runMain ucl.scenario.geometry.runners.RectilinearPolygonGenerator"
For triangular-like polygons:
sbt "runMain ucl.scenario.geometry.runners.TriangularPolygonGenerator"
For quasi-convex polygons:
sbt "runMain ucl.scenario.geometry.runners.QuasiConvexPolygonGenerator"
For totally random polygons:
sbt "runMain ucl.scenario.geometry.runners.CrazyPolygonGenerator"
You can also run them in the form
sbt "runMain ucl.scenario.geometry.runners.X path num"
Where X is the corresponding class name (one of the four above), path is the desired output file path and
num is a number of polygons generated. If path is absent, the default file with extension
.pol will be put to the project root folder.
Use the visualiser described above in order to render polygons.
Run from the command line:
sbt "runMain ucl.scenario.geometry.runners.CheckVisibility inputPath"
where inputPath is a path to your file with solutions to the Guards problem, formated as follows:
polygon_number: polygon_vertices ; guards
For instance, you can try it on the problem file from Part 2 as follows:
sbt "runMain ucl.scenario.geometry.runners.CheckVisibility ./resources/tasks/check/check.pol"