I want to calculate the intersection points of the following image:

http://www.deimel.org/images/parabola.gif

Assume that the three points of the triangle could be located anywhere.

How would I do this?

  • I think the formula for the quadratic spline can be adapted for my needs. – posfan12 Aug 28 '13 at 22:15
  • The image illustrates a parabola as the "envelope" of lines of the form $$x(a-t)+yt=t(a-t)$$ (where $a$ is the (constant) length of the "legs" of the figure, and $t$ is a parameter that varies from $0$ to $a$). The way envelopes work, the parabola doesn't contain points of intersection of the lines; the parabola is tangent to each line at some point (usually not the point of intersection with another line). Do you really want the points-of-intersection? Or do you want the points(-of-tangency) actually on the parabola? – Blue Aug 28 '13 at 23:10
  • I need the points of intersection. I already know how to generate the spline. – posfan12 Sep 4 '13 at 0:55
up vote 1 down vote accepted

Let's first solve the problem where the figures right-corner is at the origin, and its legs (of unit length) align with the axes.


The intercept-intercept form of the line equation gives this parameterization of the various lines: $$\frac{x}{t} + \frac{y}{1-t} = 1 \quad \text{or, in fraction-free form,} \quad x(1-t) + y t = t (1-t)$$ for $t$ a parameter between $0$ and $1$ (the extreme values being valid only in the fraction-free version).

Now, if we divide each leg into $n$ pieces (with $n+1$ equally-spaced points), then the intersection of the lines corresponding to $t=\frac{i}{n}$ and $t=\frac{j}{n}$, with $i, j \in \{0, 1, \dots, n\}$, is the point $$P_{ij} := \frac{1}{n^2}\large(\;ij\;,\;(n-i)(n-j)\;\large)$$


When the figure is located "anywhere", we need to apply a simple transformation. Note that, because the intersection points are defined via ratios of lengths of parallel segments, an affine transformation (that is, a linear transformation followed by a translation) will preserve the pattern.

Let's say that the resulting figure should have its (not-necessarily-right) corner at $C$ and its (not-necessarily-unit-length) legs ending at points $A$ and $B$.

We can write our original intersection points $P_{ij}$ as $$P_{ij} = \frac{ij}{n^2} u + \frac{(n-i)(n-j)}{n^2} v$$ where $u$ and $v$ are the unit vectors in the positive $x$ and $y$ directions.

Replacing $u$ with $A-C$ and $v$ with $B-C$ transforms the figure into the correct shape, though its corner remains at the origin; adding $C$ translates the figure into place. So, our transformed intersection points are given by

$$\begin{align} P^\prime_{ij} &= \frac{ij}{n^2} (A-C) + \frac{(n-i)(n-j)}{n^2} (B-C) + C \\[6pt] &= \frac{ij}{n^2} A \;+\; \frac{( n-i )( n - j )}{n^2} B \;+\; \frac{i (n-j) + j(n-i)}{n^2} C \end{align}$$

  • As I said in my original post, the three points of the triangle formed by the two outer segments can be located anywhere, in any configuration. I don't think your formula works when that is the case. – posfan12 Sep 4 '13 at 20:19
  • Ah, right. Well, we just need to apply an appropriate transformation. I'll adjust my answer. – Blue Sep 4 '13 at 20:37
  • Sorry. How do I solve this type of equation? I am accustomed to using parametric formulas where there are two equations - one for the x value, one for the y value. – posfan12 Sep 4 '13 at 23:14
  • Give the triangle's vertices coordinates, $A(x_a,y_a)$, $B(x_b,y_b)$, $C(x_c,y_c)$. For brevity here, let $\alpha$, $\beta$, $\gamma$ be the multipliers on $A$, $B$, $C$. Then, writing $(x,y)$ for $P^\prime_{ij}$, the formula $$P^\prime_{ij} = \alpha \; A + \beta \; B + \gamma \; C$$ simply means $$\begin{align}x &= \alpha \; x_a + \beta \; x_b + \gamma \; x_c \\ y &= \alpha \; y_a + \beta \; y_b + \gamma \; y_c\end{align}$$ – Blue Sep 4 '13 at 23:40

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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