Author Topic: Harder-than-it-looks math problem  (Read 1636 times)

0 Members and 1 Guest are viewing this topic.

This topic contains a post which is marked as Best Answer. Press here if you would like to see it.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1028
  • Savage
    • WFBarnes
Harder-than-it-looks math problem
« on: June 17, 2020, 01:13:09 PM »
This sounds easy, but the devil is in the details. I wanna see people stab at this problem and I know some of you can't resist...

Suppose I hand you the three XY coordinates of three points that make a triangle. If I give you a fourth XY point, is that point located inside the triangle or outside?

Answer in code.
« Last Edit: June 17, 2020, 01:17:26 PM by STxAxTIC »
The most powerful optimization technique in any programmer’s toolbox is to do nothing.

Offline Ashish

  • Forum Resident
  • Posts: 652
  • Burning Alone
Re: Harder-than-it-looks math problem
« Reply #1 on: June 17, 2020, 01:20:30 PM »
I think I dealed with this stuff when I posted space filling with polygons in program section https://www.qb64.org/forum/index.php?topic=2515
« Last Edit: June 17, 2020, 01:22:18 PM by Ashish »
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials

Offline Qwerkey

  • Forum Resident
  • Posts: 736
Re: Harder-than-it-looks math problem
« Reply #2 on: June 17, 2020, 01:41:11 PM »
No matter that Ashish (along with others?) has already solved this.  This looks an irresistible problem for a non-mathematician.  I think that you have defined my activity for tomorrow.

Offline MasterGy

  • Forum Regular
  • Posts: 132
  • people lie, math never lies
Re: Harder-than-it-looks math problem
« Reply #3 on: June 17, 2020, 01:44:24 PM »
That's a good question. That's exactly what I dealt with recently. (Philipines and the Resistors # 2)
I researched for a long time before I succeeded.


3d-Triangle : a,b,c   
3d-platoon  : p,q
(indexs : 1-x , 2-y , 3-z)

D1 = b(2) * c(3) - b(3) * c(2) - a(2) * c(3) + a(3) * c(2) + a(2) * b(3) - a(3) * b(2)
D2 = b(1) * c(3) - b(3) * c(1) - a(1) * c(3) + a(3) * c(1) + a(1) * b(3) - a(3) * b(1)
D3 = b(1) * c(2) - b(2) * c(1) - a(1) * c(2) + a(2) * c(1) + a(1) * b(2) - a(2) * b(1)

D = a(1) * (b(2) * c(3) - b(3) * c(2)) - a(2) * (b(1) * c(3) - b(3) * c(1)) + a(3) * (b(1) * c(2) - b(2) * c(1))

A = -(p(1) * D1 + p(2) * D2 + p(3) * D3 - D)
B = (q(1) - p(1)) * D1 + (q(2) - p(2)) * D2 + (q(3) - p(3)) * D3




if B = 0, then the triangle and the plane of the section are parallel to each other


intersection point: A / B
proportionally between points p and q


so: if A / B> = 0 and A / B <= 1, then the triangle ABC contains the section PQ


the thing works, do it, if someone is making a 3d game, this code might come in handy
« Last Edit: June 17, 2020, 01:55:05 PM by MasterGy »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1028
  • Savage
    • WFBarnes
Re: Harder-than-it-looks math problem
« Reply #4 on: June 17, 2020, 04:46:40 PM »
I figured this would have been hit already. Nice work boys.

The question came up in discord lately and this is what I decided on:

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(800, 600, 32)
  2.  
  3. TYPE Vector
  4.     x AS DOUBLE
  5.     y AS DOUBLE
  6.  
  7. TYPE Triangle
  8.     p1 AS Vector ' corner coordinates
  9.     p2 AS Vector
  10.     p3 AS Vector
  11.  
  12. DIM TestTriangle AS Triangle
  13. DIM TestParticle AS Vector
  14.  
  15. TestTriangle.p1.x = 150
  16. TestTriangle.p1.y = 0
  17. TestTriangle.p2.x = 0
  18. TestTriangle.p2.y = 100
  19. TestTriangle.p3.x = -150
  20. TestTriangle.p3.y = -100
  21.  
  22.  
  23.         x0 = _MOUSEX
  24.         y0 = _MOUSEY
  25.         x0 = (x0 - _WIDTH / 2)
  26.         y0 = (-y0 + _HEIGHT / 2)
  27.         TestParticle.x = x0
  28.         TestParticle.y = y0
  29.     LOOP
  30.  
  31.     CALL DrawTriangle(TestTriangle)
  32.     CALL cpset(TestParticle.x, TestParticle.y, _RGBA(255, 255, 255, 255))
  33.     CALL PointInsideTriangle(TestTriangle, TestParticle)
  34.  
  35.     _DISPLAY
  36.     _LIMIT 30
  37.  
  38.  
  39. SUB PointInsideTriangle (tr AS Triangle, p AS Vector)
  40.     DIM s12inside AS INTEGER
  41.     DIM s23inside AS INTEGER
  42.     DIM s31inside AS INTEGER
  43.     DIM dz AS Vector
  44.     DIM ta AS Vector
  45.     ' side 12
  46.     dz.x = p.x - tr.p1.x
  47.     dz.y = p.y - tr.p1.y
  48.     ta.x = tr.p2.x - tr.p1.x
  49.     ta.y = tr.p2.y - tr.p1.y
  50.     IF CrossProduct(ta, dz) > 0 THEN s12inside = 1 ELSE s12inside = 0
  51.     ' side 23
  52.     dz.x = p.x - tr.p2.x
  53.     dz.y = p.y - tr.p2.y
  54.     ta.x = tr.p3.x - tr.p2.x
  55.     ta.y = tr.p3.y - tr.p2.y
  56.     IF CrossProduct(ta, dz) > 0 THEN s23inside = 1 ELSE s23inside = 0
  57.     ' side 31
  58.     dz.x = p.x - tr.p3.x
  59.     dz.y = p.y - tr.p3.y
  60.     ta.x = tr.p1.x - tr.p3.x
  61.     ta.y = tr.p1.y - tr.p3.y
  62.     IF CrossProduct(ta, dz) > 0 THEN s31inside = 1 ELSE s31inside = 0
  63.     IF s12inside = 1 AND s23inside = 1 AND s31inside = 1 THEN
  64.         LOCATE 1, 1: PRINT "inside"
  65.     ELSE
  66.         LOCATE 1, 1: PRINT "      "
  67.     END IF
  68.  
  69. FUNCTION CrossProduct (a AS Vector, b AS Vector)
  70.     CrossProduct = a.x * b.y - b.x * a.y
  71.  
  72. SUB DrawTriangle (t AS Triangle)
  73.     CALL cline(t.p1.x, t.p1.y, t.p2.x, t.p2.y, _RGBA(255, 255, 255, 255))
  74.     CALL cline(t.p2.x, t.p2.y, t.p3.x, t.p3.y, _RGBA(255, 255, 255, 255))
  75.     CALL cline(t.p3.x, t.p3.y, t.p1.x, t.p1.y, _RGBA(255, 255, 255, 255))
  76.  
  77. SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
  78.     LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
  79.  
  80. SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
  81.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
  82.  
The most powerful optimization technique in any programmer’s toolbox is to do nothing.

Offline Qwerkey

  • Forum Resident
  • Posts: 736
Re: Harder-than-it-looks math problem
« Reply #5 on: June 18, 2020, 04:14:00 AM »
So, this will be my approach:  In triangle ABC, with angles alpha, beta and gamma, if the point is inside the triangle it forms triangles with angles alpha', beta' and gamma'.  Here the condition alpha' + beta' + gamma' = 2pi is met.  Outside, alpha' + beta' + gamma' < 2pi.  So I will code for this condition.  When I've completed, I'll check with the existing solutions and this will make an interesting InForm project (I may be some time).
 


Later edit:  Tested my condition and it seems to work.  So will now slog on with the coding.
In the meantime, you might like to try my bit of trial code. Vertices%(3, 0) and Vertices%(3, 1) are the x- & y- of the test position.  You can manually change the values to put it inside or outside and see the difference in the printed result: when this is negative (over and above calculation errors), the point is outside.  The final code will give explanations of what the calculations are.
Code: QB64: [Select]
  1. 'Is a point inside or outside a triangle? (problem set by STxAxTIC)
  2.  
  3. CONST SmallErr# = 1E-11
  4.  
  5. DIM Vertices%(3, 1)
  6.  
  7. Vertices%(0, 0) = 10
  8. Vertices%(0, 1) = 420
  9. Vertices%(1, 0) = 600
  10. Vertices%(1, 1) = 150
  11. Vertices%(2, 0) = 690
  12. Vertices%(2, 1) = 440
  13. Vertices%(3, 0) = 520
  14. Vertices%(3, 1) = 165
  15.  
  16. SCREEN _NEWIMAGE(700, 500, 32)
  17.  
  18. LINE (Vertices%(0, 0), Vertices%(0, 1))-(Vertices%(1, 0), Vertices%(1, 1))
  19. LINE (Vertices%(1, 0), Vertices%(1, 1))-(Vertices%(2, 0), Vertices%(2, 1))
  20. LINE (Vertices%(2, 0), Vertices%(2, 1))-(Vertices%(0, 0), Vertices%(0, 1))
  21.  
  22. LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(0, 0), Vertices%(0, 1)), _RGB32(255, 0, 0)
  23. LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(1, 0), Vertices%(1, 1)), _RGB32(255, 0, 0)
  24. LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(2, 0), Vertices%(2, 1)), _RGB32(255, 0, 0)
  25.  
  26. A# = SideLength#(Vertices%(0, 0), Vertices%(0, 1), Vertices%(2, 0), Vertices%(2, 1))
  27. B# = SideLength#(Vertices%(1, 0), Vertices%(1, 1), Vertices%(0, 0), Vertices%(0, 1))
  28. C# = SideLength#(Vertices%(2, 0), Vertices%(2, 1), Vertices%(1, 0), Vertices%(1, 1))
  29.  
  30. D# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(1, 0), Vertices%(1, 1))
  31. E# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(2, 0), Vertices%(2, 1))
  32. F# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(0, 0), Vertices%(0, 1))
  33.  
  34. Alpha# = Angle#(A#, B#, C#)
  35. Beta# = Angle#(B#, C#, A#)
  36. Gamma# = Angle#(C#, A#, B#)
  37.  
  38. AlphaDash# = Angle#(A#, E#, F#)
  39. BetaDash# = Angle#(B#, D#, F#)
  40. GammaDash# = Angle#(C#, D#, E#)
  41.  
  42. PRINT AlphaDash# + BetaDash# + GammaDash# - _PI(2)
  43.  
  44.     _LIMIT 30
  45.  
  46. FUNCTION SideLength# (X1#, Y1#, X2#, Y2#)
  47.     SideLength# = SQR((X1# - X2#) * (X1# - X2#) + (Y1# - Y2#) * (Y1# - Y2#))
  48.  
  49. FUNCTION Angle# (L1#, L2#, L3#)
  50.     Angle# = _ACOS(((L2# * L2#) + (L3# * L3#) - (L1# * L1#)) / (2 * L2# * L3#))
  51.  
« Last Edit: June 18, 2020, 06:13:52 AM by Qwerkey »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1028
  • Savage
    • WFBarnes
Re: Harder-than-it-looks math problem
« Reply #6 on: June 18, 2020, 08:57:56 AM »
Hmmmmm I like that approach. To keep the primed variables from measuring the wrong angle you can force them to be less than pi. Pretty cool, keep us posted if you see it all the way through.
The most powerful optimization technique in any programmer’s toolbox is to do nothing.

Offline Qwerkey

  • Forum Resident
  • Posts: 736
Re: Harder-than-it-looks math problem
« Reply #7 on: June 18, 2020, 10:24:43 AM »
I have done my bit of InForm coding - seems to work nicely:
https://www.qb64.org/forum/index.php?topic=2716.0
Let me know if you find any fatal flaws.
« Last Edit: June 18, 2020, 11:47:25 AM by Qwerkey »

Online SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3414
    • Steve’s QB64 Archive Forum
Re: Harder-than-it-looks math problem
« Reply #8 on: June 18, 2020, 12:21:45 PM »
And here's a solution without doing any fancy-pancy vector math and such:

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(640, 480, 32)
  2.  
  3. CONST DRAWIT = -1
  4.  
  5. PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 160, 150)
  6. PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 150, 50)
  7.  
  8. FUNCTION CheckTriangle (tx1, ty1, tx2, ty2, tx3, ty3, px, py)
  9.     d = _DEST: s = _SOURCE
  10.     temp = _NEWIMAGE(_WIDTH, _HEIGHT, 32)
  11.     _DEST temp: _SOURCE temp
  12.     COLOR _RGBA32(255, 255, 255, 100)
  13.     LINE (tx1, ty1)-(tx2, ty2)
  14.     LINE (tx2, ty2)-(tx3, ty3)
  15.     LINE (tx3, ty3)-(tx1, ty1)
  16.     txc = (tx1 + tx2 + tx3) / 3 'triangle x center
  17.     tyc = (ty1 + ty2 + ty3) / 3 'triangle y center
  18.     PAINT (txc, tyc)
  19.     _BLEND
  20.     PSET (px, py), _RGBA(255, 0, 0, 200)
  21.     p = POINT(px, py)
  22.     IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1
  23.     _DEST d: _SOURCE s
  24.     IF DRAWIT THEN
  25.         CLS
  26.         CIRCLE (px, py), 5, _RGBA(255, 0, 0, 200)
  27.         _PUTIMAGE (0, 0), temp, d
  28.     END IF
  29.     _FREEIMAGE temp

We're basically just doing some simple blending to see if our point appears in the triangle, or not.

Often, if we're already drawing the objects to the screen, a simple method like this is faster and more efficient than doing a string of math calculations for us.  It's also inherently more intuitive for new programmers and children to understand -- to them it's as complex as saying, "Cut a triangle out of a sheet of paper, and toss a drop of ink at it.  Is the ink inside (or on) the triangle, or not?"   It turns the problem into a simple, visual solution, with very little reliance on math at all.
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Qwerkey

  • Forum Resident
  • Posts: 736
Re: Harder-than-it-looks math problem
« Reply #9 on: June 18, 2020, 12:37:30 PM »
... a solution without doing any fancy-pancy vector math and such:

Qwerkey: the renowed fancy-pancy mathematician of this site - not!!

Offline bplus

  • Forum Resident
  • Posts: 6241
  • What could possibly go wrong?
Re: Harder-than-it-looks math problem
« Reply #10 on: June 18, 2020, 12:42:50 PM »
And here's a solution without doing any fancy-pancy vector math and such:

Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(640, 480, 32)
  2.  
  3. CONST DRAWIT = -1
  4.  
  5. PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 160, 150)
  6. PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 150, 50)
  7.  
  8. FUNCTION CheckTriangle (tx1, ty1, tx2, ty2, tx3, ty3, px, py)
  9.     d = _DEST: s = _SOURCE
  10.     temp = _NEWIMAGE(_WIDTH, _HEIGHT, 32)
  11.     _DEST temp: _SOURCE temp
  12.     COLOR _RGBA32(255, 255, 255, 100)
  13.     LINE (tx1, ty1)-(tx2, ty2)
  14.     LINE (tx2, ty2)-(tx3, ty3)
  15.     LINE (tx3, ty3)-(tx1, ty1)
  16.     txc = (tx1 + tx2 + tx3) / 3 'triangle x center
  17.     tyc = (ty1 + ty2 + ty3) / 3 'triangle y center
  18.     PAINT (txc, tyc)
  19.     _BLEND
  20.     PSET (px, py), _RGBA(255, 0, 0, 200)
  21.     p = POINT(px, py)
  22.     IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1
  23.     _DEST d: _SOURCE s
  24.     IF DRAWIT THEN
  25.         CLS
  26.         CIRCLE (px, py), 5, _RGBA(255, 0, 0, 200)
  27.         _PUTIMAGE (0, 0), temp, d
  28.     END IF
  29.     _FREEIMAGE temp

We're basically just doing some simple blending to see if our point appears in the triangle, or not.

Often, if we're already drawing the objects to the screen, a simple method like this is faster and more efficient than doing a string of math calculations for us.  It's also inherently more intuitive for new programmers and children to understand -- to them it's as complex as saying, "Cut a triangle out of a sheet of paper, and toss a drop of ink at it.  Is the ink inside (or on) the triangle, or not?"   It turns the problem into a simple, visual solution, with very little reliance on math at all.

Ha! I knew this was coming from Steve :) what took so long?

@SMcNeill  how did you figure the point value for intersecting triangle? here:
Code: QB64: [Select]
  1. IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1

I suspect that takes some fansy-pansy tech knowledge too ;-))
or maybe you tested a known point and took a reading of the value and translated that back into _RGBA32 arguments.

I do think math would be faster than PAINTing large triangles and drawing things on the side. Maybe you could setup a timed test. It IS easier to understand no doubt in my mind.
« Last Edit: June 18, 2020, 01:02:26 PM by bplus »

Online SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3414
    • Steve’s QB64 Archive Forum
Re: Harder-than-it-looks math problem
« Reply #11 on: June 18, 2020, 03:38:18 PM »
Quote
I suspect that takes some fansy-pansy tech knowledge too ;-))
or maybe you tested a known point and took a reading of the value and translated that back into _RGBA32 arguments.

That's the exact trick.  Just plot a normal point for the triangle, then PSET any point in it.  Read that value and now you have your_RGBA values to compare it against.  ;D
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1028
  • Savage
    • WFBarnes
Re: Harder-than-it-looks math problem
« Reply #12 on: June 18, 2020, 05:10:46 PM »
Emphasis on "math problem"... Yes, the preskool solution is there for those who... Nevermind... Nice analysis steve
The most powerful optimization technique in any programmer’s toolbox is to do nothing.

Offline Pete

  • Forum Resident
  • Posts: 2513
  • Cuz I sez so, varmint!
Re: Harder-than-it-looks math problem
« Reply #13 on: June 18, 2020, 05:38:33 PM »
The answer is 4.

Offline Qwerkey

  • Forum Resident
  • Posts: 736
Re: Harder-than-it-looks math problem
« Reply #14 on: June 19, 2020, 04:18:54 AM »
I hope that I have now corrected the error in mine, quod vide.