Sign in to follow this  
Jacob Roman

2D Mouse Selection [RESOLVED]

Recommended Posts

Didn't get much help at all over in the DirectX section, but since this is math related....yeah. How do I test to see if the mouse is within a 2D triangle shaped polygon, no matter what angle the triangle is? Remember, this is not 3D I'm talking about here, so don't go into the raytracing thing like the other thread I've made turned into. My thread was so hijacked. [Edited by - Jacob Roman on April 24, 2006 5:35:45 PM]

Share this post


Link to post
Share on other sites
What you're asking is, effectively, how to determine whether a point lies within a polygon or not?
Consider a frame of reference, where the origin coincides with the point of interest. For all vertices, find the angle of each vertex with the previous one with respect to that origin. Find the sum of those angles. E.g. let vi,i=1,...,n be the vertices and O be the origin, then find:
Sum[i=2,...,n][angle(vi,O,vi-1)] + angle(vn,O,v1).
The angle of two successive vertices, angle(vi,O,vi-1), will be the angle of vi from the origin, minus the angle of vi-1 from the origin.
Thus: angle(vi,O,vi-1) = atan2(vi.y, vi.x) - atan2(vi-1.y, vi-1.x)

If the total sum is +/- 2π then the point lies within the polygon. If it is zero, it lies outside the polygon. Don't forget to allow for some error in the calculations due to finite precision.
To implement this you'only need to know the order of the vertices (for either a CW or CCW traversal order)

edit:
If you'll be dealing with a lot of polygons and the atan2() seems a little too slow, you can also try this: Whenever you have to draw the polygons, also draw them flood-filled in a buffer (of the same dimensions with your viewport) using a single color as ID for each polygon. Whenever the user moves the mouse you'll have to update the currently "selected" polygon; Instead of going though all the fuss above, simply read the color at that position from the buffer and you'll get the ID of the polygon in no-time.

Share this post


Link to post
Share on other sites
If it really is a simple 2D point-in-triangle test you need, here's the algorithm I'd recommend:
for (size_t i = 0; i < 3; ++i)
if (perp_dot(v[(i + 1) % 3] - v[i]), p - v[i]) < 0.0f) {
return false;
}
}
return true;
If it doesn't work out of the box, try reversing the sign of the predicate. As usual though, no guarantee of correctness for code typed into gdnet :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by Jacob Roman
It's been awhile since I did this, but how do I find the angles of each of the vertices? And on top of that, with respect of the origin?


If the origin is the usual point with coordinates (0,0) then its angle from the origin is atan2(point.y - 0, point.x - 0) == atan2(point.y, point.x).
If you want the angle with respect to any other point (origin) you simply have to use the relative coordinates of "point" with respect to "origin"... Thus:
angle = atan2( point.y - origin.y, point.x-origin.x )
(don't forget that the result is measured in radians, not degrees)

Share this post


Link to post
Share on other sites
Regarding point-in-polygon tests, I would recommend not using the sum-of-angles method, given that there are numerous alternatives (such as the example I posted earlier) that are far more efficient and robust.

Share this post


Link to post
Share on other sites
Whoa guys, wait a minute. Why use atan() at all, or make it even more complicated, when in fact it was as simple as this:


Option Explicit

Private Type PointUDT
X As Double
Y As Double
End Type

Dim Points(2) As PointUDT

Private Function CheckTriangle(A As PointUDT, B As PointUDT, C As PointUDT, ByVal X As Double, ByVal Y As Double) As Boolean
If Determinant(A.X, A.Y, B.X, B.Y, X, Y) = True And Determinant(B.X, B.Y, C.X, C.Y, X, Y) = True And Determinant(C.X, C.Y, A.X, A.Y, X, Y) = True Then
CheckTriangle = True
Else
CheckTriangle = False
End If
End Function

Private Function Determinant(X1, Y1, X2, Y2, X3, Y3) As Boolean
Dim determ As Double
determ = (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1)

If determ >= 0 Then
Determinant = True
Else
Determinant = False
End If
End Function

Private Sub Form_Load()
Points(0).X = 0
Points(0).Y = 0

Points(1).X = 100
Points(1).Y = 0

Points(2).X = 50
Points(2).Y = 50

Me.AutoRedraw = True
Me.ScaleMode = 3
End Sub

Private Sub DrawTriangle(A As PointUDT, B As PointUDT, C As PointUDT)
Me.Line (A.X, A.Y)-(B.X, B.Y), vbRed
Me.Line (B.X, B.Y)-(C.X, C.Y), vbRed
Me.Line (C.X, C.Y)-(A.X, A.Y), vbRed
End Sub

Private Sub Rotate(Vertex() As PointUDT, Angle As Single)

Const PI As Single = 3.141592654

Dim I As Long

Dim Temp(2) As PointUDT

For I = 0 To 2

Temp(I).X = Vertex(I).X * Cos(PI * Angle / 180) - Vertex(I).Y * Sin(PI * Angle / 180)
Temp(I).Y = Vertex(I).X * Sin(PI * Angle / 180) + Vertex(I).Y * Cos(PI * Angle / 180)

Vertex(I).X = Temp(I).X
Vertex(I).Y = Temp(I).Y

Next I



End Sub

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
Points(0).X = 0
Points(0).Y = 0

Points(1).X = 100
Points(1).Y = 0

Points(2).X = 50
Points(2).Y = 50
Me.Cls
Rotate Points(), 35
If CheckTriangle(Points(0), Points(1), Points(2), X, Y) Then
Me.Circle (X, Y), 3, vbBlue
Else
Me.Circle (X, Y), 3, vbRed
End If
DrawTriangle Points(0), Points(1), Points(2)
Me.Refresh
End Sub



I got some excellent help over on another forum. Problem resolved. ;D

Share this post


Link to post
Share on other sites
Quote:
Original post by Jacob Roman
I got some excellent help over on another forum. Problem resolved. ;D
With all due respect, did you read the replies in this thread? The third reply down gives the exact same solution as you just posted above; furthermore I was very clear, both in stating it explicitly and offering an alternate solution, that no trig functions are necessary and in fact should be avoided.

The important thing is that you got the answer you needed, but I wouldn't be so quick to dismiss the help you got here - you were given the correct answer in the third reply to your original post.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jacob Roman
Yeah I've read the replies in this thread but couldn't understand on what to do really. I guess the source code provided to me spoke louder than words.
All right, but for the record I gave you source code as well - it's right there in my first reply.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jacob Roman
perp_dot doesn't exist in VB. ;)
It's a basic vector operation, just like the dot and cross products, and is a one-line function that you can easily write yourself no matter what language you're using :-)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this