0

I'm working on an implementation of the MINDIST2POLY algorithm (see Pirzadeh, H. (1999) Computational geometry with the rotating calipers), to calculate the minimum distance between two non-intersecting convex polygons. A key step in the algorithm is as follows, given polygons $P$ and $Q$:

Say we have only hit vertex $q'\in Q$. Compute $dist(p_i, q')$ and compare it to our "minimum-so-far" ($O$(1) time). Now, consider a point $p^\bot$, such that line segment $[p, p^\bot]$ and edge $[q_j, q']$ are orthogonal. Compute the intersection of lines $L(p_i, p^\bot)$ and $L(q_j, q')$. If it exists and is equal to $q_{int}$, $q_{int}\ne q_j, q'$, then compute $dist(p_i, q_{int})$.

Is there a well-known algorithm or procedure for checking whether this intersection exists?

urschrei
  • 145
  • 4

1 Answers1

2

Since you’re working in two dimensions, one simple way to do this is via cross products of homogeneous coordinates. Since $L(p_1,p^\perp)$ is supposed to be orthogonal to $L(q_j,q')$, we can use $q'-q_j$ as its normal. Its line covector is then $L(p_i,p^\perp)=\langle q'-q_j; -(q'-q_j)\cdot p_i\rangle$. For $L(q_j,q')$ we can take $q_j\times q'$. The intersection of the two lines is then simply $L(p_i,p^\perp)\times L(q_j,q')$. Convert back to Cartesian coordinates by dividing through by the third coordinate. (If the third coordinate is zero, the lines are parallel, but by construction that’s impossible.)

For example, say we have $q'=(2,3)$, $q_j=(3,1)$ and $p_i=(-1,0)$. Then $$L(q_j,q')=\langle 3,1,1\rangle\times\langle 2,3,1\rangle=\langle-2,-1,7\rangle$$ for one of our lines. For the other line, $q'-q_j=\langle-1,2,0\rangle$ and so $$L(p_i,p^\perp)=\left\langle-1,2,-\langle-1,2,0\rangle\cdot\langle-1,0,1\rangle\right\rangle=\langle-1,2,-1\rangle.$$ These two lines intersect at $\langle-2,-1,7\rangle\times\langle-1,2,-1\rangle=\langle-13,-9,-5\rangle$, which is $\left(\frac{13}5,\frac95\right)$ in Cartesian coordinates.

amd
  • 53,693