# Algorithm for icon placement on polygons

This algorithm finds a point for placement of an icon (or a label) which is guaranteed to be inside of a polygon and somewhere towards the center of the figure.

As input the algorithm only requires the vertices as an ordered list.

## Step 1: Find points halfway inside the polygon Figure 1: Explanatory figure for step 1

For every vertex we find a point halfway inside the polygon.

### Step 1.1: Find angle

First we find a angle between vertex-1 and vertex+1 through vertex. We then imagine a line through vertex along the half-point of this angle. Implemented using atan2 this is done as follows:

``````from = vertex-1
through = vertex
to = vertex+1

from_x = from_x - through_x
from_y = from_y - through_y

to_x = to_x - through_x
to_y = to_y - through_y

from_angle = atan2(from_y, from_x)+pi
to_angle = atan2(to_y, to_x)+pi

angle = min(from_angle, to_angle) + ( max(from_angle, to_angle) - min(from_angle, to_angle) )/2
``````

### Step 1.2: Linepoint

We then create an imaginary point "linepoint" along this line, so that we have two coordinate pairs to work with when finding intersections. This can be done with x = x + cos(angle), y = y + sin(angle).

``````a = 180 - vertex_x
b = a * tan(angle)

linepoint_x = vertex_x + a
linepoint_y = vertex_y + b
``````

### Step 1.3: Find intersections with edges

The next step is then to find all intersections between the line vertex-linepoint and the edges of the polygon. We need to have a total count of intersections in at least one direction from vertex to determine which way points towards the inside of the polygon (ray-casting point in polygon algorithm). We also need the closest edge in that direction.

To handle polygons with holes we just include the hole-polygons in the list of edges we check against.

In psuedocode:

``````foreach E in edges and hole_polygon_edges
skip if E_from == vertex or E_to == vertex

skip unless intersection = find_intersection(vertex-linepoint, E_from-E_to)

skip unless point_on_segment(intersection, E_from-E_to)

distance = distance(vertex, intersection)

if point_on_segment(intersection, vertex-linepoint)
intersectioncount++
if distance < nearestOn_distance
nearestOn = intersection
else
if distance < nearestOff_distance
nearestOff = intersection
``````

### Step 1.4: Find point

Now we can finally calculate the point by taking the nearest intersection point in the right direction (looking at intersectioncount to find out which direction) and getting the point halfway between vertex and the intersection.

In psuedocode:

``````if intersectioncount % 2 == 0
point = nearestOff
else
point = nearestOn

point_x = vertex_x + (point_x - vertex_x)/2
point_y = vertex_y + (point_y - vertex_y)/2
``````

## Step 2: Get centerpoint

Now we use the points halfway inside the polygons to find a point to place the icon.

This part of the algorithm could do with some work, I have ideas for several approaches that should be tested on various polygons to find the best one.

Some random ideas:

• 14:31 < SpeedEvil> I think just 'don't place on a point where the points line is under 30% of the max' is probably reasonable.
• When calculating points we have the distance between intersectionpoint and vertex. Perhaps this could somehow be used to detect polygons with several big parts and this "bridges" between them?
• A simple yet good approach seems to be finding a simple average of x and y coordinates and then finding the closest point. In psuedocode:

``````avg_x = avg(points_x)
avg_y = avg(points_y)

sort p by distance to avg_x,avg_y

place icon at p
``````