Welcome to MapForums!

Register, sign in, or use Facebook Connect above to join in and participate in the forum.

When you are signed in, this message, the ads in this row, and the red-underlined link ads all go away.

Subscribe to receive our newsletter.
Subscribe Unsubscribe
Results 1 to 5 of 5

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. #1
    The Lone Turtle is offline 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
    Dim dblRadius As Double
    ' For Averages
    Dim AdblLat As Double
    Dim AdblLon As Double

    'For Weighted Average
    Dim WdblLat As Double
    Dim WdblLon As Double
    Dim WdblRadius 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
    dblRadius = 6.18
    vbColorValue = vbBlack
    Case 2
    dblLat = 48.4999341491519
    dblLon = -99.7047368939117
    dblRadius = 10.11
    vbColorValue = vbBlue
    Case 3
    dblLat = 48.6619616705644
    dblLon = -99.8449472515777
    dblRadius = 15.16
    vbColorValue = vbCyan
    Case 4
    dblLat = 48.8583044956192
    dblLon = -99.6143183198339
    dblRadius = 16.05
    vbColorValue = vbGreen
    Case 5
    dblLat = 48.7911111785395
    dblLon = -99.2499805227612
    dblRadius = 16.18
    vbColorValue = vbMagenta
    Case 6
    dblLat = 48.4910139668177
    dblLon = -99.2037748116962
    dblRadius = 17.37
    vbColorValue = vbRed
    Case 7
    dblLat = 48.6293351829129
    dblLon = -99.0992993329416
    dblRadius = 18.99
    vbColorValue = vbWhite
    Case 8
    dblLat = 48.3418501927391
    dblLon = -99.6915830663967
    dblRadius = 21.93
    vbColorValue = vbYellow
    End Select

    Set objLocS = objMap.GetLocation(dblLat, dblLon)

    objMap.Shapes.AddShape geoShapeRadius, objLocS, dblRadius * 2, dblRadius * 2
    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
    AdblLat = AdblLat + dblLat
    AdblLon = AdblLon + dblLon

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

    Next ObjCount
    Set objPin = objMap.AddPushpin(objMap.GetLocation(WdblLat / WdblRadius, WdblLon / WdblRadius), "Weighted Lat & Long")
    objPin.BalloonState = geoDisplayBalloon
    objPin.Symbol = 250

    Set objPin = objMap.AddPushpin(objMap.GetLocation(AdblLat / 8, AdblLon / 8) , "Average Lat & Long")
    objPin.BalloonState = geoDisplayBalloon
    objPin.Symbol = 228

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

    objLocS.Goto

    objMap.Altitude = 12
    objMap.Shapes.AddTextbox objLocS, 125, 100
    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.AddTextbox objLocS, 100, 50
    objMap.Shapes.Item(10).Text = "This is the desired result (48.63562, -99.51499)."

    objApp.ActiveMap.Saved = True


    End Sub

  2. #2
    Wilfried is offline 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 ?

  3. #3
    The Lone Turtle is offline 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

  4. #4
    Wilfried is offline 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 ?

  5. #5
    Winwaed's Avatar
    Winwaed is offline Mapping-Tools.com Black Belt
    Join Date
    Feb 2004
    Location
    Irving,Texas
    Posts
    1,859
    Blog Entries
    60
    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
    Winwaed Software Technology LLC
    http://www.winwaed.com
    See http://www.mapping-tools.com for MapPoint Tools

Thread Information

Users Browsing this Thread

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

Similar Threads

  1. Incorrect road linkages [missing or impossible routing]
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 12-16-2004, 01:38 PM
  2. How to find intersection
    By vidyakulkarni in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 08-09-2004, 10:03 PM
  3. Circles
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 3
    Last Post: 12-09-2003, 12:35 AM
  4. Finding Closes Intersection
    By Sylvain in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 05-14-2003, 06:08 PM
  5. As a developer of emergency services mission criti....
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 07-31-2001, 05:22 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25