Android Question [SOLVED] GoogleMapsExtra polygon cross line

[yfleury]

Here 2 polygon. The right one, border cross another one.
How to detect this programaticaly?

 

[Erel]

If I understood correctly you want to know whether two edges of the polygon intersect. You can use this code to find intersections between two lines: https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

You can use it to check intersections between each edge and the other ones.

 

[TILogistic]

I only see a polygon.
that their lines cross
or not ?

I see 3 segments of lines crossing

Erel post is fine

 

[TILogistic]

Other:

Program to find line passing through 2 Points - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

 

[yfleury]

I take a look on all link. But it is too complicate for my knowledge to translate to b4a

 

[TILogistic]

are classes of languages (calculation of geometry) and you can execute, edit and copy.
and Translate to B4X

 

[yfleury]

Thanks @oparra But I am unable to translate that. I unknow how to do that. My java skill is 0/10

 

[TILogistic]

Tell me what are you really looking for?

And I'll see if we already have it in our classes in B4X.


regards

 

[TILogistic]

Indicates the points of the polygon (GoogleMapsExtra)


Latitude and longitude that make up the polygon.

The start point is equal to the end point of the polygon.

regards

 

[TILogistic]

Do you want to know the points of the segments (line) that intersect?

 

[yfleury]

I Just want a boolean if a segment cross another segment. If it true, I show a warning to user "Your polygon is bad because a segment is crossing another segment. Remake the polygon. "

 

[Brian Dean]

How are the vertices of your polygon stored? If they are held as a list of objects what are the objects?

 

[yfleury]

I have 2 lists, a list of latitude and a list of longitude

 

[Brian Dean]

Here is a possible solution. The following code will determine if two lines (eg edges in a polygon) intersect ...

' TRUE if line objects L1 and L2 self-intersect
Sub intersects(L1 As line, L2 As line) As Boolean
    Return (pointside(L1, L2.p0) <> (pointside(L1, L2.p1))) And (pointside(L2, L1.p0) <> (pointside(L2, L1.p1)))  
End Sub

' Determine on which side of line L point P lies
Sub pointside(L As line, P As point) As Int
    Dim a As Float
    a = ((L.p1.x - L.p0.x) * (P.y - L.p0.y)) - ((P.x - L.p0.x) * (L.p1.y - L.p0.y))
    If (a > 0) Then Return 1
    If (a < 0) Then Return -1
    Return 0
End Sub

The code uses Line and Point objects as defined in the next code segment. You will have to convert your lists of latitude and longitude values into lines. Start by combining the longitude-latitude pairs into x-y points, then convert the x-y points into lines ...

    Type point (x As Float, y As Float)
    Type line (p0 As point, p1 As point)
   
    . . . . .
    . . . . .
   
' Convert a list of point objects to a list of line objects
Sub makeLines(points As List) As List
    Dim result As List
    result.Initialize
    Dim p, oldP As point
    Dim first As Boolean = True
    For Each p As point In points
        If Not(first) Then
            result.Add(createLine(oldP, p))
        End If
        oldP = p
        first = False
    Next
    Return result
End Sub

Public Sub createLine (p0 As point, p1 As point) As line
    Dim L As line
    L.Initialize
    L.p0 = p0
    L.p1 = p1
    Return L
End Sub

Finally you have to test each line in the polygon against the other lines to determine if any intersect. Note that if the polygon has less than four points then no sides can intersect, and you must not test adjacent sides. The [validShape] routine below expects a list of point objects and builds these into a list of line objects.

' Return TRUE if the closed path represented by the list of point objects in [shape] do not self-intersect.
Sub validShape(shape As List) As Boolean
    If (shape.Size > 4) Then
        Dim result As Boolean = True
        Dim lines As List = makeLines(shape)
        Dim A, B As line
        Dim i, j As Int
        i = 0
      Do While result And (i < lines.Size - 2)
            A = lines.Get(i)
            For j = i + 2 To lines.Size - 2
                B = lines.Get(j)
              result = Not(intersects(A, B))
            Next
            i = i + 1  
        Loop
        Return result
    Else
        Return True
    End If
End Sub

I have had to adapt this code from code that I have used before, so I have not tested it thoroughly. Let me know if you run into any problems. Just a note; if you are going to work with polygons that have very, very many sides then there are better algorithms that this one.

 

[yfleury]

Thanks @Brian Dean I will test it this week

 

[klaus]

Or try this one, in the attached test project.
You may need to adapt it to your needs.

 

[Brian Dean]

@yfleury - As you are working with Lat/Lon values I suggest that you use Double variables for the point coordinates rather than Float, especially if you are working at metre precision rather than kilometres.

 

[yfleury]

@yfleury - As you are working with Lat/Lon values I suggest that you use Double variables for the point coordinates rather than Float, especially if you are working at metre precision rather than kilometres.

For segment A I have 2 points, each point have a Lat and lng (each is Double) I don't use LatLng variable.

Segment A Start at (lat1, lng1) stop at (lat2, lng2)
Segment B .....

 

[Brian Dean]

Don't worry - if you use my code just make this change ....

' Replace this line ...
' Type point (x As Float, y As Float)
' with this line ...
  Type point(x as Double, y as Double)

Sorry - I should have made that clear. Good luck.

 

[yfleury]

@Brian Dean I don't test your code. But thanks again. I bookmark it for later.

I test code from code from @klaus It work well and it is simple (only one sub) to implement it to my app.

Thanks to all