6
\$\begingroup\$

I have a map of the world and I want to place text on top of each country. The text can be anywhere from 0 to 1000 symbols long, and can often be changed.

I'm looking for an algorithm to layout text on top of each country "nicely":

  • Text ideally should not go outside of the country borders
  • Placed somewhere near poloygon's centroid
  • Should be visible when possible

I can change font size, and I can split it into multiple lines.

Currently I'm using naive centroid approach, but it requires lots of manual tweaking, and with changing text it can result in suboptimal placement:

enter image description here

Interactive version of the USA map is available here: http://what-people-google.anvaka.com/ (so that you can see labels placement drawbacks and better understand my use case).

One solution I had in mind was to approximate each country by largest posible axis aligned rectangle that can be embedded inside country shape. But maybe there is a better way to do it?

\$\endgroup\$
3
  • \$\begingroup\$ Is this related to HTML? Add a tag. How sad that I'm not familiar with the web programming so much, otherwise I would help you. \$\endgroup\$
    – Ocelot
    Oct 20, 2016 at 17:50
  • \$\begingroup\$ @Ocelot I'm looking for a generic algorithm, not necessary bound to a rendering technology. \$\endgroup\$
    – Anvaka
    Oct 20, 2016 at 17:52
  • 2
    \$\begingroup\$ Interesting. I know you aren't looking for an implementation-specific idea, but I'm curious if Google's API provides some sort of geometry map for the states and countries. I do think that the largest rectangle is probably your best bet, then you can resize text to fit within those bounds, obviously with great variation on size of text and completeness of most popular query text. It may, if you have such geometry data, be wise to find a geometric center, then increase the rectangle size until it's no longer bound, then back off and use that. Maybe have a baseline size and increase/decrease \$\endgroup\$ Oct 20, 2016 at 18:06

1 Answer 1

2
\$\begingroup\$

I would do the following (there may be a better algorithm for this):

  1. Split each string (country name) into words
  2. Create a polygon for each country's outline (Can simplify this polygon fairly aggressively)
  3. Given a starting font size, start at the top of the polygon, split the height of the polygon into the font's height * 2 rows and measure how wide each row is.
  4. Starting at the center row, find how many words you can fit into that row.
    If you have to wrap, move up one row and break at that line, and continue trying on the line below.
  5. If you have exausted all rows, shrink the font and go back to step 3
  6. If you still cannot fit all rows at a lower bound font size, then treat the shape as a rectangle and just stretch it vertically until everything fits. (Maybe try something else here, I would look at each item on a case by case basis; you can also just hide at this point)
  7. When drawing, make sure to center each line in its row
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .