Polygon Intersection

[minitech]

How do you detect intersections between polygons?
(VB.NET 2005)

[wy125]

I haven't really looked into the matter much but you might find this article useful: http://gpwiki.org/index.php/Polygon_Collision

[minitech]

Ok, I looked at it, but...
1. It's to complicated for me.
2. I can't use a line, because VB can only use points, really.

[Atheist]

Ok, I looked at it, but...
1. It's to complicated for me.
2. I can't use a line, because VB can only use points, really.
1. Polygon intersection is not a simple thing.
2. But what is a line of not two points?

;)

Edit: You could also take a look at the links I posted in this thread http://www.vbforums.com/showthread.php?t=556888

[jemidiah]

I'd be very very surprised if this code hasn't been written. After a brief Google search I found http://www.cs.man.ac.uk/~toby/alan/software/, which has a .NET wrapper. It's overkill but the code should all be there in some language or another.

[minitech]

[QUOTE=Atheist]1. Polygon intersection is not a simple thing.
2. But what is a line of not two points?

;)

1. I know, but that is really complicated for VB.
2. Two points are two points, they represent a line sometimes, but seriously, it's very hard for me to calculate things like lines. I'm not a math genius, like everyone else here :bigyello:

[jemidiah]

I think that in general this problem is much more difficult than converting points into lines. I would be very happy to go through an algorithm for convex polygons, assuming as little as possible math-wise and including things like converting a couple of points to a line, though it would be lengthy, possibly not what you're after (maybe your polygons aren't always convex), and almost certainly less optimized than whatever you'd find online. Sorry :(

Oh, also the wiki linked earlier has the following edge intersection code. I haven't checked the reasoning or the code but I'd assume it's fine. The Vector2D object is in VB6 terms a UDT with x and y members. Note vector subtraction is used in the "b-a" portions. You could use this to check whether every possible pair of edges intersect, though that scales pretty horribly if you're using large polygons.


double determinant(Vector2D vec1, Vector2D vec2){
return vec1.x*vec2.y-vec1.y*vec2.x;
}

//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
double det=determinant(b-a,c-d);
double t=determinant(c-a,c-d)/det;
double u=determinant(b-a,c-a)/det;
if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION;
return a*(1-t)+t*b;
}

[minitech]

Heh...
I don't even know what those are, and I use VB, not C++.
:D

[jemidiah]

I guess my point is that the math required for this is much higher than what you've called "...really complicated for VB". Again I'd advise you to find something already written and muddle through fitting it to your needs, because this is not a trivial problem. But, below is the edge intersection code translated to VB6 (sorry, haven't had to switch to .NET yet).


Option Explicit

Private Type Vector2D
x As Single
y As Single
End Type

Private Function Vector2DSubtract(vec1 As Vector2D, vec2 As Vector2D) As Vector2D
Vector2DSubtract.x = vec1.x - vec2.x
Vector2DSubtract.y = vec1.y - vec2.y
End Function

Private Function determinant(vec1 As Vector2D, vec2 As Vector2D) As Double
determinant = vec1.x * vec2.y - vec1.y * vec2.x
End Function

'One edge is a-b, the other is c-d
Private Function edgeIntersection(a As Vector2D, b As Vector2D, c As Vector2D, d As Vector2D) As Vector2D
Dim det As Double, t As Double, u As Double
det = determinant(Vector2DSubtract(b, a), Vector2DSubtract(c, d))
t = determinant(Vector2DSubtract(c, a), Vector2DSubtract(c, d)) / det
u = determinant(Vector2DSubtract(b, a), Vector2DSubtract(c, a)) / det

If ((t < 0) Or (u < 0) Or (t > 1) Or (u > 1)) Then
MsgBox "no intersection"
Else
edgeIntersection.x = a.x * (1 - t) + t * b.x
edgeIntersection.y = a.y * (1 - t) + t * b.y
End If
End Function

[krtxmrtz]

Some time ago I was trying to write an application for polygon clipping based on the Weiler-Atherton algorithm. However it became very difficult for me to deal with degenerate cases (i.e. vertices lying on one of the other polygon's sides, etc) so if you run the code you'll see that it fails in some cases.

As a matter of fact I also came across that link transcribed above by jemidiah and the wrapper dll worked like charm, so that's why I discontinued writing my own code.

However, the function for polygon intersection works quite satisfactorily. Only it is all written in VB6 and it can be messy due to the structures I've used, but if you study them closely maybe the code could be useful to you.