Markers Area

Topics: General
Sep 5, 2011 at 8:55 AM

Hello,

I have to determine the external area of some point (markers) that contains all the points.

Sample:

http://imageshack.us/photo/my-images/535/pointsp.png/

http://imageshack.us/photo/my-images/225/areav.png/

Any idea?

(sorry for the synthesis but my english is poor)

 

thanx

Franco

Sep 5, 2011 at 5:48 PM
Edited Sep 5, 2011 at 5:50 PM

well you need to find some algorithm to do that, please share the code if you will

p.s. check http://greatmaps.codeplex.com/discussions/269680

Sep 7, 2011 at 11:27 AM
radioman wrote:

well you need to find some algorithm to do that, please share the code if you will


The original code is written in Java (i found it on the internet)

I've translated it and this is the result.

For me it works fine ;)

 
Imports System.Collections.Generic
Imports GMap.NET

Public Class Hull
    Public Class PositionComparator
        Implements IComparer(Of PointLatLng)

        Public Function Compare(ByVal p1 As GMap.NET.PointLatLng, ByVal p2 As GMap.NET.PointLatLng) As Integer Implements System.Collections.Generic.IComparer(Of GMap.NET.PointLatLng).Compare
            Dim result As Integer = -2
            If p1.Lng > p2.Lng Then
                result = 1
            End If
            If p1.Lng < p2.Lng Then
                result = -1
            End If
            If p1.Lng = p2.Lng Then
                If p1.Lat > p2.Lat Then
                    result = 1
                End If
                If p1.Lat < p2.Lat Then
                    result = -1
                End If
                If p1.Lat = p2.Lat Then
                    result = 0
                End If
            End If
            Return result
        End Function
    End Class

    Private Function isLeft(ByVal p0 As PointLatLng, ByVal p1 As PointLatLng, ByVal p2 As PointLatLng) As Double
        'isLeft(): tests if a point is Left|On|Right of an infinite line.
        ' Input:  three points P0, P1, and P2
        ' Return: >0 for P2 left of the line through P0 and P1
        '		   =0 for P2 on the line
        '		   <0 for P2 right of the line
        'function isLeft( P0, P1, P2 ) {
        ' return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
        '}

        Return (p1.lng - p0.lng) * (p2.lat - p0.lat) - (p2.lng - p0.lng) * (p1.lat - p0.lat)
    End Function

    Public Overridable Function chainHull_2D(ByVal p As List(Of PointLatLng), ByVal n As Integer, ByVal h As List(Of PointLatLng)) As Integer
        'chainHull_2D(): Andrew's monotone chain 2D convex hull algorithm
        '  Input:  P[] = an array of 2D points sorted by increasing x- and y-coordinates
        '	          n = the number of points in P[]
        '  Output: H[] = an array of the convex hull vertices (max is n)
        '  Return: the number of points in H[]

        '  Try to order array p
        'Collections.sort(p, New PositionComparator())
        p.Sort(New PositionComparator())

        ' the output array H[] will be used as the stack
        Dim bot As Integer = 0 ' indices for bottom of the stack
        Dim top As Integer = -1 ' indices for top of the stack
        Dim i As Integer ' array scan index

        ' Get the indices of points with min x-coord and min|max y-coord
        Dim minmin As Integer = 0
        Dim minmax As Integer = 0
        Dim xmin As Double = p(0).Lng

        For i = 1 To n - 1
            If p(i).Lng <> xmin Then
                Exit For
            End If
        Next i
        minmax = i - 1
        If minmax = n - 1 Then ' degenerate case: all x-coords == xmin
            top += 1
            h.Insert(top, p(minmin))
            'If p(minmax).Lat IsNot p(minmin).Lat Then ' a nontrivial segment
            If p(minmax).Lat <> p(minmin).Lat Then ' a nontrivial segment
                top += 1
                h.Insert(top, p(minmax))
            End If
            top += 1
            h.Insert(top, p(minmin))
            Return top + 1
        End If
        ' Get the indices of points with max x-coord and min|max y-coord
        Dim maxmin As Integer = 0
        Dim maxmax As Integer = n - 1

        Dim xmax As Double = p(n - 1).Lng
        For i = n - 2 To 0 Step -1
            If p(i).Lng <> xmax Then
                Exit For
            End If
        Next i
        maxmin = i + 1
        ' Compute the lower hull on the stack H
        top += 1
        h.Insert(top, p(minmin))
        i = minmax
        i += 1
        Do While i <= maxmin
            ' the lower line joins P[minmin] with P[maxmin]
            If (isLeft(p(minmin), p(maxmin), p(i)) >= 0) AndAlso (i < maxmin) Then
                i += 1
                Continue Do ' ignore P[i] above or on the lower line
            End If

            Do While top > 0 ' there are at least 2 points on the stack
                ' test if P[i] is left of the line at the stack top
                If isLeft(h(top - 1), h(top), p(i)) > 0 Then
                    Exit Do ' P[i] is a new hull vertex
                Else
                    top -= 1 ' pop top point off stack
                End If
            Loop
            top += 1
            h.Insert(top, p(i))
            i += 1
        Loop
        ' Next, compute the upper hull on the stack H above the bottom hull
        If maxmax <> maxmin Then ' if distinct xmax points
            top += 1
            h.Insert(top, p(maxmax))
        End If
        bot = top ' the bottom point of the upper hull stack
        i = maxmin
        i -= 1
        Do While i >= minmax
            ' the upper line joins P[maxmax] with P[minmax]
            If (isLeft(p(maxmax), p(minmax), p(i)) >= 0) AndAlso (i > minmax) Then
                i -= 1
                Continue Do ' ignore P[i] below or on the upper line
            End If
            Do While top > bot ' at least 2 points on the upper stack
                ' test if P[i] is left of the line at the stack top
                If isLeft(h(top - 1), h(top), p(i)) > 0 Then
                    Exit Do ' P[i] is a new hull vertex
                Else
                    top -= 1 ' pop top point off stack
                End If
            Loop
            top += 1
            h.Insert(top, p(i))
            i -= 1
        Loop
        If minmax <> minmin Then
            top += 1
            h.Insert(top, p(minmin))
        End If
        Dim sizeH As Integer = h.Count
        For i = top + 1 To sizeH - 1
            'h.Remove(top + 1)
            h.Remove(h.Item(top + 1))
        Next i
        Return top + 1
    End Function
End Class
 
Usage:

            Dim Hull As New Hull
            Hull.chainHull_2D(polygonPoints, polygonPoints.Count, H)

            Dim myTestPolygon As GMapPolygon
            myTestPolygon = New GMapPolygon(H, "SquarePolygon")
            Me.Layer_Polygon.Polygons.Add(myTestPolygon)

PolygonPoints is defined as New List of PointLatLng
Bye and thanks ;)
Franco
Sep 7, 2011 at 7:35 PM

Hi:

You propouse an algorithm for discovering if a point is left or right of a line (segment).

I had to do this, and use other code. I want to know (if someone could tell me) wich code is faster

This is your code:

 Public Function Compare(ByVal p1 As GMap.NET.PointLatLng, ByVal p2 As GMap.NET.PointLatLng) As Integer Implements System.Collections.Generic.IComparer(Of GMap.NET.PointLatLng).Compare
            Dim result As Integer = -2
            If p1.Lng > p2.Lng Then
                result = 1
            End If
            If p1.Lng < p2.Lng Then
                result = -1
            End If
            If p1.Lng = p2.Lng Then
                If p1.Lat > p2.Lat Then
                    result = 1
                End If
                If p1.Lat < p2.Lat Then
                    result = -1
                End If
                If p1.Lat = p2.Lat Then
                    result = 0
                End If
            End If
            Return result
        End Function
    End Class

    Private Function isLeft(ByVal p0 As PointLatLng, ByVal p1 As PointLatLng, ByVal p2 As PointLatLng) As Double
        'isLeft(): tests if a point is Left|On|Right of an infinite line.
        ' Input:  three points P0, P1, and P2
        ' Return: >0 for P2 left of the line through P0 and P1
        '		   =0 for P2 on the line
        '		   <0 for P2 right of the line
        'function isLeft( P0, P1, P2 ) {
        ' return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
        '}

        Return (p1.lng - p0.lng) * (p2.lat - p0.lat) - (p2.lng - p0.lng) * (p1.lat - p0.lat)
    End Function

And this is the code i use:

bearing_AB = GMapControl1.Manager.GetBearing(pointA, pointB)
bearing_CB = GMapControl1.Manager.GetBearing(puntoC, puntoB)
side = bearing_CB - bearing_AB
                  
if side > 0 then.... (it is on the right)

If side < 0 then.... (it is on the left)

 

Bye

Yeyo

Sep 13, 2011 at 3:53 PM

Did you get the external area to work ?

Do you know of a method to calculate the actual area selected as Sqr Meters/Kilometers ?