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

STxAxTIC · « **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.

Ashish · « **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

Qwerkey · « **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.

MasterGy · « **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

STxAxTIC · « **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]

SCREEN _NEWIMAGE(800, 600, 32)
 
TYPE Vector
    x AS DOUBLE
    y AS DOUBLE
END TYPE
 
TYPE Triangle
    p1 AS Vector ' corner coordinates
    p2 AS Vector
    p3 AS Vector
END TYPE
 
DIM TestTriangle AS Triangle
DIM TestParticle AS Vector
 
TestTriangle.p1.x = 150
TestTriangle.p1.y = 0
TestTriangle.p2.x = 0
TestTriangle.p2.y = 100
TestTriangle.p3.x = -150
TestTriangle.p3.y = -100
 
DO
 
    DO WHILE _MOUSEINPUT
        x0 = _MOUSEX
        y0 = _MOUSEY
        x0 = (x0 - _WIDTH / 2)
        y0 = (-y0 + _HEIGHT / 2)
        TestParticle.x = x0
        TestParticle.y = y0
    LOOP
 
    CALL DrawTriangle(TestTriangle)
    CALL cpset(TestParticle.x, TestParticle.y, _RGBA(255, 255, 255, 255))
    CALL PointInsideTriangle(TestTriangle, TestParticle)
 
    _DISPLAY
    _LIMIT 30
LOOP
 
END
 
SUB PointInsideTriangle (tr AS Triangle, p AS Vector)
    DIM s12inside AS INTEGER
    DIM s23inside AS INTEGER
    DIM s31inside AS INTEGER
    DIM dz AS Vector
    DIM ta AS Vector
    ' side 12
    dz.x = p.x - tr.p1.x
    dz.y = p.y - tr.p1.y
    ta.x = tr.p2.x - tr.p1.x
    ta.y = tr.p2.y - tr.p1.y
    IF CrossProduct(ta, dz) > 0 THEN s12inside = 1 ELSE s12inside = 0
    ' side 23
    dz.x = p.x - tr.p2.x
    dz.y = p.y - tr.p2.y
    ta.x = tr.p3.x - tr.p2.x
    ta.y = tr.p3.y - tr.p2.y
    IF CrossProduct(ta, dz) > 0 THEN s23inside = 1 ELSE s23inside = 0
    ' side 31
    dz.x = p.x - tr.p3.x
    dz.y = p.y - tr.p3.y
    ta.x = tr.p1.x - tr.p3.x
    ta.y = tr.p1.y - tr.p3.y
    IF CrossProduct(ta, dz) > 0 THEN s31inside = 1 ELSE s31inside = 0
    IF s12inside = 1 AND s23inside = 1 AND s31inside = 1 THEN
        LOCATE 1, 1: PRINT "inside"
    ELSE
        LOCATE 1, 1: PRINT "      "
    END IF
END SUB
 
FUNCTION CrossProduct (a AS Vector, b AS Vector)
    CrossProduct = a.x * b.y - b.x * a.y
END FUNCTION
 
SUB DrawTriangle (t AS Triangle)
    CALL cline(t.p1.x, t.p1.y, t.p2.x, t.p2.y, _RGBA(255, 255, 255, 255))
    CALL cline(t.p2.x, t.p2.y, t.p3.x, t.p3.y, _RGBA(255, 255, 255, 255))
    CALL cline(t.p3.x, t.p3.y, t.p1.x, t.p1.y, _RGBA(255, 255, 255, 255))
END SUB
 
SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
    LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
END SUB
 
SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
    PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
END SUB
 

Qwerkey · « **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).
[ You are not allowed to view this attachment ]

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]

'Is a point inside or outside a triangle? (problem set by STxAxTIC)
 
CONST SmallErr# = 1E-11
 
DIM Vertices%(3, 1)
 
Vertices%(0, 0) = 10
Vertices%(0, 1) = 420
Vertices%(1, 0) = 600
Vertices%(1, 1) = 150
Vertices%(2, 0) = 690
Vertices%(2, 1) = 440
Vertices%(3, 0) = 520
Vertices%(3, 1) = 165
 
SCREEN _NEWIMAGE(700, 500, 32)
 
LINE (Vertices%(0, 0), Vertices%(0, 1))-(Vertices%(1, 0), Vertices%(1, 1))
LINE (Vertices%(1, 0), Vertices%(1, 1))-(Vertices%(2, 0), Vertices%(2, 1))
LINE (Vertices%(2, 0), Vertices%(2, 1))-(Vertices%(0, 0), Vertices%(0, 1))
 
LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(0, 0), Vertices%(0, 1)), _RGB32(255, 0, 0)
LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(1, 0), Vertices%(1, 1)), _RGB32(255, 0, 0)
LINE (Vertices%(3, 0), Vertices%(3, 1))-(Vertices%(2, 0), Vertices%(2, 1)), _RGB32(255, 0, 0)
 
A# = SideLength#(Vertices%(0, 0), Vertices%(0, 1), Vertices%(2, 0), Vertices%(2, 1))
B# = SideLength#(Vertices%(1, 0), Vertices%(1, 1), Vertices%(0, 0), Vertices%(0, 1))
C# = SideLength#(Vertices%(2, 0), Vertices%(2, 1), Vertices%(1, 0), Vertices%(1, 1))
 
D# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(1, 0), Vertices%(1, 1))
E# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(2, 0), Vertices%(2, 1))
F# = SideLength#(Vertices%(3, 0), Vertices%(3, 1), Vertices%(0, 0), Vertices%(0, 1))
 
Alpha# = Angle#(A#, B#, C#)
Beta# = Angle#(B#, C#, A#)
Gamma# = Angle#(C#, A#, B#)
 
AlphaDash# = Angle#(A#, E#, F#)
BetaDash# = Angle#(B#, D#, F#)
GammaDash# = Angle#(C#, D#, E#)
 
PRINT AlphaDash# + BetaDash# + GammaDash# - _PI(2)
 
WHILE INKEY$ = ""
    _LIMIT 30
WEND
SYSTEM
 
FUNCTION SideLength# (X1#, Y1#, X2#, Y2#)
    SideLength# = SQR((X1# - X2#) * (X1# - X2#) + (Y1# - Y2#) * (Y1# - Y2#))
END FUNCTION
 
FUNCTION Angle# (L1#, L2#, L3#)
    Angle# = _ACOS(((L2# * L2#) + (L3# * L3#) - (L1# * L1#)) / (2 * L2# * L3#))
END FUNCTION
 

STxAxTIC · « **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.

Qwerkey · « **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.

SMcNeill · « **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]

SCREEN _NEWIMAGE(640, 480, 32)
 
CONST DRAWIT = -1
 
PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 160, 150)
SLEEP
PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 150, 50)
SLEEP
SYSTEM
 
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 _RGBA32(255, 255, 255, 100)
    _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)
    _BLEND
    PSET (px, py), _RGBA(255, 0, 0, 200)
    p = POINT(px, py)
    IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1
    _DEST d: _SOURCE s
    IF DRAWIT THEN
        CLS
        CIRCLE (px, py), 5, _RGBA(255, 0, 0, 200)
        _PUTIMAGE (0, 0), temp, d
    END IF
    _FREEIMAGE temp
END FUNCTION

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.

Qwerkey · « **Reply #9 on:** June 18, 2020, 12:37:30 pm »

Quote from: SMcNeill on June 18, 2020, 12:21:45 pm

... a solution without doing any fancy-pancy vector math and such:

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

bplus · « **Reply #10 on:** June 18, 2020, 12:42:50 pm »

Quote from: SMcNeill 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]
SCREEN _NEWIMAGE(640, 480, 32)

CONST DRAWIT = -1

PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 160, 150)
SLEEP
PRINT CheckTriangle(100, 100, 200, 100, 300, 300, 150, 50)
SLEEP
SYSTEM

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 _RGBA32(255, 255, 255, 100)
_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)
_BLEND
PSET (px, py), _RGBA(255, 0, 0, 200)
p = POINT(px, py)
IF p = _RGBA32(255, 55, 55, 222) THEN CheckTriangle = -1
_DEST d: _SOURCE s
IF DRAWIT THEN
CLS
CIRCLE (px, py), 5, _RGBA(255, 0, 0, 200)
_PUTIMAGE (0, 0), temp, d
END IF
_FREEIMAGE temp
END FUNCTION

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]

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.

SMcNeill · « **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

STxAxTIC · « **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

Pete · « **Reply #13 on:** June 18, 2020, 05:38:33 pm »

The answer is 4.

Qwerkey · « **Reply #14 on:** June 19, 2020, 04:18:54 am »

I hope that I have now corrected the error in mine, quod vide.

News:

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

STxAxTIC

Harder-than-it-looks math problem

Ashish

Re: Harder-than-it-looks math problem

Qwerkey

Re: Harder-than-it-looks math problem

MasterGy

Re: Harder-than-it-looks math problem

STxAxTIC

Re: Harder-than-it-looks math problem

Qwerkey

Re: Harder-than-it-looks math problem

STxAxTIC

Re: Harder-than-it-looks math problem

Qwerkey

Re: Harder-than-it-looks math problem

SMcNeill

Re: Harder-than-it-looks math problem

Qwerkey

Re: Harder-than-it-looks math problem

bplus

Re: Harder-than-it-looks math problem

SMcNeill

Re: Harder-than-it-looks math problem

STxAxTIC

Re: Harder-than-it-looks math problem

Pete

Re: Harder-than-it-looks math problem

Qwerkey

Re: Harder-than-it-looks math problem