CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Bellini wrote:
>  Hello Sebastien...
>
>    I'm trying to fill a (maybe concave) polygon using a set of vectors with 
> the
> same direction; it's like a raster flood fill but done with vectors...
>
> I'll use it, for example, for fill glyphs of a truetype font using a plotter
> (not a printer) as output device.
>
>   thanks for your interest
>
>              Giampaolo
I assume your polygon is simple.

A simple solution (but maybe not the most efficient one) is to use the 
following strategy.

Consider your polygon as a set of segments, and consider a set of lines
defining the "hatching lines". For each line, compute the intersection 
between the set of segments using a sweep line algorithm. For each line,
you always have an even number of points to connect together to have
your internal segments.

For this you can use the function compute_intersection_points documented 
here:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2_ref/Function_compute_intersection_points.html#Index_anchor_1549

and using the traits class Arr_linear_traits_2 (used to get Curve_2
type)
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Arrangement_on_surface_2_ref/Class_Arr_linear_traits_2.html#Cross_link_anchor_1213

Points will be reported in an increasing xy-lexicographical order, so
you can directly "linked" them by pair.
The boolean report_endpoints should be set to false.

An example is presented here:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2/Chapter_main.html

If your polygon is convex, you can directly compute the intersection 
between all the segments and all the lines.
Have a look here to see how to get a decomposition of your polygon in 
convex regions (if you use this you will have extra points in the 
interior of the polygon):
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Partition_2/Chapter_main.html

Notice that in the case a line go through a segment endpoint you have to
tweak a bit.


S.