Polygon Vertices Intersection?

[cpatzer]

Does anybody have an efficient way of detecting if a polygons vertices intersect (non-simple polygon) given a series of points?

Thanks,

Christian

[NoteMe]

2D or 3D?

[cpatzer]

2D, sorry.

[NoteMe]

If this is a pure math question, here is a paper for you.

http://wscg.zcu.cz/wscg2004/Papers_2004_Full/B83.pdf



If you are trying to do this for a game or something, and you are using BitBlt, or DDraw or something there is much nicer ways to do it.




ØØ

[cpatzer]

I am not a huge math or geometry buff and just need a simple code example be it VB C# C++ or whatever that will allow me to calculate when two lines of a polygon intersect.

I can break it up into lines and interogate the x,y coordinates I suppose:

    Private Structure line
        Dim StartPoint As PointF
        Dim EndPoint As PointF
    End Structure


            Dim Lines() As line
            For i As Integer = 0 To num
                If i < num Then
                    ReDim Preserve Lines(i)
                    Lines(i) = New line
                    Lines(i).StartPoint = New PointF(Pts(i).X, Pts(i).Y)
                    Lines(i).EndPoint = New PointF(Pts(i + 1).X, Pts(i + 1).Y)
                Else
                    ReDim Preserve Lines(i)
                    Lines(i) = New line
                    Lines(i).StartPoint = New PointF(Pts(i).X, Pts(i).Y)
                    Lines(i).EndPoint = New PointF(Pts(0).X, Pts(0).Y)
                End If
            Next

            Dim LinesIntersect As Boolean = False
            For Each FirstLine As line In Lines
                For Each SecondLine As line In Lines
                    'do comparisions from first line to second line
                Next
            Next

I just thought there might be a more elegant algorithm.

Thanks.

[cpatzer]

This post finished my code:

http://www.vbforums.com/showthread.p...29#post1951829

incombination with this.

            Dim li As Boolean = False
            For Each FirstLine As line In Lines
                For Each SecondLine As line In Lines
                    If MS_INTERSECT(FirstLine.StartPoint, FirstLine.EndPoint, SecondLine.StartPoint, SecondLine.EndPoint) Then
                        li = True
                    End If
                Next
            Next
            If li Then
                Return 0
            End If

Thanks.