0

enter image description here

I already posted this question here

And I got the solution thanks to Fang but the problem is that the coordinates I need to use are GPS coordinates and apparently GPS needs a different formula than cartesian.

So I am working with Google Maps APIv3 polygons and having coordinates of AB (by drawing them with the polygon tool) I click on position C which I need to be moved to D which is perpendicular to AB and CD is parallel to AB

So the question would be:

Having
A = 50.88269282423443,6.0036662220954895
B = 50.882753744583226,6.003803014755249
C = 50.88252571592428, 6.003832183778286

- D is perpendicular to AB
- CD is parallel to AB

What would be the formula to get D

I've been trying a long time to figure it out but no succes so far.

Community
  • 1
  • 1
Sinan Samet
  • 6,432
  • 12
  • 50
  • 93

3 Answers3

1

so A,B,C are knowns 'D' is unknown.

axis CD

  • is cd(t1)=C+(B-A)*t1
  • where:
  • cd(t1) is any point on CD
  • t1 is parameter from interval <-inf,+inf>

axis BD

  • is bd(t2)=B+Q*t2
  • where:
  • bd(t2) is any point on BD
  • t2 is parameter from interval <-inf,+inf>
  • Q is vector perpendicular to B-A
  • in 2D you can obtain it like this:
  • Q.x=+(B-A).y
  • Q.y=-(B-A).x
  • in 3D use cross product but your example implies 2D case...

point D

  • is intersection of BD and CD
  • so just solve algebraically this:
  • I. cd(t1)=C+(B-A)*t1
  • II. bd(t2)=B+Q*t2
  • III. cd(t1)=bd(t2)
  • in 2D this (III.) leads to 2 linear equations with 2 variables ...
  • C.x+(B.x-A.x)*t1=B.x+(B.y-A.y)*t2
  • C.y+(B.y-A.y)*t1=B.y-(B.x-A.x)*t2
  • find the parameter t1 and then compute the D=cd(t1)
  • or t2 and then compute the D=bd(t2)
  • you should derivate both solutions and use one with better precision
  • both will use some division A1/A2 so chose one with bigger|A2|

enter image description here

if your point D can lock also to the point A

  • then find both positions D1 locked to A and D2 locked to B
  • and chose one that is closer to the point C (min(|D1-C|,|D2-C|))
  • to simplify this you can use D1+(B-A)=D2 ...

[edit2] I did make some mistake somewhere in edit1 so here is working version

    double ax,ay,bx,by,cx,cy,dx,dy; // points
    double bdx,bdy,cdx,cdy;         // directions
    double t1,t2;                   // parameters
/*
    //--- intersection equations ----------------
    1. cx+cdx*t1=bx+bdx*t2;
    2. cy+cdy*t1=by+bdy*t2;

    //--- separate t1 ---------------------------
    1. t1=(bx-cx+(bdx*t2)/cdx;
    //--- substitute t1 and separate t2 ---------
    2. t2=(cy-by+((bx-cx)*cdy/cdx))/(bdy-(bdx*cdy/cdx));
    //-------------------------------------------

    //--- separate t2 ---------------------------
    1. t2=(cx-bx+cdx*t1)/bdx;
    //--- substitute t2 and separate t1 ---------
    2. t1=(by-cy+((cx-bx)*bdy/bdx))/(cdy-(cdx*bdy/bdx));
    //-------------------------------------------
*/
    // common
    cdx=bx-ax;
    cdy=by-ay;
    bdx=+cdy;
    bdy=-cdx;
    //solution 1
    t2=(cy-by+((bx-cx)*cdy/cdx))/(bdy-(bdx*cdy/cdx));
    dx=bx+bdx*t2;
    dy=by+bdy*t2;
    //solution 2
    t1=(by-cy+((cx-bx)*bdy/bdx))/(cdy-(cdx*bdy/bdx));
    dx=cx+cdx*t1;
    dy=cy+cdy*t1;
  • just use the solution that is not dividing by zero ...
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Nice answer but as I am not very good in math it will take me a while to study and figure it out and finally convert it to a javascript function. Also what exactly does `<-inf,+inf>` stand for? – Sinan Samet Jan 06 '15 at 09:39
  • @SinanSamet just finished editing so read the answer again. the interval `<-inf,+inf>` means that the number can be any from real numbers from -infinity to + infinity ... that is axis for line it would be from 0 to 1. the math is very simple when you read again you will find the basic school equations I think you can solve this on paper within 5 mins ... when not use derive or whatever tool ... – Spektre Jan 06 '15 at 09:47
  • Alright thank you! I will do my best just need a little time to wake up it's still early :) – Sinan Samet Jan 06 '15 at 09:52
  • For example with the formula `cd(t1)=C+(B-A)*t1` I suppose I am to do it twice? Once for the x and once for the y? – Sinan Samet Jan 06 '15 at 10:04
  • 1
    @SinanSamet yes ..I already derivate the the system search for text `in 2D this (III.) leads to 2 linear equations with 2 variables ...` after that line is the system you should to solve get t1 or t2 from it and substitute it back to `cd(t1)=C+(B-A)*t1` ... which are 2 equations one for `x` and one for `y` as you deduced... (this is called vector math) – Spektre Jan 06 '15 at 10:15
  • I started with the formula `C.x+(B.x-A.x)*t1=B.x+(B.y-A.y)*t2 C.y+(B.y-A.y)*t1=B.y-(B.x-A.x)*t2` like you said and having `A=1,6 B=4,8 C=5,3` I got the right answer when I found t1 and t2 was +1 on both sides. So I am supposed to use t1 now at all times? And I didn't use any of the other formulas so far but am I supposed to to find the final formula? (apologies if I ask stupid questions) – Sinan Samet Jan 06 '15 at 10:47
  • @SinanSamet lol algebraic solution means you do not use numbers before the final equation is derived... wait a minute I will try to do it and add into answer :) – Spektre Jan 06 '15 at 10:51
  • Maybe I'm wrong but what I found of this is `t1.x = C.x+(B.x-A.x)*B.x+(B.y-A.y)` and `t1.y = C.y+(B.y-A.y)*B.y-(B.x-A.x)`. Oh okay I didn't know that D: – Sinan Samet Jan 06 '15 at 10:52
  • @SinanSamet done hope I did not make some silly math mistake ... but you get the idea what to do even if yes ... – Spektre Jan 06 '15 at 11:10
  • I find this pretty complicated to understand but I tried using the formula `t1=((B.x-C.x)/(B.x-A.x) + (B.y-A.y)*(C.y-B.y)/((A.x-B.x)*(B.x-A.x)))/(1-((B.y-A.y)/((A.x-B.x)*(B.x-A.x))))` to get t1 and used the solucation to get x with it but the answer was wrong (probably my mistake) I guess I should start with looking into algebraic solutions. – Sinan Samet Jan 06 '15 at 13:05
  • I noticed I miscalculated it so I recalculated but this time I got 0 as answer to t1 which would mean D.x = C.x which was not true in my case. I'm trying to do the deriving too but I just don't understand how t2 suddenly disappears for example. – Sinan Samet Jan 06 '15 at 14:48
  • @SinanSamet well that is easy after separation of t1,t2 you get two equations `t1=f(t2)` and `t2=g(t1)` so instead of `t2` you wrote `g(t1)` (that is called substitution) so it became `t1=f(g(t1))` now separate the `t1` again and that is the result. if you use `dx,dy` instead of `(B.x-A.x),(B.y-A.y),Q.x,Q.y` then it will be more readable to avoid mistakes. if the angle of `A B is 0,90,180 or 270 deg` then one axis has zero change and one of the solution is wrong therefore you should evaluate the correct one – Spektre Jan 06 '15 at 20:50
  • @SinanSamet I tried my equation today and I had a mistake there see edit2 for the working version you have there both solutions so you do not need to derivate anything ... – Spektre Jan 07 '15 at 10:08
  • Thank you I will look into it. I just finished reading this: http://www.purplemath.com/modules/systlin4.htm and it all became much more clear to me now :D Feels good to understand it – Sinan Samet Jan 07 '15 at 10:20
  • It kinda works but I still have the same problem I had here: http://stackoverflow.com/questions/27251745/finding-closest-90-degree-angle-spot?lq=1 The line somehow extends and Fang told me there it's because I am using GPS coordinates and not cartesian. See the last picture in my question on that post that's what's happening. – Sinan Samet Jan 07 '15 at 10:36
  • @SinanSamet well that is true ... convert GPS to cartesian and then the solution back to the GPS then ... see spherical coordinate system on wiki you will find all equations there. but that will give you 3D points not 2D so either use the dot/cross product version or project the points onto plane with `normal = (B-A)x(C-A)` and point `(A+B+C)/3` lies on the plane and use basis vector conversion to 2D/3D – Spektre Jan 07 '15 at 10:46
  • @SinanSamet look here http://stackoverflow.com/a/27166057/2521214 how the basis vectors work ... you do not need even to compute the plane ... if you code it right – Spektre Jan 07 '15 at 10:52
1

After your previous question about the polygons, I started making something, a javascript object. It will show its use here. I posted it there (I skipped the documentation in this post here, please read the documentation there): Mercator Projection slightly off

I first post the code, I explain later.


<title>Getting coordinates perpendicular to AB</title>
<div id="log"></div>
<script src="https://maps.googleapis.com/maps/api/js?v=3.exp&libraries=geometry"></script>
<script>
Earth = {
    // @see http://www.space.com/17638-how-big-is-earth.html for the data
    // along the equator
  circumference_equator: 40075000,    
   // throught both poles.
   // Note: this is basically the original definition of the meter; they were 2km off on a distance from pole to equator ( http://en.wikipedia.org/wiki/History_of_the_metre )
  circumference_poles: 40008000,              
  // given a change in latitude, how many meters did you move?
  lat2Y: function(dLat) {
    return this.circumference_poles / 360 * dLat;
  },
  // given a change in longitude and a given latitude, how many meters did you move?
  lng2X: function(dLng, lat) {
    return Math.cos( this.deg2rad(lat) ) * (this.circumference_poles / 360 * dLng);
  },
  // given a distance you move due North (or South), what's the new coordinates?
  // returns a change in latitude
  y2Lat: function(y) {
    return y * 360 / this.circumference_poles;
  },
  // given a distance you move due East (or West) and a given latitude, what's the new coordinates?
  // returns a change in longitude
  x2Lng: function(x, lat) {
    return x * 360 / ( Math.cos( this.deg2rad(lat) ) * this.circumference_poles);
  },
  // (360°) degrees to radials
  deg2rad: function(deg) {
    return deg * Math.PI / 180;
  },
  // returns a change in position
  xy2LatLng: function(y, x, lat) {
    return {
      lat: this.y2Lat(y),
      lng: this.x2Lng(x, lat)
    };
  },
  // @param heading: North = 0; east = 90°; ...
  setHeading: function(lat, lng, dist, heading) {
    var latDestination = lat +  this.y2Lat(dist * Math.cos(this.deg2rad(heading)));
    var lngDestination = lng +  this.x2Lng(dist * Math.sin(this.deg2rad(heading)), lat);
    return {
      lat: latDestination,
      lng: lngDestination
    };
  },
  // returns the absolute position
  moveByXY: function(lat, lng, x, y) {
    var dLatLng = Earth.xy2LatLng(x, y, lat);
    latLng = [dLatLng.lat, dLatLng.lng ];
    return {
      lat: lat + latLng[0], 
      lng: lng + latLng[1]
    }
  }
}
/**
* returns the shortest distance between a point p and a line segment (u,v).
* based on https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
*/
function distToSegment(p, v, w) { 
  return Math.sqrt(distToSegmentSquared(p, v, w)); 
  function distToSegmentSquared(p, v, w) {
    var l2 = dist2(v, w);
    if (l2 == 0) {return dist2(p, v);}
    var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    if (t < 0) {return dist2(p, v);}
    if (t > 1) {return dist2(p, w);}
    return dist2(p, 
      {x: v.x + t * (w.x - v.x),
       y: v.y + t * (w.y - v.y)}
    );
  }
  function sqr(x) { 
    return x * x ;
  }
  function dist2(v, w) { 
    return sqr(v.x - w.x) + sqr(v.y - w.y); 
  }
}
</script>
<script>
var A = {lat: 50.88269282423443,  lng: 6.0036662220954895};
var B = {lat: 50.882753744583226, lng: 6.003803014755249};
var C = {lat: 50.88252571592428,  lng: 6.003832183778286}; 
// get the angle of AB (let Google calculate it)
var angle_ab = google.maps.geometry.spherical.computeHeading(
  new google.maps.LatLng(A.lat, A.lng), 
  new google.maps.LatLng(B.lat, B.lng)
);
// we convert these coordinates to metric units. lat goes along y; lng goes along x
// so this tells us that from A to B there are X metres eastwards, Y metres northwards.
var a = {x:0, y:0};
var b = {
  x: Earth.lng2X(B.lng - A.lng, A.lat),
  y: Earth.lat2Y(B.lat - A.lat),
};
var c = {
  x: Earth.lng2X(C.lng - A.lng, A.lat),
  y: Earth.lat2Y(C.lat - A.lat),
};
// second, we look for point E, being the projection of C on AB
var dist_E = distToSegment(c, a, b);
// Now we know this: if we move from B, distance "dist_E" on an angle 90° to the right (anti-clockwise) of AB
var D = Earth.setHeading(B.lat, B.lng, dist_E, angle_ab + 90);

log('distance of E (= projection of C on AB) to AB: <b>' + dist_E +'</b>m');
log('Point D: <b>' + D.lat +','+ D.lng +'</b>');

function log(text) {
  document.getElementById('log').innerHTML += text + '<br>';
}
</script>

What I did:

  • first I convert the data from coordinates to metres

  • I find point E: the projection of C on AB

  • The distane and angle of CE is the same as BD, so I can use Earth.setHeading(), from B.


NOTICE: There is no rectangle in your question, but still, notice: there is no such thing as a rectangle on a curved surface; it is impossible make that rectangle completely accuratly. If you go x distance forward, then turn 90° to the right hand side and repeat that 4 times, you will not get back (exactly) on the point where you started.

On a sphere, the sum of the angles of a rectangle will be greater than 360°; the sum of the angles of a triangle will be greater than 180°. Simple example: take points (lat, lng) 0,0 ; 0,90 ; 90,0 (two points on the equator + the North Pole); that's a triangle with a sum of angles = 270°.

So, what ever answer you seek, will be an approximation. The bigger the distances, the less accurate the result will be (no matter what genius solves the problem);

You cannot simply assume every right angle on your diagram will be a right angle on the earth's surface.

Community
  • 1
  • 1
Emmanuel Delay
  • 3,619
  • 1
  • 11
  • 17
  • Thanks I will look into it. Also exact function that I want is already made I am just trying to clone it. The function I am trying to make is the right angle function you can use in Google Mapmaker when you draw a building and hold shift, it shows you the guideline to the right angle and snaps to it. That's just exactly what I want. – Sinan Samet Jan 07 '15 at 13:28
  • Yes, that's (kind of) why I wrote it. Look if you are happy with the accuracy of my result. – Emmanuel Delay Jan 07 '15 at 13:31
  • Look very impressive! I'm implementing it in my code right now to see if it works like I want it to I hope it does! – Sinan Samet Jan 07 '15 at 13:46
  • It does work sometimes but it has some mistakes I think. For example when I have a polygon which has no exact 90 degree angles and I edit the polygon with your function, sometimes it does go to the right spot. But depending on which side I choose I guess it goes to the opposite side sometimes. So when I have this polygon http://prntscr.com/5pjev1 and I edit the upper right corner it does this: http://prntscr.com/5pjf82 The unfilled edge is where I dropped the point, and your function moved it to the bottom. – Sinan Samet Jan 07 '15 at 14:11
  • It also doesn't lock to the closest point of the chosen C but it has a specified length somehow which is mostly correct or nearly correct. But I can't choose my own length because of that. – Sinan Samet Jan 07 '15 at 14:30
  • I noticed it works right for all corners except one when I draw the polygon clockwise and when I draw it anti-clockwise it doesn't. – Sinan Samet Jan 07 '15 at 14:39
  • I'll have to look at this a little later. But look at line 108, where I put the +90. Try -90 there. – Emmanuel Delay Jan 07 '15 at 14:43
  • Alright. And I tried that just now when I do that the ones that were going right go wrong and the ones that were going wrong go right. Also what Mapmaker does is take the closest point to the dropped point but this one only changes the degree to 90 degrees keeping the same length. But besides these 2 things it works good! – Sinan Samet Jan 07 '15 at 14:51
  • In case it would be helpful I also posted this question on the gis exchange site and got recommended to use JSTS which seems useful but I couldn't find my way around it yet. http://gis.stackexchange.com/questions/128269/getting-gps-coordinates-perpendicular-and-parallel-to-ab/128313?noredirect=1#comment185165_128313 – Sinan Samet Jan 07 '15 at 14:54
  • If I could only get the degrees C to AB that would be enough to fix one of the problems :) – Sinan Samet Jan 07 '15 at 15:32
  • Look at line 90. calculate var angle_ac, then calculate angle_ac - angle_ab. Something like that – Emmanuel Delay Jan 07 '15 at 15:37
  • I tried but I don't get the expected degree somehow. My idea was to get the degree from C to AB and choose the closest 90 degree so if it would return -110 for example I would make it go to -90 and if it would be 78 degrees for example I would choose 90 degrees instead. But angle_ac-angle_ab somehow doesn't return what it should return. Maybe the values I give in are wrong but I'm pretty sure they are correct I tested them. – Sinan Samet Jan 07 '15 at 16:11
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/68362/discussion-between-emmanuel-delay-and-sinan-samet). – Emmanuel Delay Jan 07 '15 at 18:00
1

Thanks to Emmanuel I was able to find the spherical functions which helped me a lot by making the function. I like his answer too but what I finally made was a lot less code.

this.makeRightAngle = function(polygon, e, A, B, C){
    var heading_AB = google.maps.geometry.spherical.computeHeading(
      new google.maps.LatLng(A.lat, A.lng), 
      new google.maps.LatLng(B.lat, B.lng)
    );

    var heading_AC = google.maps.geometry.spherical.computeHeading(
      new google.maps.LatLng(A.lat, A.lng), 
      new google.maps.LatLng(C.lat, C.lng)
    );

    var heading_BC = google.maps.geometry.spherical.computeHeading(
      new google.maps.LatLng(A.lat, A.lng), 
      new google.maps.LatLng(C.lat, C.lng)
    );

    var distanceBC = google.maps.geometry.spherical.computeDistanceBetween(
      new google.maps.LatLng(B.lat, B.lng), 
      new google.maps.LatLng(C.lat, C.lng)
    );

    var heading_C_AB = heading_AC - heading_AB;

    if((heading_C_AB < 0 && heading_C_AB > -200) || (heading_C_AB > 200)){
        var new_heading = heading_AB - 90;
    }
    else{
        var new_heading = heading_AB + 90;
    }

    var D = google.maps.geometry.spherical.computeOffset(
      new google.maps.LatLng(B.lat, B.lng), //From LatLng
      distanceBC, //Get distance BC
      new_heading //Heading of AB + or - 90 degrees
    );

    var p = {x: D.lat(), y: D.lng()};

    var latlng = new google.maps.LatLng(p.x, p.y);

    return latlng;  
}

Still many thanks for both answers!

Sinan Samet
  • 6,432
  • 12
  • 50
  • 93