[SoC] QGIS label placement, week 3

[Martin Dobias]

Hi Wolf

On Mon, Jun 15, 2009 at 9:36 AM, Wolf
Bergenheim<wolf+grass at bergenheim.net> wrote:
> On Sat, Jun 13, 2009 at 03:01, Martin Dobias<wonder.sk at gmail.com> wrote:
>> Hi all,
>>
>> my report about the progress is available here:
>> http://www.qgis.org/wiki/Label_Placement_GSoC_2009
>
> That was an interesting read! :) If I remember correctly the PAL
> algorithm splits concave polygons into multiple convex polygons and
> then tries to place as many labels inside these convex polygons. Does
> your dataset consist of a lot of concave polygons? Centroid placement
> should not take a lot of time with convex polygons...
>
> Looking forward to seeing how this develops... Perhaps a more improved
> algorithm for concave polygon splitting needs to be found?

PAL splits concave polygons into convex ones, but that happens only
with the more advanced methods of generating label candidates. I've
been using placement around centroid for my tests. The splitGeom()
function actually only checks whether polygon's outer ring is not
self-intersecting. It seems that formerly this function also used to
split such polygons, but that code is commented out and invalid
polygons are just ignored. The check itself consits of doing a convex
hull followed by n^2 checks of intersection of segments. I guess the
self-intersection check in geos has better performance...

I'll be checking the other methods (horizontal, free) that split the
polygons later, stay tuned :)

Bye
Martin