I am trying to find a transformation that takes me between Cartesian coordinates and a pseudo-coordinate-system I have developed which is described as follows:
Please first see the diagram below.

Before I go into details, I would also like to make it clear that I am hoping for a push in the right direction towards solving this problem, although a thorough solution is more than welcome.

Given a straight line segment (red) of length $l$, there are a series of finite points which define the coordinates. These points are constructed as 'equally spaced' dotted lines (all of length $m$), the first of which is at an angle $\theta$ 'clockwise' to the segment perpendicular and rotates regularly up to the end of the segment, at which point the dotted line is at an angle $\phi$ 'anticlockwise' to the segment perpendicular. (As such the most vertical dotted line isn't necessarily at the middle of the segment.)

Within each dotted line, the dots are spaced equally, a distance $d$ apart.
The dotted lines are spaced equally along the segment, a distance $s$ apart.
Specifically I want to devise an algorithm which can map a Cartesian coordinate to the closest point in the coordinate system just described (taking care to state that there is no closest point if it lies outside of the trapezoid [noting that the outermost points still have a finite surrounding area - a smaller trapezoid to be exact]).

This will be coded up, so computational efficiency is a minor goal.


Many thanks in advance.

EDIT: If this problem is too difficult, then a solution for when $\theta = \phi$ (so a vertical dotted line is in the middle of the segment, as in the diagram) would still be useful.

  • $\begingroup$ I may be picky, but the image is so blurry it makes my eyes hurt. $\endgroup$ – tomasz Jul 18 '13 at 22:34

This looks very much like a straightforward Cartesian <-> Polar coordinate system transformation, limited to a trapezoidal section of the Polar space where you cannot see the origin. Have you attempted to use this type of transform?

Edit: I see that it is not truly a polar system with the angle changes you specify. This means that either you can approximate using the polar system (for very small angle changes), or do a line-by-line comparison to see which lines are closest to your point, then take several points on each close line and find the closest of those.

A more straightforward approach would be to note that the way you have created the lines makes it so that for every line $k$ parallel to $l$, the coordinate marks on $k$ are spaced proportionally compared with the coordinate mark spacing on $l$, so that translating your $x$ value is a linear transform (think of parallel lines intersecting a triangle). Once you have calculated your $x$ value in the new coordinate system, you must find the length of the segment $x$ is associated with between lines $k$ and $l$; this will be your $y$ value in the new coordinate system. This should be a straightforward calculation, given that $y$ in Cartesian coordinates is the distance between the lines, and $\theta$ is the angle of the segment. I would guess the $y$ value in the new system would be something along the lines of


where $\theta$ is determined by having found your $x$ value.

I have glossed over the finding of the $x$ value, so here are some more explicit pointers:

Pick any two $\theta$ from your new coordinate system; these coordinate lines will intersect at some point. This is one source of an "origin" for your system, even though it is not "fixed" in the way that origins usually are. Find the distance $d$ from this intersection point to line $l$. Then ${y+d\over d}$ (using the Cartesian $y$ value) is the proportion that you apply to your $x$ value.

  • $\begingroup$ That was a nice suggestion with polar coordinates; I guess it's a bit of a shame that my lines aren't spaced out by angle instead I did think of doing a line-by-line test using binary search, but I fear that even that approach may be a bit too slow $\endgroup$ – user1585968 Jul 18 '13 at 21:29
  • $\begingroup$ I think my most recent edit should account for the difference between your coordinate system and the polar coordinate system. $\endgroup$ – abiessu Jul 19 '13 at 16:50

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.