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.php?p=1951829#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.