Android Code Snippet Geo-Zone Determination (Point in Polygon)

Discussion in 'Code Snippets' started by Harris, May 19, 2015.

  1. ilan

    ilan Expert Licensed User

    the libgdx math functions are really good. i managed to create the polygons and also check if they are overlapping the problem is that
    if they are touching each other i get returned as they are overlapping.

    so i tried to scale 1 polygon and like this if they are only touching at their frames each other i get false (thats what i want)

    the problem is that the scaling of the vertices is relative to the origin of the polygon.

    so i have first to set the origin but thats not that simple :(

    i tried to get the lowest x,y and highest x,y and then get the center of the polygon

    Code:
    Dim centerx, centery As Float
                    centerx = lowx + ((highx-lowx)/
    2)
                    centery = lowy + ((highy-lowy)/
    2)
    the problem is that if i have a triangle the center is on the walls of the triangle and then the scaling is not done correct

    triangle1.png

    with a square it is ok

    rect1.png

    if i would take a more complex polygon i wont get the result i need.

    is there any way to check only if polygons are overlapping with a minimum area and not just laying next to each other?

    thanks
     
  2. ilan

    ilan Expert Licensed User

  3. JordiCP

    JordiCP Well-Known Member Licensed User

    Central point for a square works because of its simmetry. Also would work for regular polygons. Not sure if centroid would solve all cases

    If you want to make a smaller polygon contained in the "original one", I would follow this algorithm:

    • For each pair of vertices (Vi,Vj)
      • calculate the central point of the segment joining them. (Cij) and its slope (m)
      • Then take two perpendicular points to this one, at a small distance to this central point (Cij1,Cij2)
        • One of them will be inside and the other outside the polygon.
        • As you can calculate for each point if it is inside or outside the polygon, keep the one which falls inside and discard the other. Let's call it CijI
      • With this point, get a line with the same angle as the original, and keep it (CijI and m) for later use
    • Next
    • Once you have done this for all the lines, just calculate their intersecting points and you have the new polygon

    If you draw the steps, you will see that it is more or less what you are doing mentally when posting the triangle example
     
    lemonisdead and ilan like this.
  4. ilan

    ilan Expert Licensed User

    Thank you for your answer but i really dont understand the instruction how to get a copied scaled polygon inside it self.

    I have all vectors for the path of the polygon

    To make it simple:

    Lets take a triangle with 3 vectors (x/y)

    V1(100,100)
    V2(200,200)
    V3(100,200)

    What would be the centre of this triangle?
     
  5. ilan

    ilan Expert Licensed User

    ok this code is working for me so far:

    Code:
    Sub compute2DPolygonCentroid(vertices As ListAs String
        
    Dim centroid(2As Double
        
    Dim signedArea = 0.0 As Double
        
    Dim x0 = 0.0 As Double
        
    Dim y0 = 0.0 As Double
        
    Dim x1 = 0.0 As Double
        
    Dim y1 = 0.0 As Double
        
    Dim a = 0.0 As Double
       
        
    For i = 0 To vertices.Size - 1
            
    If i = vertices.Size - 1 Then
                
    Dim dbl() As Double = vertices.Get(i)
                
    Dim dbl2() As Double = vertices.Get(0)
                x0 = dbl(
    0)
                y0 = dbl(
    1)
                x1 = dbl2(
    0)
                y1 = dbl2(
    1)
                a = x0*y1 - x1*y0
                signedArea = signedArea + a
                centroid(
    0) = centroid(0) + ((x0 + x1)*a)
                centroid(
    1) = centroid(1) + ((y0 + y1)*a)   

                signedArea = signedArea * 
    0.5
                centroid(
    0) = centroid(0) / ((6.0*signedArea))
                centroid(
    1) = centroid(1) / ((6.0*signedArea))
            
    Else
                
    Dim dbl() As Double = vertices.Get(i)
                
    Dim dbl2() As Double = vertices.Get(i+1)
                x0 = dbl(
    0)
                y0 = dbl(
    1)
                x1 = dbl2(
    0)
                y1 = dbl2(
    1)
                a = x0*y1 - x1*y0
                signedArea = signedArea + a
                centroid(
    0) = centroid(0) + ((x0 + x1)*a)
                centroid(
    1) = centroid(1) + ((y0 + y1)*a)               
            
    End If
        
    Next
        
    Return centroid(0) & ":" & centroid(1)
    End Sub
    this gives me the center of the polygon and now i can set the origin and scale it correctly

    i have not tested it with more complex polygons, will let you know when i get to it :)

    thanx a lot guys
     
  6. ilan

    ilan Expert Licensed User

    dear @Harris, sorry that i turned your thread to this chaos :D
    i hope you forgive me :)
     
    Harris likes this.
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice