How to avoid overposting (overlapping) labels?

I have to display a multitude of labels on-screen without overlap. The label positions should be as close as possible to the features they describe. The features may be points, lines, or polygons on-screen (imagine any variety of map). I have to satisfy the following requirements in my application:

• labels must be positioned to avoid overposting (overlap) with other labels
• labels must be positioned to avoid overlapping with other features (polygons and line segments)
• optimum position for a label is above and to the right of the feature they describe
• below and to the right is less acceptable
• least acceptable positions are to the left

I need to come up with a method for doing this.

Before I just start attempting to do this at random, I am hoping someone here may have already done this and be able to give me some advice as to where to start.

Basically, with the labels, I could use bounding boxes to compare them to each other. Although I don't know a good way to do this. With the line segments and polygons onscreen that they are labeling, I really don't have a clue what I should do to avoid overlap. I am hoping it won't require much more effort on top of开发者_JS百科 avoiding the overlap of the labels themselves.

I think repulsion would work if I only had to deal with labels overlapping other labels. But if I have a line segment drawn across half the screen, I don't know how I can avoid overlap with that using the repulsion technique.

The language I am using is Actionscript 3 and the Flex framework. I don't believe Flex has any layout manager classes like there are in Java Spring that can do this work for me.

Anyway, links or suggestions would be welcome. I can allow for some brute force; I don't see how I can accomplish this otherwise. Thank you!

PS I believe the technical term for this problem is "overposting".

I don't see any way to accomplish this without having a reference to all the labels and the other shapes / lines you need to avoid. Assuming you have those references, just tie into the Flex Framework methods.

In updateDisplayList() loop over your labels; and position them in conjunction with to everything else on screen. You can use the getExplicitOrMeasuredWidth() and getExplicitOrMeasuredHeight() methods to determine the space needed for the item in question.

If you use a built in Flex Container, such as a VBox or HBox the labels and other lines will be positioned in accordance to each other. Or, if you're using Spark a VGroup or HGroup will offer the same functionality.