0
$\begingroup$

Given two intersecting polygons and a direction vector, how can one find the distance that one (and only one) of the polygons needs to be translated in the given direction in order to eliminate the intersection?

For example: How far should the red poly move in the direction of the arrow to clear the blue poly?

I.e. let $p1$, $p2$ be polygons such that $p1 \cap p2 \ne \emptyset$; let $v$ be a vector. Find a scalar $s$ such that $( p1 + vs ) \cap p2 = \emptyset$.

I have attempted several strategies so far, but neither seems to be general enough. Since an intuitive solution is evident when looking at an image, I'm sure there must be a general procedure, but so far have been unable to find one, and all references to similar problems are mired in the concreteness of their specific domains (i.e. GIS, gaming programming, etc).

$\endgroup$
5
  • $\begingroup$ You mean, something like (in imprecise terms), "Extend the leading edges of the static polygon backwards to infinity, and compute the union of the result and the moving polygon. The distance the moving polygon needs to move, is the maximum altitude of that union, measured along the direction vector." perhaps? Unfortunately, my math-fu is weak on proofs and such definitions, so I am afraid I cannot help further than that (except that instead of infinity, sweep comes to mind)... but perhaps one of the highly capable members here will rephrase that with the correct terminology? $\endgroup$
    – Nominal Animal
    Nov 18, 2017 at 1:18
  • $\begingroup$ Also, you might wish to reword that into "Find a scalar $S$ such that ... for all $s \ge S$", to explicitly omit the consideration of cases where there is some range of $s$ where no intersection occurs; i.e. the bigger of the two polygons has a hole or niche where the smaller polygon fits into. My comment above explicitly rejects such cases, and is intended to calculate the minimum $s$ at and after which no intersection occurs at all. $\endgroup$
    – Nominal Animal
    Nov 18, 2017 at 1:24
  • $\begingroup$ Thanks for both edit and comments. Your first comment is actually what I'm doing for now: find the forward/back edges of p1 and p2, extend segments parallel to v backwards/forwards and get distance to entry/exit into from the respective other polygon, get s as a max from those... I got to this through trial and error, so I don't know if it is on-topic for this site, but I'd be happy to post it as an answer when I have time. $\endgroup$
    – jtatria
    Nov 21, 2017 at 6:42
  • $\begingroup$ Re: the qualification: my original problem didn't contemplate holes or niches, and though I purposefully didn't specify convex polygons in hopes of finding a more general answer, I see now that such a solution might not exist... But on the other hand, fitting a smaller polygon in a hole would actually work for me, so I'd rather keep it in-scope. In any case, this turned out to be much harder than I thought... geometry is hard :S $\endgroup$
    – jtatria
    Nov 21, 2017 at 6:52
  • $\begingroup$ Numerically, there are certain obvious approaches, that might ... uh, "extend back"? .. to the geometric description. For example, the system can always be rotated so that the direction vector is on the positive $x$ axis. This leads to only having to consider edges that are in or participate (i.e. partially or fully included) in the $y$ range of the smaller object. Splitting the edges so that each vertex in one object has a vertex in the other at the same $y$ leads to an obvious algorithm of finding the altitude (since it can only occur at an $y$ with a vertex in one or both of the objects). $\endgroup$
    – Nominal Animal
    Nov 21, 2017 at 11:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .