Fast 2D signed distance

Question

I need a way to compute the distance beetween a point and the bounding edge of a polygon.

• If the point is outside the polygon, the distance will be posivite
• If the point is inside the polygon, the distance will be negative

This is called SDF for Signed Distance Field/Function

The polygon itself is composed of multiple paths, can be concave, with holes, but not self intersecting, and with a lot of clockwise ordered points (10000+).

I've found some existing solutions, but they require to test the point against each polygon edge, which is not efficient enough.

Here is the visual result produced (green is positive, red is negative):

So I've tried the following:

Put the polygon edges in a quadtree

To compute the distance, find the closest edge to the point and change the sign depending on which side of the edge the point is.

Sadly, it doesn't works when the point is at the same distance of multiple edges, such as corners.

I've tried adding condition so a point is outside the polygon if it's on the exterior side of all the edges, but it doesn't solve the interior problem, and the other way around.

Can't wrap my head around it...

If anyone curious, the idea is to later use some shader to produce images like this :

EDIT

To clarify, here is a close up of the problem arising at corners :

• For all the points in area A, the closest segment is S1, so no problem
• For all the points in area E, the closest segment is S2, so no problem either
• All points in area B, C and D are at the same distance of S1 and S2
  • Points in area B are on the exterior side of S1 and interior side of S2
  • Points in area D are on the interior side of S1 and exterior side of S2
  • Points in area C are on the exterior side of both segments

One might think that a point has to be on the interior side of both segments in order to be considered "in". It solves the problem for angles < 180°, but the problem is mirrored for angles > 180°

Worst, two or more corners can share the same position (like the four way corner in the low part of first image)...

Answer 1

For closed, non-intersecting and well oriented polygons, you can speed up the calculation of a signed distance field by limiting the work to feature extrusions based on this paper.

The closest point to a line lies within the edge extrusion as you have shown in your image (regions A and E). The closest feature for the points in B, C and D are not the edges but the vertex.

The algorithm is:

• for each edge and vertex construct negative and positive extrusions
• for each point, determine which extrusions they are in and find the smallest magnitude distance of the correct sign.

The work is reduced to a point-in-polygon test and distance calculations to lines and points. For reduced work, you can consider limited extrusions of the same size to define a thin shell where distance values are calculated. This seems the desired functionality for your halo shading example.

While you still have to iterate over all features, both extrusion types are always convex so you can have early exits from quad trees, half-plane tests and other optimisations, especially with limited extrusion distances.

The extrusions of edges are rectangles in the surface normal direction (negative normal for interior distances).

From 1:

The extrusions for vertices are wedges whose sides are the normals of the edges that meet at that vertex. Vertices have either positive or negative extrusions depending on the angle between the edges. Flat vertices will have no extrusions as the space is covered by the edge extrusions.

From 1:

Answer 2

I hope this solves your problem.

This is implemented in Python.

First, we use imageio to import the image as an array. We need to use a modified version of your image (I filled the interior region in white).

Then, we transform the RGBA matrix into a binary matrix with a 0 contour defining your interface (phi in the code snippet)

Here's phi from the snippet below (interior region value = +0.5, exterior region value = -0.5):

import imageio
import numpy as np
import matplotlib.pyplot as plt
import skfmm

# Load image
im = imageio.imread("0WmVI_filled.png")
ima = np.array(im)

# Differentiate the inside / outside region
phi = np.int64(np.any(ima[:, :, :3], axis = 2))
# The array will go from - 1 to 0. Add 0.5(arbitrary) so there 's a 0 contour.
phi = np.where(phi, 0, -1) + 0.5

# Show phi
plt.imshow(phi)
plt.xticks([])
plt.yticks([])
plt.colorbar()
plt.show()

# Compute signed distance
# dx = cell(pixel) size
sd = skfmm.distance(phi, dx = 1)

# Plot results
plt.imshow(sd)
plt.colorbar()
plt.show()

Finally, we use the scikit-fmm module to compute the signed distance.

Here's the resulting signed distance field: