Version 22 (modified by 11 years ago) ( diff ) | ,
---|
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:
- Porting the Voronoi classes from JTS to GEOS: Providing the functionality of constructing Voronoi diagrams to GEOS by porting it from JTS to GEOS.
- 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.
- 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.
- 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:
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 nest week
- Port the classes, triangulate::ConstraintSplitPointFinder and triangulate::NonEncroachingSplitPointFinder.
- Write test cases for the same.