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)...

Farmland

Take a look at Adaptively Sampled Distance Fields. I seem to recall that one of their papers included sample source code for their octree implementation. – Astereognosis

That is not a polygon!! – Levelheaded

@JerryHalisberry a set of polygonal paths ? – Farmland

Is the hole in counterclockwise order? – Ellison

@DavidEisenstat yes ! – Farmland

What do you need? A way of colouring each pixel of the whole image (not just the polygon) depending of its signed distance? Just a flood-fill algo to colour the inner part of the polygon? What kind of primitives you use in the shader? – Courlan

@Courlan The SDF is used to generate a texture atlas (a set of tiles) containing only the signed distance. Then a set of quads is rendered with a shader using that texture to produce the final result. It's a lot like sdf font rendering (aras-p.info/blog/2017/02/15/…). Problem is the texture generation is horribly slow (1st picture) or 100x faster but buggy (2nd picture). – Farmland

OK. I think your quadtree is the way to go. You say you found issues on corners. It shouldn't be so (review your code). Perhaps if you break a line such that each piece fits inside an only quad in the tree, then you may avoid wrong closest-edge. – Courlan

I think you should use distance to a segment not just distance (perpendicular) to a line. So, on corners the distance is to the corner point, not to its lines. The sign of this distance is positive because the perpendicular to lines lies out of segments. – Courlan

In opencv, there's this pointPolygonTest function. – Transvestite

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:

Kimbrakimbrell

Thanks Robin. It doesn't really address my problem : the floor I'm trying to represent is huge (1 km² industrial complex with fairly detailed resolution) so I don't have the luxury to render it full size and do some marching algorithm on it. It will be tiled and rendered on demand. Your method is pretty interresting any way. Thanks again for your help. – Farmland

Answer 2

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:

Flatt