Efficient Way To Compute Points Where Convolution Equals Zero

I want to model the following procedure. Given a shape $$L\subseteq\mathbf{R}^2$$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $$K\subseteq\mathbf{R}^2$$, I want to compute $$\{p\in\mathbf{R}^2: ((1-1_L)*1_K)(p)=0\}$$ (in terms of convolution) or $$\{p\in\mathbf{R}^2:\forall k\in K:p+k\in L\}$$ in an alternative formulation, e.g. all points $$p$$ such that $$K$$ centered at $$p$$ fits into $$L$$. What strategies do I have to perform this at high resolution?

One idea I had was that for every shape $$K$$ there should exist a set of points $$\{d_i\}_i$$ such that if I already know that $$p+d_i$$ is in my set for all $$i$$ then $$p$$ must be in the set as well. E.g. if $$K$$ is the ball with radius $$1$$ then $$\{(0,1),(1,0),(0,-1),(-1,0)\}$$ would be such a set. Using this I could create some grid where I compute the function first and from there deduce some values, then maybe proceed with a finer grained grid?

• What does the notation $1$, $1_L$, $1_K$, and $*$ represent?
– D.W.
Nov 24, 2021 at 17:44
• Convolution, so what I want is $\{p\in\mathbf{R}^2:\forall k\in K:p+k\in L\}$, sorry, I now realize that this a nicer formulation. Nov 24, 2021 at 17:45
• Do you want to consider rotations of $K$ or only translation?
– D.W.
Nov 24, 2021 at 17:45
• How are the shapes represented? Are they the interior of polygons, so they can be represented by their vertices?
– D.W.
Nov 24, 2021 at 17:46
• Rotations would be interesting but translation are fine for now. Ideally it would work with SVG paths, but pixels are fine as well. Nov 24, 2021 at 17:47

I'll describe one way to solve this, with a sweepline algorithm, which I think works. The approach is a bit complex, though it is fully general, should be efficient, and gives the exact answer.

My approach is inspired by the Bentley-Ottmann algorithm, so if this answer is hard to follow, it might be worth reading and understanding that first.

I will assume that the shapes $$L,K$$ are the interior of polygons, and $$K$$ is convex. I assume we know the vertices of these polygons. An edge of a polygon is a line segment between two adjacent vertices (i.e., a line segment on the perimeter). Let $$p=(p_x,p_y)$$, i.e., $$p_x$$ is the $$x$$-coordinate of $$p$$ and $$p_y$$ is the $$y$$-coordinate of $$p$$.

We'll use the following fact about containment:

Fact: If there are no intersections between the edges of $$K,L$$, and one vertex of $$K$$ is inside $$L$$, then $$K \subseteq L$$, i.e., $$K$$ is contained in $$L$$.

Let $$v$$ be a vertex of $$K$$ (any vertex; say the leftmost one). Then the goal is equivalent to finding all $$p$$ such that there is no intersection between the edges of $$K+p$$ and $$L$$, and such that $$v+p$$ is inside $$L$$. To find this set of $$p$$, we'll use a sweepline algorithm.

At any time step in the execution of the sweepline algorithm, we'll have a vertical sweepline at some particular $$x$$-coordinate, namely at $$p_x$$. The goal will be to find all values of $$p_y$$ such that $$K+(p_x,p_y)$$ is contained in $$L$$, i.e., such that there is no intersection between the edges of $$K+(p_x,p_y)$$ and $$L$$, and such that $$v+(p_x,p_y)$$ is inside $$L$$. So let's take a moment to figure out how to achieve that goal. Then, we'll need to sweep the value of $$p_x$$ in an increasing way, so I'll need to discuss how to achieve that.

Given a fixed value of $$p_x$$, here is how we can find all satisfactory $$p_y$$. Consider any edge $$e$$ of $$K$$ and any edge $$f$$ of $$L$$. Then the set of $$p_y$$ such that $$e+(p_x,p_y)$$ does not intersect $$f$$ is a union of two intervals and is easy to compute. Thus, the set of $$p_y$$ such that $$e+(p_x,p_y)$$ does not intersect any edge of $$L$$ is a union of intervals and is also easy to compute. Similarly, the set of $$p_y$$ such that $$v+(p_x,p_y)$$ is inside $$L$$ is another union of intervals that is also to compute. We can intersect those two sets, to get the set of satisfactory values of $$p_y$$, represented as a union of disjoint intervals.

Notice that in this set of values of $$p_y$$, the endpoint of each interval corresponds to a critical value of $$p_y$$ that causes an intersection between $$e+(p_x,p_y)$$ and $$f$$, for some edges $$e,f$$ of $$K,L$$ respectively.

What if we increase $$p_x$$ a tiny bit? What will that do to the endpoint of one of those sets? It'll change the critical value of $$p_y$$ a tiny bit, and it is easy to compute this change if you know the corresponding $$e,f$$. In particular, in some neighborhood of this $$p_x$$, there is a linear relationship between $$p_x$$ and this interval endpoint (this critical value of $$p_y$$). You can also compute the region of validity of this linear relationship (its end corresponds to the $$x$$-coordinate of the endpoints of $$e,f$$, which is the first to the right and the first to the left). Each end of the region of validity is an "event" (i.e., value of $$p_x$$ where things change).

This lets you build a sweepline algorithm. For a fixed $$p_x$$, you can compute the set of valid values of $$p_y$$, and a similar relationship that holds in the neighborhood (region of validity). Between each pair of adjacent events (i.e., values of $$p_x$$), you can express the set of valid values of $$p_y$$ as a disjoint union of intervals whose endpoints are linear functions of $$p_x$$.

In this way, we can build up a data structure that represents the valid pairs $$(p_x,p_y)$$. Essentially, it is a union of a bunch of trapezoids, where each trapezoid has a left and right edge that is vertical and aligns with an "event", and where the top and bottom are sloping based on the linear relationship between $$p_x$$ and $$p_y$$ that holds in that region of validity.

That's a lot of words, and it sounds pretty complex. I apologize that I didn't have time to draw pictures to try to make this clearer. I hope this is helpful nonetheless. I imagine there be corner cases to work out that I have glossed over, based on special cases (e.g., where $$e,f$$ intersect not at a single point but are parallel, and so on).

• Wow, thanks so much for the comprehensive answer! I'll sure need a few days to work through all of this, but really appreciate it! Nov 24, 2021 at 22:38