Android Question How find center of polygon

[yfleury]

Hi all,
I have a polygon on google map and I want to find center.

 

[Brian Dean]

This is a pretty simple algorithm. I have translated it from a desktop application and tested it with a couple of simple cases - it looks okay.

    Type point (x As Double, y As Double)


Private Sub signedArea(shape As List) As Double
    ' NB : This function can return negative values.
    Dim this, prev As point
    Dim i As Int
    Dim result As Double = 0.0
    If (shape.Size > 2) Then
        prev = shape.Get(shape.Size - 1)
        For i = 0 To shape.Size - 1
            this = shape.Get(i)
            result = result + (prev.x * this.y - this.x*prev.y)
            prev = this           
        Next
    End If
    Return result / 2
End Sub

Public Sub centroid(shape As List) As point
    Dim this, prev, result As point
    result.Initialize
    Dim x, y, f, a As Double
    Dim i, n As Int
    If (shape.Size > 2) Then
        n = shape.Size - 1
        prev = shape.Get(n)
        For i = 0 To n
            this = shape.Get(i)                    ' Pick the next point
            f = (prev.x * this.y) - (this.x * prev.y)
            x = x + (prev.x + this.x) * f
            y = y + (prev.y + this.y) * f
            prev = this
        Next
        a = signedArea(shape) * 6
        result.x = x / a
        result.y = y / a
    End If
    Return result
End Sub

I have made the algorithm for a polygon area a separate function because it is a useful one to know, but note that you normally take the abs(...) value of the result. The signed value is useful if you want to check the winding of a polygon, or calculate the centroid, as here.

Note also that if the polygon is self-intersecting (that is, it crosses itself) you are going to get mathematically correct but logically surprising results.

 

[emexes]

mathematically correct but logically surprising

too true, too often ?

 

[yfleury]

@Brian Dean I try your code today
I have some error (I comment your code below with error

Public Sub centroid(shape As List) As point
    Dim this, prev, result As point
    result.Initialize               ' -------------------------->  '(' expected.
    Dim x, y, f, a As Double
    Dim i, n As Int
    If (shape.Size > 2) Then
        n = shape.Size - 1
        prev = shape.Get(n)
        For i = 0 To n
            this = shape.Get(i)                    ' Pick the next point
            f = (prev.x * this.y) - (this.x * prev.y)
            x = x + (prev.x + this.x) * f
            y = y + (prev.y + this.y) * f
            prev = this
        Next
        a = signedArea(shape) * 6
        result.x = x / a       ' --------------------------> Property: X is readonly.
        result.y = y / a       ' --------------------------> Property: Y is readonly.
    End If
    Return result
End Sub

 

[keirS]

This is a pretty simple algorithm. I have translated it from a desktop application and tested it with a couple of simple cases - it looks okay.


Note also that if the polygon is self-intersecting (that is, it crosses itself) you are going to get mathematically correct but logically surprising results.

The centroid of a concave polygon can be outside the bounds of the polygon in which case the OP may want the visual center. If you want to stick a label in the in the center of the polygon then having the label outside the bounds of the polygon is not helpful. Calculating the visual center is not that easy as the fastest algorithm requires the implementation of a quad tree and a priority queue.

 

[yfleury]

Well is not simple.... I don't know if user of my app will create concave polygon, But it's a possible. Maybe I can put a label on top of polygon. That was a simple solution

 

[Brian Dean]

I have some error (I comment your code below with error

Did you remember to include the "Type" statement to define a "point". Anyway, I have attached a complete B4A project now. I originally wrote it in B4J so it a bit rough. Note that the result is shown only in the log.

A couple of other remarks - you can remove the "Sub signedArea" function altogether by moving this line to "Sub centroid(...)"

A = A + (prev.x * this.y - this.x * prev.y)

... and making an adjustment when dividing by the area later. Also @keirS is perfectly correct - this subroutine calculates the position of the centre of gravity of a polygon shape. There is not really an easy definition of what makes the "visual" centre of an irregular shape. If you put a label on top of a concave polygon you still have to decide where to position it. The CofG is usually a good place to start.

[Edit : sorry - forgot to attach the project]

 

[yfleury]

I Brian, I don't forget the TYPE in global

 

[yfleury]

It work now. I adapt your code for my list of latlnt

Thank Brian

Type Point have conflict with Point and I use latlnt
I know, I am not clear lol My mind is subjet to bug