1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What does the notation $1$, $1_L$, $1_K$, and $*$ represent? $\endgroup$
    – D.W.
    Nov 24 at 17:44
  • $\begingroup$ 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. $\endgroup$
    – fweth
    Nov 24 at 17:45
  • $\begingroup$ Do you want to consider rotations of $K$ or only translation? $\endgroup$
    – D.W.
    Nov 24 at 17:45
  • $\begingroup$ How are the shapes represented? Are they the interior of polygons, so they can be represented by their vertices? $\endgroup$
    – D.W.
    Nov 24 at 17:46
  • $\begingroup$ Rotations would be interesting but translation are fine for now. Ideally it would work with SVG paths, but pixels are fine as well. $\endgroup$
    – fweth
    Nov 24 at 17:47
1
$\begingroup$

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

(See e.g. https://stackoverflow.com/a/4833823/781723 and https://stackoverflow.com/a/52827803/781723.)

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – fweth
    Nov 24 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.