OCCRA
Go to Post Duct tape is like the Force - it has a dark side and a light side and it holds the universe together. - Jnadke [more]
Home
Go Back   Chief Delphi > Other > Math and Science
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Reply
Thread Tools Rate Thread Display Modes
  #16   Spotlight this post!  
Unread 05-05-2017, 11:46 PM
KJaget's Avatar
KJaget KJaget is offline
Zebravision Labs
FRC #0900
Team Role: Mentor
 
Join Date: Dec 2014
Rookie Year: 2015
Location: Cary, NC
Posts: 112
KJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant future
Re: Math Quiz 11

Letting matlab do the work. Set up a system of equations. x(1) = point2.x, x(2) = point2.y, x(3) = point3.x, etc. This is a set of (xsrc-xdst)^2 + (ysrc-ydst)^2 - distance^2 = 0 equations derived from the list given in the OP.

Code:
function F = distEQ(x)

F(1) = (x(1) - x(5))^2 + (x(2) - x(6))^2 - 47.8017^2;
F(2) = (x(3) - x(7))^2 + (x(4) - x(8))^2 - 69.2026^2;
F(3) = (x(7) - x(15))^2 + (x(8) - x(16))^2 - 148.492^2;
F(4) = (x(11) - x(13))^2 + (x(12) - x(14))^2 - 86.764^2;
F(5) = (x(7) - x(9))^2 + (x(8) - x(10))^2 - 63.0714^2;
F(6) = (x(1) - x(13))^2 + (x(2) - x(14))^2 - 189.528^2;
F(7) = (x(9) - x(11))^2 + (x(10) - x(12))^2 - 65.192^2;
F(8) = (x(5) - x(15))^2 + (x(6) - x(16))^2 - 147.085^2;
F(9) = (x(1) - x(3))^2 + (x(2) - x(4))^2 - 90.5207^2;
F(10) = (x(9) - x(13))^2 + (x(10) - x(14))^2 - 86.0349^2;
F(11) = (x(3) - x(15))^2 + (x(4) - x(16))^2 - 171.956^2;
F(12) = (x(5) - x(11))^2 + (x(6) - x(12))^2 - 88.8144^2;
F(13) = x(1) - 0;
F(14) = x(2) - 0;
Save as distEQ.m

Code:
>> fun = @distEQ;
>> x0(1:16) = 10;
>> x = fsolve(fun, x0)
x =

 Columns 1 through 7:

   8.7244e-20  -4.0763e-20   8.9553e+01  -1.3199e+01   3.9964e+01   2.6228e+01   3.3832e+01

 Columns 8 through 14:

   2.7839e+01   8.8708e+01   5.8929e+01   5.3763e+01   1.1396e+02   1.3930e+02   1.2852e+02

 Columns 15 and 16:

   1.0523e+02   1.5804e+02

# Convert to x,y coords for point2, 3, 4, etc.
>> xx = reshape(x,2,8)'
xx =

   8.7244e-20  -4.0763e-20
   8.9553e+01  -1.3199e+01
   3.9964e+01   2.6228e+01
   3.3832e+01   2.7839e+01
   8.8708e+01   5.8929e+01
   5.3763e+01   1.1396e+02
   1.3930e+02   1.2852e+02
   1.0523e+02   1.5804e+02

# Sanity check pt2 -> pt4 matches the initial conditions
>> sqrt(sum((xx(1,:) - xx(3,:)).^2))
ans =  47.802

# see what this run gets for 8->9 (remember index - 1)
>> sqrt(sum((xx(7,:) - xx(8,:)).^2))
ans =  45.081
Depending on initial conditions and arbitrary values for x&y of point 2, I also get 282.56, 21.878, 290.81, and probably more (out of battery).
Reply With Quote
  #17   Spotlight this post!  
Unread 05-06-2017, 07:19 PM
GeeTwo's Avatar
GeeTwo GeeTwo is offline
Technical Director
AKA: Gus Michel II
FRC #3946 (Tiger Robotics)
Team Role: Mentor
 
Join Date: Jan 2014
Rookie Year: 2013
Location: Slidell, LA
Posts: 4,757
GeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond repute
Re: Math Quiz 11

I have attached a spreadsheet which goes through the calculations to solve this problem. I haven't verified everything on it yet, but I have fixed a lot of problems along the way; I'm mostly posting to show that the problem IS soluble and as a demo of the sorts of ambiguities and multiple roots that make result in multiple solutions to the system of twelve equations in twelve unknowns.

The cells highlighted in yellow are intended to be set as you investigate different values of distance 8-9, and the different ambiguities, or if you want to zoom in to a particular segment of angle 8-5-9; see the notes in the spreadsheet for details. The top graph is a layout of the eight points based on all of the constraints EXCEPT the distance 2-4, and also based on the four ambiguity states and the initial angle 8-5-9. The second plot spans a range of angles 8-5-9. By default, I have it set for the range from 0 to 2pi.

Essentially, you enter the value for distance 8-9, then try each of the 16 ambiguity states, and look for places where the actual distance between points 2 and 4 (red curve) crosses the constraint distance (green line), then trace up that angle to a value for distance 8-9 (blue curve). Ideally, you would use Newton's method or similar to determine where a crossing occurs, and zoom in on it to find more precisely where the crossing occurs. With the assumed distance 8-9 of 55.17, I found two solutions for false-false-false-true, (approx 190 and 186), two for false-true-true-false (127, 183), and a near miss on true-true-true-false (109).

I don't think I've used anything more complex than the law of cosines to do any of this. Does this answer your question, Jon Stratis?
Attached Files
File Type: xlsx MQ11.xlsx (58.9 KB, 9 views)
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.
Reply With Quote
  #18   Spotlight this post!  
Unread 05-11-2017, 10:57 AM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,706
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Math Quiz 11


Math Quiz 11, Part B:

Given three points p1, p2, p3 with coordinates (1,1), (1.5,0.5), and (2.0,0.75) respectively...

... find the coordinates of the point p4 whose distance from points p1, p2, p3 is 1.477601434758372, 1.909792135285932, 2.416879392936271 respectively.


Reply With Quote
  #19   Spotlight this post!  
Unread 05-11-2017, 11:35 AM
Jared Russell's Avatar
Jared Russell Jared Russell is offline
in hibernation
FRC #0254 (The Cheesy Poofs), FRC #0341 (Miss Daisy)
Team Role: Engineer
 
Join Date: Nov 2002
Rookie Year: 2001
Location: San Francisco, CA
Posts: 3,301
Jared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond reputeJared Russell has a reputation beyond repute
Re: Math Quiz 11

Quote:
Originally Posted by Ether View Post

Math Quiz 11, Part B:

Given three points p1, p2, p3 with coordinates (1,1), (1.5,0.5), and (2.0,0.75) respectively...

... find the coordinates of the point p4 whose distance from points p1, p2, p3 is 1.477601434758372, 1.909792135285932, 2.416879392936271 respectively.


This is an overdetermined trilateration problem (3 constraints, 2 unknowns), which happens frequently due to measurement noise in localization systems (like GPS). As such, the solution depends on what properties you want your residual to have. For one such choice of properties, I happen to know a neat trick that solves this problem elegantly for the particular case where (# constraints) = (# unknowns + 1).

Solution here.

This method adds a free parameter to the distance measurements representing measurement error (assuming it is uniform across all measurements), which lets us solve the system of equations efficiently to find the point representing the center of the three circle-circle intersections (obtained by leaving out one constraint at a time). "h" represents the radius^2 of the circle joining those intersections (which can be imaginary, as in this case, depending on whether or not all three circles overlap or not). The fact that "h" is small in magnitude shows that the solution is very close.

It would also be reasonable to want a (perhaps weighted by distance) least squares solution, but this would require whipping out a non-linear least squares solver.
Reply With Quote
  #20   Spotlight this post!  
Unread 05-11-2017, 11:45 AM
Jon Stratis's Avatar
Jon Stratis Jon Stratis is offline
Mentor, LRI, MN RPC
FRC #2177 (The Robettes)
Team Role: Mentor
 
Join Date: Feb 2007
Rookie Year: 2006
Location: Minnesota
Posts: 4,409
Jon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond reputeJon Stratis has a reputation beyond repute
Re: Math Quiz 11

Gee, that's some nice math

For part B... Is the system actually solvable? You can define each circle with the simple equation (x+a)^2 + (y+b)^2 = r^2. That leaves you with 3 equations but only 2 unknowns, which makes it really easy for there to be no solution. Of course, there's no guarantee that the circles even intersect, but we should assume they do, right? Two circles can have 2, 1, or no intersections in common, likewise three circles can have 2, 1, or 0 common intersections!

Plotting it out, it initially looks like there's an intersection point (near -0.409, 0.555) ... but zoom in and the circles just miss having a common intersection. Plug the system of equations into Wolfram Alpha, and it comes back with no solution, supporting this finding.

So, lets simplify it down to pairs of circles, see how close we actually get.

p1 + p2:
x=-0.409
y=0.5550000000000005

p1 + p3:
x=-0.4089999999999995
y=0.5549999999999989

p2 + p3:
x=-0.4089999999999999
y=-0.5550000000000041

Given how close we are... Is this just a rounding issue with your numbers Ether, or is there intentionally no solution?
Attached Thumbnails
Click image for larger version

Name:	Math Quiz 11B.png
Views:	17
Size:	78.9 KB
ID:	22347  Click image for larger version

Name:	Math Quiz 11B2.png
Views:	12
Size:	22.1 KB
ID:	22348  
__________________
2007 - Present: Mentor, 2177 The Robettes
LRI: North Star 2012-2016; Lake Superior 2013-2014; MN State Tournament 2013-2014, 2016-2017; Galileo 2016; Iowa 2017; Tesla 2017
2015: North Star Regional Volunteer of the Year
2016: Lake Superior WFFA
Reply With Quote
  #21   Spotlight this post!  
Unread 05-11-2017, 12:49 PM
KJaget's Avatar
KJaget KJaget is offline
Zebravision Labs
FRC #0900
Team Role: Mentor
 
Join Date: Dec 2014
Rookie Year: 2015
Location: Cary, NC
Posts: 112
KJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant futureKJaget has a brilliant future
Re: Math Quiz 11

The solver approach also gives p4 = (-.409, .555). I modified the distEQ from my previous post and it converged pretty much immediately.

Not sure what Wolfram Alpha uses but e-15 looks an awful lot like C++'s double epsilon value, meaning it it likely hitting limits of the precision an 8-byte floating point number can handle.

Last edited by KJaget : 05-11-2017 at 12:51 PM.
Reply With Quote
  #22   Spotlight this post!  
Unread 05-11-2017, 01:16 PM
GeeTwo's Avatar
GeeTwo GeeTwo is offline
Technical Director
AKA: Gus Michel II
FRC #3946 (Tiger Robotics)
Team Role: Mentor
 
Join Date: Jan 2014
Rookie Year: 2013
Location: Slidell, LA
Posts: 4,757
GeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond reputeGeeTwo has a reputation beyond repute
Re: Math Quiz 11

Point (-.409, .555) works out just fine in gawk (running under cygwin running under windows 7 32 bit); I suspect differences in round off.

Code:
GeeTwo@Teal ~
$ cat ./MQ11.gawk
#!/bin/gawk -f
BEGIN {x[1]=1; x[2]=1.5; x[3]=2.0;
        y[1]=1;y[2]=0.5; y[3]=0.75;
        r[1]=1.477601434758372;
        r[2]=1.909792135285932;
        r[3]=2.416879392936271;
        tx=-.409; ty=0.555;
        for (i=1; i<4; i++) {
                printf "point %d: %.15f %.15f\n",
                        i, r[i], sqrt((tx-x[i])*(tx-x[i])+(ty-y[i])*(ty-y[i]));}
}

GeeTwo@Teal ~
$ ./MQ11.gawk
point 1: 1.477601434758372 1.477601434758372
point 2: 1.909792135285932 1.909792135285932
point 3: 2.416879392936271 2.416879392936271
Excel (2010, same O/S) rounds all these numbers down a digit earlier than depicted.
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.

Last edited by GeeTwo : 05-11-2017 at 01:21 PM.
Reply With Quote
  #23   Spotlight this post!  
Unread 05-11-2017, 01:23 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,706
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Math Quiz 11


Nice work Jared and Jon. Thanks for posting.

Quote:
Originally Posted by Jared Russell View Post
This is an overdetermined trilateration problem (3 constraints, 2 unknowns), which happens frequently due to measurement noise in localization systems (like GPS). As such, the solution depends on what properties you want your residual to have. For one such choice of properties, I happen to know a neat trick that solves this problem elegantly for the particular case where (# constraints) = (# unknowns + 1).

Solution here.
Or minimize the sum of the squares of the distance errors, using Maxima's COBYLA.

Quote:
Originally Posted by Jon Stratis View Post
For part B... Is the system actually solvable?
Good question.

Technically, no, because it's overdetermined as Jared (and you) said...

... but, I purposely picked distance values that make all 3 circles have a common intersection point (to several decimal digits), so in that sense it is solvable for a unique solution.


EDIT:

Quote:
Originally Posted by GeeTwo View Post
Point (-.409, .555) works out just fine in gawk
Hey Gus, welcome to the gawk club! It's my go-to tool for data munging and quick math stuff.




Attached Thumbnails
Click image for larger version

Name:	grf_solution_overview.png
Views:	23
Size:	6.9 KB
ID:	22353  Click image for larger version

Name:	grf_solution_zoom.png
Views:	17
Size:	4.3 KB
ID:	22354  Click image for larger version

Name:	cobyla_minSSE.png
Views:	18
Size:	24.1 KB
ID:	22355  

Last edited by Ether : 05-11-2017 at 02:16 PM.
Reply With Quote
  #24   Spotlight this post!  
Unread 05-11-2017, 04:41 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,706
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Math Quiz 11

Quote:
Originally Posted by Jared Russell View Post
It would also be reasonable to want a (perhaps weighted by distance) least squares solution, but this would require whipping out a non-linear least squares solver.
Change the p4_p3 distance from 2.416879392936271 to 2.6

Now the 3 circles no longer have a common point of intersection, so it becomes an optimization problem.

Maxima can use Powell's COBYLA algorithm to find a "best fit" value based on an objective function that the user can define.

The red boxes are the solution using equal weights for all three distance errors.

The green boxes are the solution for relative weights inversely proportional to the distance.


Attached Thumbnails
Click image for larger version

Name:	no_solution.png
Views:	21
Size:	6.9 KB
ID:	22358  Click image for larger version

Name:	weightedLS.png
Views:	22
Size:	30.2 KB
ID:	22359  
Reply With Quote
  #25   Spotlight this post!  
Unread 05-13-2017, 02:19 PM
Thayer McCollum's Avatar
Thayer McCollum Thayer McCollum is offline
FF: Blucifer
FRC #0159 (Alpine Robotics)
Team Role: Leadership
 
Join Date: Apr 2016
Rookie Year: 2015
Location: Fort Collins
Posts: 366
Thayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond reputeThayer McCollum has a reputation beyond repute
Re: Math Quiz 11

Quote:
Originally Posted by Ether View Post
Change the p4_p3 distance from 2.416879392936271 to 2.6

Now the 3 circles no longer have a common point of intersection, so it becomes an optimization problem.

Maxima can use Powell's COBYLA algorithm to find a "best fit" value based on an objective function that the user can define.

The red boxes are the solution using equal weights for all three distance errors.

The green boxes are the solution for relative weights inversely proportional to the distance.


I'm not nearly as good at math as a lot of you so maybe this doesn't work? I was trying to find an answer that minimized the error using the equal error method. I put the first three points into SolidWorks and then created three distance lines (I didn't use circles) from each point. I then created point four and three more lines connecting each distance line to point four (the error lines). Because I was trying to minimize the error using equal error I set three error lines equal to each other.

Then I didn't know what to do. SolidWorks doesn't (that I know of) have a way to set the length of a line to it's minimum acceptable value. So I just started plugging in numbers, a number larger than the minimum error would be accepted, a number smaller would make the sketch unsolvable. So I started hopping between two numbers, averaging them, getting a new domain, averaging them, etc. I did like 20 iterations of this, eventually working with numbers that were ten decimals long. Then I finally noticed something interesting, as the error became closer to the minimum value the lines became closer and closer to being co-linear.

So I scrapped dimensioning the error lines and just set each error line as co-linear with its respective distance line. This generated the final position of my point four. Which I got to be (-.50036693, .54231098) with an error length of .09102222. This was a different location than Ether's so I tried plugging in his point for equal error. When I did this the minimum error I could get was .118118 (coincidence? I think not).

Ether is a lot smarter than I am, and he actually used math so I'm assuming I just couldn't get SolidWorks to get a smaller error using his point. So what I want to know is what is the error for Ether's calculation and is it actually smaller than mine (I assume so)?
Attached Thumbnails
Click image for larger version

Name:	Quiz11.PNG
Views:	8
Size:	78.8 KB
ID:	22363  Click image for larger version

Name:	Quiz11CloseUp.PNG
Views:	6
Size:	52.8 KB
ID:	22365  
Reply With Quote
  #26   Spotlight this post!  
Unread 05-13-2017, 04:42 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,706
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Math Quiz 11

Quote:
Originally Posted by Thayer McCollum View Post
So what I want to know is what is the error for Ether's calculation and is it actually smaller than mine (I assume so)?
Since the 3 circles have no common point of intersection, there is no unique "correct" solution.

The answer you get depends on what you're trying to minimize and what constraints you impose.

As Jared posted earlier in this thread:
Quote:
Originally Posted by Jared Russell View Post
the solution depends on what properties you want your residual to have
You added the constraint that the magnitude of the residuals had to be equal, so you got a different solution. Your solution is valid, given that extra constraint.

I minimized the sum of the squares of the errors (SSE), with no residual equality constraint, so my solution has a smaller SSE than yours.


Attached Thumbnails
Click image for larger version

Name:	SSE.png
Views:	11
Size:	14.8 KB
ID:	22367  

Last edited by Ether : 05-13-2017 at 07:31 PM.
Reply With Quote
  #27   Spotlight this post!  
Unread 05-13-2017, 05:07 PM
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,706
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: Math Quiz 11

Quote:
Originally Posted by Ether View Post
You added the constraint that the residuals had to be equal, so you got a different solution. Your solution is valid, given that extra constraint
Here's the Maxima solution, with your added constraint (red box) that the residuals must be equal in magnitude.

The coordinates of the solution (green box) match yours, and the residuals (orange box) match yours.


Attached Thumbnails
Click image for larger version

Name:	equal_residuals.png
Views:	15
Size:	26.8 KB
ID:	22368  
Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 08:48 AM.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi