Harder-than-it-looks math problem

[luke]

@SMcNeill why do you the PSET at all? Wouldn't it just be easier to check the POINT directly:

Code: [Select]

FUNCTION CheckTriangle (tx1, ty1, tx2, ty2, tx3, ty3, px, py)
    DIM p AS _UNSIGNED LONG, r AS _UNSIGNED LONG
    d = _DEST: s = _SOURCE
    temp = _NEWIMAGE(_WIDTH, _HEIGHT, 32)
    _DEST temp: _SOURCE temp
    COLOR _RGB(255, 255, 255)
    _DONTBLEND
    LINE (tx1, ty1)-(tx2, ty2)
    LINE (tx2, ty2)-(tx3, ty3)
    LINE (tx3, ty3)-(tx1, ty1)
    txc = (tx1 + tx2 + tx3) / 3 'triangle x center
    tyc = (ty1 + ty2 + ty3) / 3 'triangle y center
    PAINT (txc, tyc)
    CheckTriangle = POINT(px, py) > 0

    _DEST d: _SOURCE s
    IF DRAWIT THEN
        CLS
        CIRCLE (px, py), 5, _RGB(255, 0, 0)
        _PUTIMAGE (0, 0), temp, d
    END IF
    _FREEIMAGE temp
END FUNCTIONOr am I missing something?

[Qwerkey]

Thanks, QB64, for _ACOS() additional to the restrictive ATN() of QuickBasic.  My method uses The Law of Cosines to find angles from triangle side lengths.

To keep the primed variables from measuring the wrong angle you can force them to be less than pi.

The beauty of _ACOS() is that it always returns the angle in the range 0 - pi, and so needs no code adjusters.
Next time, I'll have a slightly harder trig puzzle!

[bplus]

Nice one @luke  I suspected there was easier way to Steve's method but blundered, my mind probably too cluttered with worries about my gambling problem with Blackjack ;-))

Here is key to the simplest solution (so far), well @MasterGy has fewest Lines of Code (I think, don't see working demo) but why does that work? assuming it does, knowing MasterGy I think I am safe ;-))
I am also assuming Luke's also works because..., well you know!
BTW I am also assuming STx's works for same reason. :)
I only tried @SMcNeill 's and know it works as far as it went, but why I ask the PAINT question at the end of this post.

Key to simple math solution:

Code: QB64: [Select]

1. FUNCTION PtInteriorOfAngleTF (ox1, oy1, ax1, ay1, ax2, ay2, ptx, pty)
2.     a1 = atan360(_ATAN2(ay1 - oy1, ax1 - ox1)) ' angle of one arm from origin of angle
3.     a2 = atan360(_ATAN2(ay2 - oy1, ax2 - ox1)) ' angle of the other arm from origin of angle
4.     ap = atan360(_ATAN2(pty - oy1, ptx - ox1)) ' angle of point from same origin
5.     IF a2 < a1 THEN SWAP a2, a1 'make a1 the samller of the two angles for test fit of point
6.     IF ap >= a1 AND ap <= a2 THEN PtInteriorOfAngleTF = -1 ' if point angle is inside or on the 2 arm angles then point is in or on.
7.  
8.     'PRINT a1, a2, ap, PtInteriorOfAngleTF 'debug
9.     'I can't believe all the blunders I've made putting this so simple an idea together!!!
10. END FUNCTION
11.  
12. FUNCTION atan360 (ra) 'convert radian angle from _ATAN2()  to guaranteed positive angle
13.     atan360 = _R2D(ra + _PI(2))
14. END FUNCTION
15.  

Here it is in action to the triangle problem:

Code: QB64: [Select]

1. _TITLE "Interior of an Angle" ' B+ 2020-06-09  Math Geometry
2. ' Interesting problem posed by STx 2020-06-17
3. ' https://www.qb64.org/forum/index.php?topic=2714.0
4.  
5. 'got me thinking how I might solve it here is what I came uo with
6. ' to save time using Steve's code to problem setup, so I check same as his for starters
7.  
8. SCREEN _NEWIMAGE(640, 480, 32)
9. px = 160: py = 150
10. PRINT "Test Interior"
11. tf = PtInteriorOfTriangleTF(100, 100, 200, 100, 300, 300, px, py)
12. IF tf THEN PRINT "Pt ("; px; ","; py; ") is in or on." ELSE PRINT "Pt ("; px; ","; py; ") is Out."
13. SLEEP
14. CLS
15. px = 150: py = 50
16. PRINT "Test Exterior"
17. tf = PtInteriorOfTriangleTF(100, 100, 200, 100, 300, 300, px, py)
18. IF tf THEN PRINT "Pt ("; px; ","; py; ") is in or on." ELSE PRINT "Pt ("; px; ","; py; ") is Out."
19. SLEEP
20. CLS
21.  
22. 'try some more borderline cases
23. ' pt is corner of tringle
24. PRINT "Test triangle point"
25. px = 100: py = 100
26. tf = PtInteriorOfTriangleTF(100, 100, 200, 100, 300, 300, px, py)
27. IF tf THEN PRINT "Pt ("; px; ","; py; ") is in or on." ELSE PRINT "Pt ("; px; ","; py; ") is Out."
28. SLEEP
29. CLS
30. 'point is on line between 2 points
31. px = 150: py = 100
32. PRINT "Test Border line"
33. tf = PtInteriorOfTriangleTF(100, 100, 200, 100, 300, 300, px, py)
34. IF tf THEN PRINT "Pt ("; px; ","; py; ") is in or on." ELSE PRINT "Pt ("; px; ","; py; ") is Out."
35. SLEEP
36.  
37. 'oh let's just test everywhere!
38. _TITLE "Testing random points on screen, press escape to quit any other for another test..."
39. WHILE _KEYDOWN(27) = 0
40.     CLS
41.     px = RND * 640: py = RND * 480
42.     tf = PtInteriorOfTriangleTF(100, 100, 200, 100, 300, 300, px, py)
43.     IF tf THEN PRINT "Pt ("; px; ","; py; ") is in or on." ELSE PRINT "Pt ("; px; ","; py; ") is Out."
44.     SLEEP
45. WEND
46. SYSTEM
47.  
48.  
49. SUB drawSituation (tx1, ty1, tx2, ty2, tx3, ty3, px, py) '3 points of triangle and test pt yellow
50.     LINE (tx1, ty1)-(tx2, ty2)
51.     LINE (tx2, ty2)-(tx3, ty3)
52.     LINE (tx3, ty3)-(tx1, ty1)
53.     CIRCLE (px, py), 3, &HFFFFFF00
54. END SUB
55.  
56. FUNCTION PtInteriorOfTriangleTF (tx1, ty1, tx2, ty2, tx3, ty3, px, py)
57.     drawSituation tx1, ty1, tx2, ty2, tx3, ty3, px, py
58.     IF PtInteriorOfAngleTF(tx1, ty1, tx2, ty2, tx3, ty3, px, py) THEN
59.         IF PtInteriorOfAngleTF(tx2, ty2, tx1, ty1, tx3, ty3, px, py) THEN
60.             IF PtInteriorOfAngleTF(tx3, ty3, tx1, ty1, tx2, ty2, px, py) THEN
61.                 PtInteriorOfTriangleTF = -1
62.             END IF
63.         END IF
64.     END IF
65. END FUNCTION
66.  
67. FUNCTION PtInteriorOfAngleTF (ox1, oy1, ax1, ay1, ax2, ay2, ptx, pty)
68.     a1 = atan360(_ATAN2(ay1 - oy1, ax1 - ox1))
69.     a2 = atan360(_ATAN2(ay2 - oy1, ax2 - ox1))
70.     ap = atan360(_ATAN2(pty - oy1, ptx - ox1))
71.     IF a2 < a1 THEN SWAP a2, a1
72.     IF ap >= a1 AND ap <= a2 THEN PtInteriorOfAngleTF = -1
73.  
74.     'PRINT a1, a2, ap, PtInteriorOfAngleTF 'debug
75.     'I can't believe all the blunders I've made putting this so simple an idea together!!!
76. END FUNCTION
77.  
78. FUNCTION atan360 (ra) 'convert radian angle from _ATAN2()  to guaranteed positive angle
79.     atan360 = _R2D(ra + _PI(2))
80. END FUNCTION
81.  
82. 'FUNCTION CheckTriangle (tx1, ty1, tx2, ty2, tx3, ty3, px, py)
83.  
84. 'thanks SMcNeill for this simple to understand method
85. ' BUT I think I have simpler! ;-))
86.  
87.  
88. '    DIM p AS _UNSIGNED LONG, r AS _UNSIGNED LONG
89. '    d = _DEST: s = _SOURCE
90. '    temp = _NEWIMAGE(_WIDTH, _HEIGHT, 32)
91. '    _DEST temp: _SOURCE temp
92. '    COLOR _RGBA32(255, 255, 255, 100)
93. '    _DONTBLEND
94. '    LINE (tx1, ty1)-(tx2, ty2)
95. '    LINE (tx2, ty2)-(tx3, ty3)
96. '    LINE (tx3, ty3)-(tx1, ty1)
97. '    txc = (tx1 + tx2 + tx3) / 3 'triangle x center
98. '    tyc = (ty1 + ty2 + ty3) / 3 'triangle y center
99. '    PAINT (txc, tyc)
100. '    _BLEND
101. '    PSET (px, py), _RGBA(255, 0, 0, 200)
102. '    p = POINT(px, py)
103. '    IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1
104. '    _DEST d: _SOURCE s
105. '    IF DRAWIT THEN
106. '        CLS
107. '        CIRCLE (px, py), 5, _RGBA(255, 0, 0, 200)
108. '        _PUTIMAGE (0, 0), temp, d
109. '    END IF
110. '    _FREEIMAGE temp
111. 'END FUNCTION
112.  

It is both simple to understand AND mathematical the Intersect of 2 Heavenly Realms.

In English, it just says that a Point Interior to a Triangle has to be Interior to each of it's 3 Interior Angles.

Does PAINT consider a Point On the Triangle in it? Anyway this code considers On or In as opposed to Exterior only.

EDIT: add more comments for key function

[STxAxTIC]

Problem with non vector methods is you're stuck on screen. Let's tilt the x and y axes both by say, whatever 31 degrees. How does your solution change?

All my solution does is require that the triangle be drawn with with the right hand rule, and the criteria for being inside is whether or not the stray point occurs to the left of the vector, that's all it does. No explicit coordinate system means this works for any orientation of both the coordinates and the triangle.

[STxAxTIC]

Wow sorry if I marked that as best answer for a while, don't forum and drive, kids.

[bplus]

Problem with non vector methods is you're stuck on screen. Let's tilt the x and y axes both by say, whatever 31 degrees. How does your solution change?

All my solution does is require that the triangle be drawn with with the right hand rule, and the criteria for being inside is whether or not the stray point occurs to the left of the vector, that's all it does. No explicit coordinate system means this works for any orientation of both the coordinates and the triangle.

Here we go again with the stupid right hand rule! a 3D property when discussing 2D triangles or shall we talk about triangles on spheres?

A point interior of an angle is not dependent on axis orientation you know that, all the way down to Topology, so I can talk surface of sphere.

In English, it just says that a Point Interior to a Triangle has to be Interior to each of it's 3 Interior Angles.

My solution depends solely on angles between points.

[STxAxTIC]

There are few instances here when someone so blatantly can't see the point. Don't be at the center of it man, it's not usually you.

[Pete]

Of course he can't "see" the point. A point is zero-dimensional space. You really need to take my Physic 101 Sems, Bill. :D

Pete

[SMcNeill]

@SMcNeill why do you the PSET at all? Wouldn't it just be easier to check the POINT directly

It would be.  I just added the PSET as a physical representation of the problem.  The code to draw the visible circle to highlight the point came later, as my poor eyes just couldn't pick up on that single pixel very easily.

Does PAINT consider a Point On the Triangle in it? Anyway this code considers On or In as opposed to Exterior only.

My example counts a point ON the triangle as being IN it.  If that's not desirable for your needs, just redraw the triangles edge a separate color after the fill has did its job.

Problem with non vector methods is you're stuck on screen. Let's tilt the x and y axes both by say, whatever 31 degrees. How does your solution change?

If you're dealing with 3 dimensional triangles and points, use the GL commands to draw it and check the color value.  The solution really doesn't need to change at all.  People have displayed 3d graphics on 2d screens for ages now.  Didn't you know that??

[STxAxTIC]

Nope, I have a lot to learn from you about math apparently. Can I start pitching my questions right to you?

[STxAxTIC]

Actually don't answer, I will pose the same question in 3d next chance I get, that will at least give a chance for bplus to become aminus. I don't know what yer gonna do Steve...

[bplus]

Dang this is harder than I thought, didn't test enough cases (only one, blah).

Made one fix that repaired test reports for most triangles but still am getting false negatives. I know the theory is right just not executed well enough yet.

[Ashish]

Ok.. Here's my approach. It is based on areas.

EDIT : Code Updated. Now press SpaceBar to generate new triangle

Code: QB64: [Select]

1. TYPE vec2
2.     x AS INTEGER
3.     y AS INTEGER
4. END TYPE
5. _TITLE "Move mouse into triangle, it will become red"
6. SCREEN _NEWIMAGE(600, 600, 32)
7.  
8. DIM p(2) AS vec2, m AS vec2
9. p(0).x = INT(RND * 600): p(0).y = INT(RND * 600)
10. p(1).x = INT(RND * 600): p(1).y = INT(RND * 600)
11. p(2).x = INT(RND * 600): p(2).y = INT(RND * 600)
12. red~& = _RGB(255, 0, 0)
13. white~& = _RGB32(255)
14. DO
15.     k$ = INKEY$
16.     CLS
17.     IF k$ = " " THEN
18.         p(0).x = INT(RND * 600): p(0).y = INT(RND * 600)
19.         p(1).x = INT(RND * 600): p(1).y = INT(RND * 600)
20.         p(2).x = INT(RND * 600): p(2).y = INT(RND * 600)
21.     END IF
22.     WHILE _MOUSEINPUT: WEND
23.     m.x = _MOUSEX: m.y = _MOUSEY
24.     IF insideTriangle(p(0), p(1), p(2), m) THEN COLOR red~& ELSE COLOR white~&
25.     FOR i = 0 TO 2 'draw triangle
26.         LINE (p(i).x, p(i).y)-(p((i + 1) MOD 3).x, p((i + 1) MOD 3).y)
27.     NEXT
28.     _DISPLAY
29.     _LIMIT 60
30. LOOP
31.  
32. 'p1,p2,p3 -> coordinates of triangle
33. 'N is the test point.
34. 'returns true if N is inside the triangle
35. FUNCTION insideTriangle (p1 AS vec2, p2 AS vec2, p3 AS vec2, N AS vec2)
36.     p_area& = triangleArea(p1, p2, N) + triangleArea(p1, N, p3) + triangleArea(N, p2, p3)
37.     insideTriangle = (ABS(triangleArea(p1, p2, p3) - p_area&) <= 3)
38. END FUNCTION
39. FUNCTION triangleArea& (p1 AS vec2, p2 AS vec2, p3 AS vec2)
40.     triangleArea& = 0.5 * ABS(p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y))
41. END FUNCTION
42.  

[STxAxTIC]

Ashish, you have made my day!!!

For those above who are terrified of vectors, this perfect solution contains the same calculation mine does, right down to the cross product of vectors --- except what Ashish just blessed us with is just so damn efficient and tight! A lovely lovely job. I think we'll all be answering to you as the QB64 president in a few short years.

[bplus]

Yeah well, looks like he only tested one triangle.

Oh that's clever though, the area of 3 little triangles with the point as a vertex has to equal the given triangle area.

To me that's just plain Geometry and no right hand rule in sight, LOL.