# 2D Mouse Selection [RESOLVED]

## Recommended Posts

Jacob Roman    120
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 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 on other sites
Jacob Roman    120
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?

##### Share on other sites
jyk    2094
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 on other sites
Quote:
 Original post by Jacob RomanIt'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 on other sites
jyk    2094
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 on other sites
Jacob Roman    120
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 ExplicitPrivate Type PointUDT    X As Double    Y As DoubleEnd TypeDim 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 IfEnd FunctionPrivate 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 IfEnd FunctionPrivate 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 = 3End SubPrivate 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), vbRedEnd SubPrivate 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 SubPrivate 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.RefreshEnd Sub

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

##### Share on other sites
jyk    2094
Quote:
 Original post by Jacob RomanI 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 on other sites
Jacob Roman    120
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.

##### Share on other sites
jyk    2094
Quote:
 Original post by Jacob RomanYeah 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 on other sites
Jacob Roman    120
perp_dot doesn't exist in VB. ;)

##### Share on other sites
jyk    2094
Quote:
 Original post by Jacob Romanperp_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 on other sites
Jacob Roman    120
I assumed it meant perpendicular dot product, but didn't know how to implement it. Just a regular dot product.