Re: [boost] [GSoC] Boost.Polygon edge, polyline and edge set concepts

Subject: Re: [boost] [GSoC] Boost.Polygon edge, polyline and edge set concepts
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-03-24 12:24:03

monish gupta wrote:
> Hello community
> 
> I want work on project : Boost.Polygon edge, polyline and edge set
> concepts. Could anyone provide me some weblinks to learn about
> polyline and edge set algorithms?

Monish,

If you look at the documentation for polygon you will see polygon set operations are the primary feature of the library.  These operations include booleans (polygon clipping), resizing (grow, shrink), connectivity extraction and are generalized by the map overlay operation.

The edge set operations are the exact same operations, but working on edges instead of polygons.  Those may be edges of polygons, or polylines or just individual edges.  Booleans on edge sets would merge partially overlapping edges (union) or clip partially overlapping edges to the overlap (intersection).  What is primarily needed to implement this is a line segment intersection algorithm such as Bentley-Ottmann http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm.  I already have line segment intersection implemented because it is needed for the polygon set operations, so this proposed project would expose that algorithm and use it to implement the edge set operations, providing concept based generic interfaces for objects that model new edge, polyline and edge set concepts to be used with the algorithms.  There are many other edge related algorithms already implemented in the library, such as a robust test for whether two edges intersect, as well as many others that could be implemented as part of the project.

Regards,
Luke