Course project for INF562 - Computational Geometry from Theory to Applications (2019-2020), École Polytechnique
Martín Cepeda & Cédric Javault
Given a point cloud S of n 2D vertices, we implement two greedy approaches in order to approximate the MINimum Area simple Polygonalization and MAXimum Area simple Polygonalization of S (MINAP and MAXAP respectively), an NP-hard problem (Fekete, 2000). These two iterative approaches are based in the insertion of minimum area triangles at each step.
This problem was given at the CG:SHOP 2019 Competition a year earlier.
- Java 1.8
- core.jar (Processing 1.5.1 library, for 2D rendering of polygons and point clouds)
- TC.jar (for dealing with I/O operations on text files, developed for INF361) doc
- Jcg.jar (Java library for computational geometry, developed for INF562 by Luca Castelli Aleardi) doc
AreaOptimizer input_file_path saves minumum/maximum area polygon found
AreaOptimizer input_file_path solution_file_path shows saved solution and score S=areaPolygon/areaConvexHull