How to Find Best Position for A Label in Irregular Shape?

rayq

Hi, does anyone know a way to find the best position for a label in an irregular shape? For example, a lake is in a L shape with ~50 points and I want to post its name in the middle inside the lake, I can't post it in the mid point of the range since it will be outside the lake in such L shape, so how to estimate/calculate the best possible position? If you have experience doing so or know where to get the info of how to doing it, please let me know. Any help will be greatly appreciated. Thanks.

Raymond

XLoom

What points do you mean? Do you mean pixels as in raster graphics or points as vertices in vector graphics? There is always possibility to convert the vector graphics to raster graphics, so I'll give you one simple, but algorithmically complex solution (it can be optimized) with raster graphics.

When you have a bitmap with a lake on it. Lets say the lake is drawn with black pixels and all other parts of map with white pixels. Obviously the best place for label is where it lays mostly on black pixels. How to get it? The solution is to find for each position on map, how many black pixels will be under the label if the label is drawn starting from that position and choose the position with highest value. Just count the black pixels that are under label while it's drawn. That's about it It can be optimized a lot as this solution is slow with complexity X*Y*Z*W where X and Y are map dimensions and Z and W are the size of label. If you think of the label as a rectangle, then you can move it by scanlines, so the complexity is only about X*Y.

rayq

[b][red]This message was edited by rayq at 2006-6-6 13:3:0[/red][/b][hr]
[b][red]This message was edited by rayq at 2006-6-6 13:2:11[/red][/b][hr]
No, I meant a single entity, for example, a irregular shaped polygon with 50 vertices in vector graphics. I was given a project to find the best/optimal point for its label placement. If the shape is a circle, rectangle, or equal sided polygon, the best position for its label is the mid point. For irregular shape, which is the best??? Better yet, the angle (tilted upward/downward) of the label can somewhat follow the shape. I think the algorithm (if found) can be used with regular/irregular shape!


Thanks for your input.

: What points do you mean? Do you mean pixels as in raster graphics or points as vertices in vector graphics? There is always possibility to convert the vector graphics to raster graphics, so I'll give you one simple, but algorithmically complex solution (it can be optimized) with raster graphics.
:
: When you have a bitmap with a lake on it. Lets say the lake is drawn with black pixels and all other parts of map with white pixels. Obviously the best place for label is where it lays mostly on black pixels. How to get it? The solution is to find for each position on map, how many black pixels will be under the label if the label is drawn starting from that position and choose the position with highest value. Just count the black pixels that are under label while it's drawn. That's about it It can be optimized a lot as this solution is slow with complexity X*Y*Z*W where X and Y are map dimensions and Z and W are the size of label. If you think of the label as a rectangle, then you can move it by scanlines, so the complexity is only about X*Y.
:
:
:
:

XLoom

With the extension of tilted labels it becomes very a difficult problem. The easiest thing would still be to create a rasterized picture and have a rectangular label. If you don't want to do that, then your best bet might be to first triangulate the shape, then try to fit in the label the label on the triangles somehow. I don't really know any specific algorithm for it. Things that popped into mind that you might want to try after triangulation are:
1) for each triangle put the label to the center of the triangle at the angle that the triangles outer side is (ie the side that is original vertex in the shape) and find out how much of the label is inside the triangles, then choose the triangle where the label is most inside this triangle and other triangles it intersects.
or
2) for each two triangles draw a straight between centers of two triangles and put the label on the straight at half way between the two triangles, then again choose the label that is best inside the triangles.

It might give quite nice outcome, if the lakes are simple polygons that do not have very jagged edges.

The easiest algorithm for triangulation is probably ear cutting:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html

: No, I meant a single entity, for example, a irregular shaped polygon with 50 vertices in vector graphics. I was given a project to find the best/optimal point for its label placement. If the shape is a circle, rectangle, or equal sided polygon, the best position for its label is the mid point. For irregular shape, which is the best??? Better yet, the angle (tilted upward/downward) of the label can somewhat follow the shape. I think the algorithm (if found) can be used with regular/irregular shape!

rayq

I'll try the rasterized method that you mentioned. Yes, you are right about the angular text. I might just keep it simple as rectangular label. Thanks a lot for your help.

Ray

: With the extension of tilted labels it becomes very a difficult problem. The easiest thing would still be to create a rasterized picture and have a rectangular label. If you don't want to do that, then your best bet might be to first triangulate the shape, then try to fit in the label the label on the triangles somehow. I don't really know any specific algorithm for it. Things that popped into mind that you might want to try after triangulation are:
: 1) for each triangle put the label to the center of the triangle at the angle that the triangles outer side is (ie the side that is original vertex in the shape) and find out how much of the label is inside the triangles, then choose the triangle where the label is most inside this triangle and other triangles it intersects.
: or
: 2) for each two triangles draw a straight between centers of two triangles and put the label on the straight at half way between the two triangles, then again choose the label that is best inside the triangles.
:
: It might give quite nice outcome, if the lakes are simple polygons that do not have very jagged edges.
:
: The easiest algorithm for triangulation is probably ear cutting:
: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html
: