Google Summer of Code 2013

Student Name
Vishal Tiwari

Mentor Name
strk

Project Title: Adding Voronoi Diagram to GEOS

Project Aim
The aim of the project is as follows:

1. Porting the Voronoi classes from JTS to GEOS: Providing the functionality of constructing Voronoi diagrams to GEOS by porting it from JTS to GEOS.

2. Writing C++ test cases: This will include porting the Voronoi Test file from JTS to GEOS. Furthermore one or two test cases will be written from scratch.

3. Exposing the functions through C-API: It provides a wrapper for the C++ functions. All the reference functions are implemented in geos_ts_c.cpp. (These are the thread safe apis). These functions are also exposed via the non-thread apis that are implemented in geos_c.cpp file. Such wrapper will be provided for the functions/methods that will be ported for Voronoi Class.

4. Writing C test cases: Test cases to test the Voronoi class methods wrapper functions written in geos_ts_c.cpp and geos_c.cpp will be written to test all the methods exposed via the apis.

Week 1 Report

1. Work Done :

• Have ported the methods that are in geos/triangualte/quadedge/QuadEdgeSubdivion.cpp. The methods are as such:
  • getVoronoiDiagram : Gets the cells in the Voronoi diagram for a triangulation.
  • getVoronoiCellPolygons : Gets the polygons for the Voronoi Cells for a triangulation.
  • getVoronoiCellPolygon : Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
  • getVertexUniqueEdges : Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in the subdivision. The frame vertices can be included if required.
• Class TriangleCircumcentreVisitor was also ported.
• More methods like geos::geom::Triangle::circumcentre, and geos::geom::closeRing that were required in the above functions were also ported.

2. Problem Faced :

• I am having some silly problems during compilation which i am working out with strk, it will be solved soon.

3. Work to be done in the next week :

• Solve the errors that are coming as of now.
• Port the classes left, and see the working of the methods ported.
• Start with the port of class VoronoiDiagramBuilder.

Week 2 Report

1. Work Done:

• I have fixed the problems that i was facing the previous week.
• I have ported all the methods and classes that are required for VoronoiDiagramBuilder.
• I have started the port of VoronoiDiagramBuilder class.

2. Problems Faced :

• During the port of one of the methods i was stuck with some C++ STL data structure, which required a different compiler, but it was solved, as i used a different STL data structure.

3. Work to be done in the next week:

• Finish the port of VoronoiDiagramBuilder class.
• Write the testcases for QuadEdgeSubdivision class, and related methods that i have ported earlier.

Week 3 Report

1. Work Done:

• Came across with some more methods related to VoronoiDiagram in other class and also ported them.
• Completed the port of VoronoiDiagramBuilder.

2. Problems Faced :

• No problems faced as such.

3. Work to be done in the next week:

• Write C++ testcases for QuadEdgeSubdivision class and VoronoiDiagramBuilder class.

Week 4 Report

1. Work Done:

• Tested some methods in geom::Triangle and geom::CoordinateList that were ported and also tested some methods of VoronoiBuilder class.
• A lot of time was spend in fixing bugs and memory leaks.

2. Problems Faced:

• As its a port from java to C++, we have to take care for memory leaks. Also i am stuck in a comparison between two QuadEdge objects, which i am working out with strk.

3. Work to be done in the next week:

• Deal with the problem i am facing and write test cases for the remaining methods.

Week 5 Report

1. Work Done:

• This week was spent mainly, in fixing the memory leaks and segmentation faults. I have tested all the methods and classes that have been ported. Everything seems to be working fine. Thus completion of the Voronoi port via C++ interface.

2. Problems Faced:

• No problems other than memory leaks and seg faults.

3. Work to be done in the next week:

• Check for bugs because of the coming evaluation.
• I will look into, how the C-api of geos has been implemented.

Week 6 Report

1. Work Done:

• Made cleaned subsets of the work done so far so as for better peer reviewing.
• The work i didn't include a particular fix, due to which i was getting memory leaks, so i was stuck in that for a while, which was later fixed.
• Started to look into how the C-interface has been implemented.

2. Problems Faced::

• I had some problems in making subsets in git, but eventually got it. :)

3. Work to be done in the next week:

• Expose the C++ apis through the C wrapper interface.

Week 7 Report:

1. Work Done:

• Exposed the Voronoi Diagram Builder C++ apis through C wrapper interface for the thread safe apis. Also expose it via non-thread safe apis, which is a simple wrapper around the thread-safe apis.

2. Problems Faced:

• I tried to test it, but whenever i try to link my file against the libgeos_c.so, I get some errors, which will be resolved soon.

3. Work to be done in the next week:

• Resolve the linkage error and test the C-Api wrapper for Voronoi Diagram Builder and write corresponding test cases.

Week 8 Report

1. Work Done:

• Resolved the linkage error that was coming before.
• Tested the c-api wrapper for Voronoi Diagram and also added test cases the same. Thus completing the part that was proposed in the GSoC Proposal.

2. Problems Faced:

• None.

3. Work to be done in the coming weeks:

• I will be testing a little bit more and would work on cleaning the code.
• As the proposed work is done, I would start on something new. I will work on the port for Conforming Delaunay Triangulation for which I would first figure out the classes and methods required for the port.

Week 9 Report

1. Work Done:

• Made a local release that includes the functionality that have been added so far.
• Tested the c++ apis as wells as c-apis against difference tolerance values.
• Looked into the various methods in JTS required for the port of ConformingDelaunayTriangulationBuilder.

2. Problems Faced:

• None

3. Work to be done in the comming week:

• Port methods required for ConformingDelaunayTriangulationBuilder class.

Week 10 Report

1. Work Done:

• Figured out the classes and methods required to port ConformingDelaunayTriangulationBuilder class. Main classes are as follows:
  -- index::KdTree.
  -- index::KdNode.
  -- triangulate::ContraintVertex
  -- triangulate::ConstraintSplitPointFinder
  -- triangulate::NonEncroachingSplitPointFinder

• Ported the functionality for making a Kdtree and doing insert, and query operations.
• Had to make a new branch for QuadEdgeSubdivision(required for Voronoi) because the previous one was unable to rebase to the svn-trunk. strk has made some comments, which i will be working on in the next week.

2. Problems Faced:

• None.

3. Work to be done in the comming week:

• Ported the remaining classes mentioned above.
• Write Test cases for kdtree classes, which have been ported.

Week 11:

1. Work Done:

• Tested KdNode and KdTree and wrote their test cases.
• Ported the class triangulate::ContraintVertex.

2. Problems Faced:

• None.

3. Work to be done in the next week

• Port the classes, triangulate::ConstraintSplitPointFinder and triangulate::NonEncroachingSplitPointFinder.
• Write test cases for the same.

Week 12:

1. Work Done:

• Ported the following classes:
  

-- triangulate::Segment
-- triangulate::splitSegment
-- NonEncroachingSplitPointFinder
-- ConstraintSplitPointFinder
-- (method)geom::LineSegment::getCoordinate()

• Worked out a number of problems with strk such as memory leaks in the triangulate::quadedge::QuadEdgeSubdivision class which is required for Voronoi Diagram Builder.

2. Problems Faced:

• Had some problems in fixing the memory leaks.

3. Work to be done in the next week

• Test VoronoiDiagramBuilder for memory leaks.
• Make documentation.

Week 13

1. Work done:

• This week I spent my time in fixing memory leaks for Voronoi class. Finally with the help of strk, we have integrated it with the main trunk.
• It also contains the C-API interface along with some test cases.

2. Problems faced:

• Had some issues with the memory leaks.

3. Work to be done in the next week:

• Make documentation.