 Welcome to MapForums!

When you are signed in, this message, the ads in this row, and the red-underlined link ads all go away.   ## Mission Impossible? Intersection of Multiple Circles

This is a discussion on Mission Impossible? Intersection of Multiple Circles within the MapPoint Desktop Discussion forums, part of the Map Forums category; Mission: Identify the coordinates of a center point using multiple pairs of Latitude & Longitude each with its own radius ...

1. Junior Member White Belt
Join Date
Nov 2005
Posts
3

## Mission Impossible? Intersection of Multiple Circles

Mission: Identify the coordinates of a center point using multiple pairs of Latitude & Longitude each with its own radius value. The number of pairs varies from 3 to 9. The pairs represent distances from an unknown (data not available) point. Im trying to approximate, as accurately as possible, the latitude and longitude of the unknown point. Sometimes the circles overlap significantly and some circles barely touch or not at all.

Averaging Latitude and longitude points does not produce the desired point, nor does creating weighted averages of the longitude and longitude, using the radius as the factor (illustrated in the illustration code).

The below code example illustrates the challenge (and it might help others trying to work with MapPoint circles, pushpins, colors, latitude and longitude).

Any ideas?

The Lone Turtle

Public Sub IllustrationCircles()

Dim objApp As MapPoint.Application
Set objApp = CreateObject("MapPoint.application")
Dim objMap As MapPoint.Map
Set objMap = objApp.ActiveMap
Dim objPin As MapPoint.Pushpin
Dim objLocS As MapPoint.Location

objApp.Visible = True
objApp.UserControl = True
Dim ObjCount As Integer

Dim dblLat As Double
Dim dblLon As Double
' For Averages

'For Weighted Average
Dim WdblLat As Double
Dim WdblLon As Double
Dim vbColorValue As Long
objApp.WindowState = geoWindowStateMaximize
objApp.PaneState = geoPaneNone
objMap.Altitude = 100

' could be anwhere from 3-9
For ObjCount = 1 To 8

Select Case ObjCount
Case 1
dblLat = 48.6280056894734
dblLon = -99.378787241166
vbColorValue = vbBlack
Case 2
dblLat = 48.4999341491519
dblLon = -99.7047368939117
vbColorValue = vbBlue
Case 3
dblLat = 48.6619616705644
dblLon = -99.8449472515777
vbColorValue = vbCyan
Case 4
dblLat = 48.8583044956192
dblLon = -99.6143183198339
vbColorValue = vbGreen
Case 5
dblLat = 48.7911111785395
dblLon = -99.2499805227612
vbColorValue = vbMagenta
Case 6
dblLat = 48.4910139668177
dblLon = -99.2037748116962
vbColorValue = vbRed
Case 7
dblLat = 48.6293351829129
dblLon = -99.0992993329416
vbColorValue = vbWhite
Case 8
dblLat = 48.3418501927391
dblLon = -99.6915830663967
vbColorValue = vbYellow
End Select

Set objLocS = objMap.GetLocation(dblLat, dblLon)

If vbColorValue = vbBlue Then
objMap.Shapes.Item(ObjCount).Line.Weight = 10

Else
objMap.Shapes.Item(ObjCount).Line.Weight = 1

End If

objMap.Shapes.Item(ObjCount).Line.ForeColor = vbColorValue

'For Average

'For Weighted Average
WdblLat = WdblLat + (dblLat * dblRadius)
WdblLon = WdblLon + (dblLon * dblRadius)

Next ObjCount
objPin.BalloonState = geoDisplayBalloon
objPin.Symbol = 250

objPin.BalloonState = geoDisplayBalloon
objPin.Symbol = 228

Set objLocS = objMap.GetLocation(48.62191, -99.55227)

objLocS.Goto

objMap.Altitude = 12
objMap.Shapes.Item(9).Text = "Notice the vbBlue Circle does Not intersect with more than one circle (vbBlack or vbMagenta), toss it?"

Set objLocS = objMap.GetLocation(48.63562, -99.51499)
objLocS.Goto
objMap.Shapes.Item(10).Text = "This is the desired result (48.63562, -99.51499)."

objApp.ActiveMap.Saved = True

End Sub  Reply With Quote

2. Senior Member Black Belt
Join Date
Nov 2004
Location
Belgium
Posts
2,433
Hi,

I dont understeand your question, but my mother's tongue is not English. Can you eventually clarify the problem with a drawing or so ?  Reply With Quote

3. Junior Member White Belt
Join Date
Nov 2005
Posts
3
Hi Wilfried,

Thanks for responding.

With respect to what I am trying to accomplish; the code which I have posted is an illustration of the problem. If you run the procedure you get a map with circles (and some comments). The map depicts 8 colored circles which represent the data (circles based upon latitude and longitude of the center and a radius).

I am trying to mathematically determine the best intersecting point of the circles as Latitude and Longitude. Unfortunately they do not always perfectly intersect. I believe that GPS utilizes a similar concept to what I am trying to accomplish.

Or maybe as I think it through, it might be the average of all the intersections of the circles. (sum of latitudes of intersections / number of intersections would yield Best Latitude, sum of all Longitudes of intersections / number of intersections would yield Best Longitude). I dont know how to determine the Latitude and Longitude of intersections.

It might help to think of it like this: if you took 8 disks of varying size and laid them on a table in a manor so that most overlapped and some might be butted against another disk, that would be the picture. Im trying to determine the most central point of the intersections. Averaging the data does not work.

Again, the code gives an illustration of the problem.

Thanks for looking at the problem; it might be more of an advanced geometry challenge than a MapPoint challenge.

Regards,

The Lone Turtle  Reply With Quote

4. Senior Member Black Belt
Join Date
Nov 2004
Location
Belgium
Posts
2,433
Hi,

Ok, I opened a new VP project and copied your code. But it does not wants to compile. It comlains on following things:

vbBlack, vbBlue, etc..
geoWindowStateMaximize, geoDisplayBalloon, etc..

I clicked "add reference" in solution explorer and add Micrsosoft mappoint control, but I do not see it in the solution explorer and errors are the same.

I assume I have to include some other files / libraries, but I dont know how to do it in VB. Someone can advice ?  Reply With Quote

5. There might be a geometric solution, but the errors in the input data make it difficult.

I would be tempted to approach the problem with a Simplex Algorithm ("Numeric Recipes in C" has the code, and Sedgwick probably does as well).
Basically, set up a function, which takes a test location as the input, and returns an error.
One possible way of calculating the error:

Measure each distance from the test location to the circle centres.
Then calculate the sum-square of (measured distance - circle radius).
Return square root of this sum, as the error.

Then setup the Simplex algorithm to work in two dimensions and to minimize this error value.
Starting seed coordinates (you'll need three in a triangle) should be somewhere near the centroid of the input data points.

Coding the Simplex algorithm up is quite involved - too much to post here, and probably off topic. If you think you're up to it, I could dig up the book references (both books are good books to have on the shelf anyway).

Also I'm not sure what the speed would be like with VB6 calling MapPoint. Simplex is an iterative algorithm - progressively finding better solutions. As such it is VERY good - far,far better than a brute force search, but it would be difficult to know if it will be too slow or not until you try it.

As an alternative, I initially thought of it as a Linear Programming Problem. If possible, this would be much quicker. However, you need to represent a "measure distance" function as a linear function, I don't think this is possible.

Richard  Reply With Quote

There are currently 1 users browsing this thread. (0 members and 1 guests)

circles, impossible, intersection, mission, multiple 