0
$\begingroup$

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle.

This problem works in 2-dimensional Euclidean space. A function takes input of:

  • Two real numbers, the ratio of which graphically represents a slope (a slope of "infinity" should be defined)
  • Two sets of two points, for a total of four points. Each point has two real components

The only restriction is that within each set, the two points cannot coincide, and the two points must not form a line with the same slope as the input slope.

Now, imagine that a line is formed at each of the four points, each with the same specified slope. If one were to point at the left-most line, then move his finger to the right across the graph, the function should output the two points that correspond to the two center lines. In the case that the slopes are horizontal, one can move down-up and find the middle two points that way.

I need a numerical algorithm that solves this problem in the general case.

$\endgroup$
4
  • 1
    $\begingroup$ Why are the points grouped in pairs? Anyways, I think you want to look at the dot products $P \cdot n$, where $P$ is the coordinates of a point, and $n$ is a vector perpendicular to your input slope. (i.e. if your input slope is $a/b$, $n$ should have slope $-b/a$. i.e. it could just be the vector $n=(a,-b)$) $\endgroup$
    – user14972
    Nov 5, 2013 at 5:00
  • $\begingroup$ Could you clarify a few things? For instance, when you "point at" the left-most line, which point are you pointing at? The specified one? When the lines are horizontal, which is the "leftmost" line? It seems that you really just have four lines, each with a specified slope, and you want to find some point on the "second line from the left". Could you clarify exactly what you're after? I think precisely writing down what you want will help you figure out how to do it! $\endgroup$
    – Zach L.
    Nov 5, 2013 at 6:13
  • $\begingroup$ @Hurkyl: The points are grouped in pairs because of the restriction on each pair. I don't see how the dot product will be of use, please clarify on this. $\endgroup$ Nov 5, 2013 at 14:22
  • $\begingroup$ @Zach L.: the left-most line is the one that is the most to the left on the graph. i.e., the one with the lowest x-value. When the slopes are horizontal, there is no "leftmost" line. There would only be a "bottommost" line, and you can find the middle 2 lines by pointing at the bottommost line, then moving upwards. $\endgroup$ Nov 5, 2013 at 14:24

1 Answer 1

1
$\begingroup$

I'd suggest using the normal form of a line, since that nicely handles infinite slopes. The equation $$ax+by=c$$ describes a line with slope $-\frac ab$, since you can rewrite this to $y=-\frac abx+\frac cb$. An infinite slope for a vertical line corresponds to $b=0$. Different values of $c$ describe different lines of the same slope.

So take your slope, represented using two numbers $a$ and $b$, to formulate the left hand side of the equation. Plug in your four points to obtain the corresponding values for $c$. Then sort by these values $c$ to identify the middle ones.

Note that $\begin{pmatrix}a\\b\end{pmatrix}$ is a normal vector of the line, i.e. a vector perpendicular to the line itself. Its size does not really matter, so no need to normalize it to length $1$ as some other applications require, as long as you use the same values for all four points. Now computing a value of $c$ using the left hand side of the equation is simply a dot product, so this is using dot products to compare points, like the comment by Hurkyl suggests.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .