Topic: C# - Find measured point between 3, or more, points?

[Jeff_M]

First, I must state that my math skills are not what they could be...my last class was high school Trig in 1975, I attended 2 college classes for Calculus before I decided it was way over my head for what I was doing. That being said, I hope that this can be solved without hurting my brain too much. I've found some relevant messages/responses over at the StackExchange
http://math.stackexchange.com/questions/366894/closest-point-to-3-or-more-circles
http://math.stackexchange.com/questions/710547/solving-multivariate-polynomial-to-find-closest-point-to-a-3-or-more-circles?lq=1

But I have no idea how to apply the responses.

Let me explain my goal: A surveyor locates 3-6, or more, known points. Each of these points has a measured distance to a point that cannot be accessed to survey. I need to locate the best position of that point. Now, if a circle is drawn with the measured distance from each point, and ALL circles intersect, then this is easily solved by using the average of the closest points of intersections of all the circles. However, there is no guarantee that the circles will intersect, as the measurements have been typically done with a tape measure. Which, I think, means I then need to use the equations shown in the links above. Except, I have NO idea how to apply them, use them, write them in C#. Anyone care to enlighten me?

Here is an example of what is needed to find the location of, except that quite often there are no directions given for the measured distances:

[nobody]

First, I must state that my math skills are not what they could be...my last class was high school Trig in 1975, I attended 2 college classes for Calculus before I decided it was way over my head for what I was doing. That being said, I hope that this can be solved without hurting my brain too much. I've found some relevant messages/responses over at the StackExchange
http://math.stackexchange.com/questions/366894/closest-point-to-3-or-more-circles
http://math.stackexchange.com/questions/710547/solving-multivariate-polynomial-to-find-closest-point-to-a-3-or-more-circles?lq=1

But I have no idea how to apply the responses.

Let me explain my goal: A surveyor locates 3-6, or more, known points. Each of these points has a measured distance to a point that cannot be accessed to survey. I need to locate the best position of that point. Now, if a circle is drawn with the measured distance from each point, and ALL circles intersect, then this is easily solved by using the average of the closest points of intersections of all the circles. However, there is no guarantee that the circles will intersect, as the measurements have been typically done with a tape measure. Which, I think, means I then need to use the equations shown in the links above. Except, I have NO idea how to apply them, use them, write them in C#. Anyone care to enlighten me?

Here is an example of what is needed to find the location of, except that quite often there are no directions given for the measured distances:

I've had some success with this:

http://www.codeproject.com/Articles/30615/Converting-math-equations-to-C

I did have to clean the equations up at the end a little, but not by much.

[Jeff_M]

Thanks, Alien. Not sure what I need to do to get the Word equation to copy correctly. I made the edit to the Word options, but when I copy to the clipboard I still just get the expression, not the MathML.

[MickD]

Hi Jeff, I'm not quite sure I understand the goal exactly but with anything geometrical I like to break it down to triangles. Circles and triangles are the basic building blocks and really, to create these higher level functions in code you need to break down the complex formulas in to basic vectors at a lower level.

Anyway, try and break it down to triangles and basic trig if you can, it might not be as elegant but once you get the lower parts you can optimise those parts into more complex functions to achieve the higher level equivalents as your understanding improves.

hth

[Kerry]

Hi Jeff,
I'd need to see the problem as "knowns" and "required" ... my head works that way currently ...

Circles and triangles are the basic building blocks ...

My Math Master ( in '63 ) used to say ' The world is simple boys ; everything reduces to circles and triangles.'
English master used to say different, but that's another story.

[Jeff_M]

Mick, Kerry - This is the approach I've taken and have a mostly working version using Circles & Triangles. It only falls down when there are known points with measured distances that do not add up to the distance between those points, so no intersecting circles. This normally isn't a problem, but I'm trying to account for those 1 in 100 cases. I'll try to put together a better explanation with graphics tomorrow. I've been at this for about 10 hours today and my brain needs a break.

[nobody]

Thanks, Alien. Not sure what I need to do to get the Word equation to copy correctly. I made the edit to the Word options, but when I copy to the clipboard I still just get the expression, not the MathML.

The copying and pasting was a pain in Word...had to add the tab then change the setting...and if the equation wasn't placed in the equation box in word well it was hard to get to work. Hopefully someone can provide a better solution.

[MexicanCustard]

Create a region where the circles overlap.  If the region is empty then they overlap at the exact point and you can find that point by the average of the closest points of intersections of all the circles.  If the region is not empty you could use the center of mass for the region as the closest point of reference.

[MexicanCustard]

BTW Kean's blog today. 

http://through-the-interface.typepad.com/through_the_interface/2015/08/getting-the-centroid-of-an-autocad-region-using-net.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+typepad%2Fwalmsleyk%2Fthrough_the_interface+%28Through+the+Interface%29

[BillZndl]

Jeff,
Don't know if this is what you're after.
It takes a set of points and gives an point that pretty close to center of all the points.
It's in Autolisp but it might give you some ideas.

Code - Text: [Select]

1. ;3/13/03
2.                                     ;Joe Burke
3.                                     ;Autodesk forums
4.                                     ;
5. (defun AveragePts (ptlist)
6.   (if (null (caddr (car ptlist)))                                              ;test first point for 2D point
7.     (setq ptlist (mapcar '(lambda (x) (append x '(0.0))) ptlist))
8.    )
9.   (mapcar '(lambda (ord)(/ ord (length ptlist) 1.0))
10.    (list
11.      (apply '+ (mapcar '(lambda (pt) (car pt)) ptlist))
12.      (apply '+ (mapcar '(lambda (pt) (cadr pt)) ptlist))
13.      (apply '+ (mapcar '(lambda (pt) (caddr pt)) ptlist))
14.     )
15.    )
16.   )
17.  

[MexicanCustard]

Jeff, I got to thinking about this and if I'm wrong then maybe you can provide a sample that shows otherwise.  If you have two circles who's diameter represents the distance from center to another point and the two circles do no overlap.  Then the average point between them will be a line drawn from center to center and trimmed to only leave the line outside both circles then take the midpoint of the remaining line.  Or simply, the midpoint of a line that's tangent to the closest points of the two circles.   Now realistically that point could lie to either side tangent to one of the circles but if you're asking the computer to make its best guess then the midpoint between the two tangents is close.

I couldn't get three circles that didn't overlap to refer to a single point.  I think with three or more circles there has to be overlap.  Otherwise one circle is so far away it was measured inaccurately.

Edit: I can get three circles to not overlap on the unknown point.  They will overlap just not over where you're trying to find a point.  You would have to create a region from the space between the circles and find the centroid of that.

[Mark]

Let me explain my goal: A surveyor locates 3-6, or more, known points. Each of these points has a measured distance to a point that cannot be accessed to survey. I need to locate the best position of that point.
...
Here is an example of what is needed to find the location of, except that quite often there are no directions given for the measured distances:

I believe what you want is a Least Squares solution. We use to use Cadastral Measurement Management (CMM) to position corners using only distances. That was/is some bad-ass software. I'm guessing it no longer works on the 64bit OS's.

http://wordpress.nmsu.edu/kwurm/cadastral-measurement-management/

[Jeff_M]

MC, I came to the same conclusion last night about the line between circles that don't overlap. I was going to test that approach this evening. I do provide an option to allow a point & measurement to be removed from consideration if it appears that it was recorded in error...I have a form showing the points used, the measured values, and the Residual amount the calculated point is from the actual measured distance. The residual, in practice, should be typically <a few tenths, so if the user sees a large discrepancy they can remove a point (if more than 3 were used) to get a valid location.

Mark, thanks for that. I will do some more investigating before I complete this project.