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

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: