Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-12 15:27:27

Hi Thomas,
>
> I get a "You do not have the required role." Can you make your proposal
> public, so that also non-mentors can view it? Well, on the other hand, I
> shouldn't spend too much time into this, so it's probably good that I can't
> see it.

It seems to me that I am not able to make it public, that's why I'll add it
to this message.
Personal Details

   - Name: Andrii Sydorchuk
   - College/University: Kyiv Taras Schevchenko National Universtiy
   - Course/Major: Cybernetics/Applied Mathematics
   - Degree Program (BS, MS, PhD, etc.): Master
   - Email: sydorchuk.andriy_at_[hidden]
   - Homepage: -
   - Availability:
   I plan to spend 6-8 hours per day (more if required).
   I've already started (reading articles), 20th of August.
   I don't think that any of this factors with affect my availability.

Background Information

Educational background: I've earned Bachelors Degree in Applied Mathematics
(GPA 4.95). At the moment I am on the first course of my Master's program in
Applied Mathematics. Courses taken: Algebra and Geometry, Mathematical
Analysis, Discrete Mathematics, Programming, Differential Equations, Numeric
Methods, Mathematical Logic and Algorithms Theory, Mathematica Modeling,
etc.

Programming background: 1) January 2010 - April 2010 - Google Company,
Software Engineer Intern (Zurich, Switzerland).     Responsible for managing
workflow pipelines.

                                               2) April 2009 - December 2009
- Scopicsoftware Company, C++ Algorithm Software Developer. Responsible
 for 2D/3D applications development.

Programming interests: Algorithms, Data Structures, Computational Geometry;

                                        Software competitions:

                                           2010 - Internal Google Code Jam
2010 - 7th place.

                                           2009 - All Ukrainian Collegiate
Programming Contest 2009 - 3d diploma.

                                           2008 - Advanced to Google Code
Jam 2008 semifinal (London).

                                       Languages, technologies and tools:
C++, C#, Python, STL, MFC, Qt, OpenGL;

                                      3D rendering;

Interest in contribution to the Boost C++ libraries: become more familiar
with Boost libraries;

                                                                       make
contribution to the library used by lots of people;

Interest in the project: I am interested in algorithms, data structures,
analytical geometry. And all of them are included as part of  Sweepline
project. But the main idea is to become more familiar with Boost library
(not only part I'll work on).

Previous work in this area (Scopicsoftware): 1) Making improvement to the
algorithm of finding center lines of standard fonts, however   this project
used wave algorithm approach.

                                                              2) Developing
3D CAD system for creating office cubicles. Implementation of Collada[1] 3D

  models importer. Adding support of YafaRay raytracing engine[2].
Development and
                    improvement of algorithms for cubicles clustering and
objects arrangement.

Plans beyond Summer of Code: 1) continue implementation of computational
geometry algorithms in Boost.

                                              2) become more familiar with
other parts of Boost library and work on them also.

C++ (4.2)

C++ Standard Library (4.3)

Boost C++ Library (0.0, starting to learn)

Subversion (2.0, only SVN)

Software development environments: Visual Studio, emacs.

Documentation tool: I haven't used any of them (will study one of them
during April - May).

Project Proposal

Implement generic and robust sweepline algorithm for solving 2D Voronoi
diagram and Delaunay triangulation problems.

I will also implement Sweep Line algorithm visualization tool using OpenGL.
This will slightly help during testing. Basically it will visualize all the
execution process: site events, circle events, adding new sites to the beach
line, removing sites and so on.

During last month I'll implement benchmark tests. It is also a good idea to
start with writing tests and add new cases during development.

Basically implementation of sweepline requires next data structures:

            1) Event queue (priority queue). We can split site events and
circle events into two data structures[3]:

                            a) site events may be stored in stl vector.
Which will be sorted after reading input data. Complexity     of sorting
                                        n*log(n), where n - is number of
input sites.

                            b) circle events may be stored in stl
priority_queue. Adding new element, lookup, deletion will require     log(n)
time,                                       where n is number of elements in
the priority queue.

            2) Sweepline (self-balanced binary tree). For sweepline it is
good choice to use wrapper class (adapter pattern) of stl map or set. It
                is better to use map, because we can split keys and
associated data (storing whatever our problem requires).  For elements we
                  can     choose bisectores of two neihbour sites[4]. We
will also need to define robust key comparer[5], as there might be
                  precision problems.

            3) Output data structures (half edges, double linked lists,
etc.). I'll do further research in this area.

Next degeneracies will require careful handling:

            1) 2 or more events on a common vertical line;

            2) event points coincide, e.g. 4 or more co-circular points;

            3) a site coincides with event;

Proposed Milestones and Schedule

Present - end of May: design basic architecture, write test cases, read
articles connected with the topic, learn Boost;

start of June - mid of July: finish Voronoi and Delaunay triangulation
implementation;

mid of July - 20th of August: improve logic, make refactoring, work on
performance, testing, finishing documentation, benchmark tests.

*References*

[1] - http://code.google.com/p/opencollada/

[2] - http://www.yafaray.org/

[3] - Kenny Wong, Hausi A. Muller. An Efficient Implementation of Fortune's
Plane-Sweep Algorithm for Voronoi Diagrams.

[4] - Mark de Berg. Computational Geometry: Algorithms and Applicatoins.
Page.156.

[5] - Ruud, B. Building a Mutable Set, 2003