Author Topic: IN/ Out triangle: Help!  (Read 1687 times)

0 Members and 1 Guest are viewing this topic.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
IN/ Out triangle: Help!
« on: June 23, 2020, 08:54:13 am »
Hi guys
I have this trouble...
I have found a geometric formula to evaluate the position of a P point towards the ABC plane of a triangle using the centroid...
here the reference  https://en.wikipedia.org/wiki/Centroid#Of_a_triangle
Quote
Let ABC be a triangle, let G be its centroid, and let D, E, and F be the midpoints of BC, CA, and AB, respectively. For any point P in the plane of ABC then PA+PB+PC <= 2*(PD+PE+PF)+3*PG

Please I am not able to catch the mistake
here the code.
Code: QB64: [Select]
  1.  
  2. SCREEN _NEWIMAGE(800, 600, 32)
  3. _TITLE "In or Out the triangle?"
  4.     x AS INTEGER
  5.     y AS INTEGER
  6.  
  7. CONST True = -1, False = NOT True
  8. DIM SHARED P(1 TO 8) AS point ' 3 vertex 3 medium points 1 centroid 1 point P to test
  9. WINDOW SCREEN(0, 0)-(799, 599)
  10. Initialize
  11.     ' it gets input
  12.     a = _MOUSEBUTTON(1)
  13.     b = _MOUSEBUTTON(2)
  14.     P(4).x = _MOUSEX: P(4).y = _MOUSEY
  15.     c = INKEY$
  16.     ' output to screen
  17.     CLS
  18.     makeImage
  19.     ' calculations
  20.     IF IsInner THEN _PRINTSTRING (10, 30), " Point is inner to triangle" ELSE _PRINTSTRING (10, 10), " Point is outer to triangle"
  21.     IF c = CHR$(13) XOR a THEN Initialize
  22.     ' it slows pc
  23.     _DISPLAY
  24.     _LIMIT 10
  25. LOOP UNTIL c = " " OR b = True
  26.  
  27. FUNCTION IsInner
  28.     'PA+PB+PC <= 2*(PD+PE+PF)+3*PG
  29.     IF (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))) <= 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8))) THEN IsInner = True ELSE IsInner = False
  30.  
  31.     ' debug output
  32.     PRINT (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))) <= 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8))); " ";
  33.     PRINT (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))), 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8)))
  34.  
  35. FUNCTION Distance (P1 AS point, P2 AS point)
  36.     ' in a Carthesian grid the distance between P1 and P2
  37.     'is the hypotenuse of the triangle rectangle of the 2 cohordinates
  38.     Distance = SQR(((P1.x - P2.x)) ^ 2 + ((P1.y - P2.y)) ^ 2)
  39.  
  40. SUB makeImage
  41.     DIM a AS INTEGER
  42.     COLOR _RGB32(255)
  43.     ' graphic cursor starts at last vertex of triangle
  44.     PSET (P(3).x, P(3).y)
  45.     FOR a = 1 TO 3 STEP 1 ' vertexs
  46.         LINE -(P(a).x, P(a).y)
  47.     NEXT
  48.  
  49.     ' using little circle points are more visible
  50.     ' PSET
  51.     CIRCLE (P(4).x, P(4).y), 3, _RGB32(255, 0, 0) ' point to test
  52.     ' PSET
  53.     CIRCLE (P(5).x, P(5).y), 3, _RGB32(0, 0, 255) ' centroid
  54.     'PSET
  55.     CIRCLE (P(6).x, P(6).y), 3, _RGB32(0, 255, 0) 'midpoints
  56.     ' PSET
  57.     CIRCLE (P(7).x, P(7).y), 3, _RGB32(0, 255, 200)
  58.     '    PSET
  59.     CIRCLE (P(8).x, P(8).y), 3, _RGB32(200, 255, 0)
  60.  
  61. SUB Initialize
  62.     DIM a AS INTEGER
  63.     ' it creates at random 3 vertex and point P to test inner/outer triangle
  64.     FOR a = 1 TO 4 STEP 1
  65.         P(a).x = 1 + RND * 780
  66.         P(a).y = 1 + RND * 580
  67.     NEXT
  68.     ' it calculates centroid
  69.     P(5).x = (P(1).x + P(2).x + P(3).x) / 3
  70.     P(5).y = (P(1).y + P(2).y + P(3).y) / 3
  71.  
  72.     'it calculates midpoints DEF
  73.     P(6).x = (P(1).x + P(2).x) / 2
  74.     P(6).y = (P(1).y + P(2).y) / 2
  75.     P(7).x = (P(3).x + P(2).x) / 2
  76.     P(7).y = (P(3).y + P(2).y) / 2
  77.     P(8).x = (P(1).x + P(3).x) / 2
  78.     P(8).y = (P(1).y + P(3).y) / 2

all point are at the right place but the function always returns true nevertheless the P point is put by mouse.

you can change triangle with enter key or left click of mouse, you can quit with space key or right click of mouse

Thanks to help
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #1 on: June 23, 2020, 11:27:46 am »
Looks like it is set up OK but
Quote
Let ABC be a triangle, let G be its centroid, and let D, E, and F be the midpoints of BC, CA, and AB, respectively. For any point P in the plane of ABC then PA+PB+PC <= 2*(PD+PE+PF)+3*PG
I could not find this quote in the Wiki you referenced to judge the context. The quote comes at very end.

This looks more like finding points on the same plane, "in the plane of ABC", as the triangle NOT in the interior of the triangle. In which case your exercise being all on same plane to start would return true always.
« Last Edit: June 23, 2020, 11:47:54 am by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #2 on: June 23, 2020, 01:11:17 pm »
Wait, didn't we just spend a week on this question and solve it multiple ways?
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #3 on: June 23, 2020, 01:44:44 pm »
Wait, didn't we just spend a week on this question and solve it multiple ways?

Slightly different if this test is for Coplanar points to triangle.

Yes I was going to test 3D version of this with your problem code but I don't know if the 2 points not Interior might still be coplanar, what are the odds? Oh just points of cube that contains the triangle we know those arent coplanar.
« Last Edit: June 23, 2020, 01:46:24 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #4 on: June 23, 2020, 02:06:06 pm »
Meh you guys aren't reading my pdf, I solved both
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #5 on: June 23, 2020, 02:18:18 pm »
Meh you guys aren't reading my pdf, I solved both

So does your PDF say if this:
PA+PB+PC <= 2*(PD+PE+PF)+3*PG

is a test for Coplanar Points of Triangle ABC with DEF midpoints of ABC segments and G the Centroid Pt

or is it a test for points Interior (and Coplanar) of triangle ABC?

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #6 on: June 23, 2020, 02:42:17 pm »
It's not news that I use vector notation, so no, the thing you cite isn't part of my write-up on the grounds that I didn't need it. I have two explicit calculations for coplanarity and containment as separate concerns. Obviously one encloses the other...

If I could use the proper notation on forums I would just 'splain it but no freebie this time
« Last Edit: June 23, 2020, 02:43:19 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #7 on: June 23, 2020, 03:02:19 pm »
Thanks Bplus
for the perspective that you bring. Rightly you stress that it talks about the plane of ABC... but with a 2D entities (the points: vertexs of triangles, centroid, middlepoints of sides of triangle and P poit to test) how can I  produce a P point external to the 2D plane in which the triangle is already?
This is the thought that let me use that formula to test if P point is out o in to the triangle.
 
triangolo centroide e punto P.jpg


So I'll give a try with the other formula
Quote
PA^2+PB^2+PC^2 = GA^2+GB^2+GC^2+3(PG^2)

Waiting more info I thank you for your time spent to answer me
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #8 on: June 23, 2020, 04:11:13 pm »
Quote
Waiting more info I thank you for your time spent to answer me

Just a little more wait, just got back from lunch and testing Spriggsy's help for FileDialog.

I have reworked your code a little to make it easier to read and hope to use it with code I worked on yesterday for STx 3D problem.

If I say, "It shouldn't take long", I will curse myself! ;-))  Excellent drawing BTW!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #9 on: June 23, 2020, 05:07:02 pm »
@TempodiBasic

Well in 3D there is still no relief from returning -1 for True
Code: QB64: [Select]
  1. _TITLE "Checking TempodiBasic formula for Coplanar Points"
  2. ' 2020-06-23 ref:  https://www.qb64.org/forum/index.php?topic=2745.0
  3.  
  4. SCREEN _NEWIMAGE(1000, 600, 32)
  5. _DELAY .25 'allow time to load before moving
  6.  
  7. DEFDBL A-Z
  8. TYPE xyz
  9.     x AS DOUBLE
  10.     y AS DOUBLE
  11.     z AS DOUBLE
  12.  
  13. 'given 3d tri
  14. '(1,1,0)
  15. '(1,0,1)
  16. '(0,1,1)
  17. DIM SHARED tri(2) AS xyz ' This turns out to be Equilateral triangle from my experiments of getting 3D angles
  18. tri(0).x = 1: tri(0).y = 1: tri(0).z = 0
  19. tri(1).x = 1: tri(1).y = 0: tri(1).z = 1
  20. tri(2).x = 0: tri(2).y = 1: tri(2).z = 1
  21.  
  22. 'given test cases   6 points in 3d tri or not? 2 are made up the remaider are in which is which?
  23. '(.66,.66,.66)
  24. '(.46,.66,.86)
  25. '(.83,.89,.26)
  26. '(.55,.55,.55)
  27. '(.75,.79,.46)
  28. '(.79,.89,.66)
  29. DIM test(5) AS xyz
  30. test(0).x = .66: test(0).y = .66: test(0).z = .66 'on/in
  31. test(1).x = .46: test(1).y = .66: test(1).z = .86
  32. test(2).x = .83: test(2).y = .89: test(2).z = .26
  33. test(3).x = 100: test(3).y = -100: test(3).z = 100 '
  34. test(4).x = .75: test(4).y = .79: test(4).z = .46
  35. test(5).x = 0: test(5).y = 0: test(5).z = 0 '
  36.  
  37. DIM SHARED P(1 TO 8) AS xyz, TF
  38. Initialize
  39. FOR i = 0 TO 5 'test points to Stx triangle, we know 4 are inside of triangle so MUST also be Coplanar
  40.     P(4).x = test(i).x: P(4).y = test(i).y: P(4).z = test(i).z
  41.     TF = IsInner
  42.     PRINT "For test point"; i; " IsInner test returned"; TF
  43.     PRINT
  44. PRINT "Number 3 and 5 should not be true"
  45. FUNCTION dist3D (p1 AS xyz, p2 AS xyz)
  46.     dist3D = SQR((p1.x - p2.x) ^ 2 + (p1.y - p2.y) ^ 2 + (p1.z - p2.z) ^ 2)
  47.  
  48.  
  49. SUB Initialize
  50.     DIM i AS INTEGER
  51.     PRINT "Initializing"
  52.     ' using STx known triangle and test points already tested
  53.     FOR i = 1 TO 3 STEP 1
  54.         P(i).x = tri(i - 1).x
  55.         P(i).y = tri(i - 1).y
  56.         P(i).z = tri(i - 1).z
  57.         PRINT P(i).x, P(i).y, P(i).z
  58.     NEXT
  59.     PRINT "Centroid"
  60.  
  61.     ' it calculates centroid
  62.     P(5).x = (P(1).x + P(2).x + P(3).x) / 3
  63.     P(5).y = (P(1).y + P(2).y + P(3).y) / 3
  64.     P(5).z = (P(1).z + P(2).z + P(3).z) / 3
  65.     PRINT P(5).x, P(5).y, P(5).z
  66.     PRINT "Mid-points"
  67.     'it calculates midpoints DEF
  68.     P(6).x = (P(1).x + P(2).x) / 2
  69.     P(6).y = (P(1).y + P(2).y) / 2
  70.     P(6).z = (P(1).z + P(2).z) / 2
  71.     PRINT P(6).x, P(6).y, P(6).z
  72.  
  73.     P(7).x = (P(3).x + P(2).x) / 2
  74.     P(7).y = (P(3).y + P(2).y) / 2
  75.     P(7).z = (P(3).z + P(2).z) / 2
  76.     PRINT P(7).x, P(7).y, P(7).z
  77.  
  78.     P(8).x = (P(1).x + P(3).x) / 2
  79.     P(8).y = (P(1).y + P(3).y) / 2
  80.     P(8).z = (P(1).z + P(3).z) / 2
  81.     PRINT P(8).x, P(8).y, P(8).z
  82.     PRINT
  83.  
  84. FUNCTION IsInner
  85.     'PA+PB+PC <= 2*(PD+PE+PF)+3*PG
  86.     DIM PA, PB, PC, PD, PE, PF, PG
  87.     PA = dist3D(P(4), P(1)): PB = dist3D(P(4), P(2)): PC = dist3D(P(4), P(3))
  88.     PD = dist3D(P(4), P(6)): PE = dist3D(P(4), P(7)): PF = dist3D(P(4), P(8))
  89.     PG = dist3D(P(4), P(5))
  90.     IF PA + PB + PC <= 2 * (PD + PE + PF) + 3 * PG THEN IsInner = -1
  91.     PRINT PA + PB + PC, 2 * (PD + PE + PF) + 3 * PG
  92.  
  93.     'IF (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))) <= 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8))) THEN IsInner = True ELSE IsInner = False
  94.  
  95.     ' debug output
  96.     'PRINT (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))) <= 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8))); " ";
  97.     'PRINT (Distance(P(4), P(1)) + Distance(P(4), P(2)) + Distance(P(4), P(3))), 3 * Distance(P(4), P(5)) + 2 * (Distance(P(4), P(6)) + Distance(P(4), P(7)) + Distance(P(4), P(8)))
  98.  
  99.  
  100.  

Sorry I don't understand the "Inner" formula better to say what our difficulty is.

EDIT: Dang forgot to call Initialize! still didn't help :(
« Last Edit: June 23, 2020, 05:32:40 pm by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #10 on: June 23, 2020, 07:10:04 pm »
@TempodiBasic

If you start with your drawing here:
https://www.qb64.org/forum/index.php?topic=2727.msg119597#msg119597
and remove all the mid points and lines to them, you will have a tetrahedron (3 sided pyramid). If the areas of the 3 triangles from P = the area of the base triangle then the tetrahedron is flat and P is Coplanar to ABC and inside or on triangle ABC.


Compare the Sum of the areas of 3 triangles from point P to the area of Triangle ABC, will check if P is is inside on same plane as ABC, if P were higher or lower or outside Triangle ABC then the Sum of the areas of 3 Triangles from P to the 3 sides of Triangle ABC would be greater than the area of ABC.
 
We did this here on Father's Day:
https://www.qb64.org/forum/index.php?topic=2727.msg119597#msg119597
« Last Edit: June 24, 2020, 12:17:35 pm by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #11 on: June 23, 2020, 07:23:19 pm »
Bing Search from new Edge: (that my browser couldn't find using Google)
https://www.mat.uniroma2.it/~tauraso/AMM/AMM12015.pdf

This IS the article referenced in Wiki about the formula.

I don't know any other way to interpret |AB| other than always positive distance between 2 Points.

Maybe the paper is wrong, TempodiBasic you are good at finding bugs, are you an entomologist? ;-))
« Last Edit: June 23, 2020, 07:52:40 pm by bplus »

Offline codeguy

  • Forum Regular
  • Posts: 174
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #12 on: June 23, 2020, 10:57:25 pm »
if the slope is the same between any two points of the triangle and a point of the triangle and the point in question, it's coplanar. You may need a tolerance of .001 or so because digital division isn't always precise.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #13 on: June 24, 2020, 04:18:46 am »
@bplus

yes your research is very accurate.  So in the original article there is the 3rd dimension! And it solves the question of why the author says plane of triangle ABC!

about the other formula this is the reference: https://www.isinj.com/mt-usamo/An%20Introduction%20to%20the%20Modern%20Geometry%20of%20the%20Triangle%20and%20the%20Circle%20-%20Altshiller-Court%20N.%20College%20Geometry%20(Dover%202007).pdf
at page 70 of book (89 of pdf file) theorem 109.
Quote
Let P be any point in the plane of a triangle with vertices A, B, and C and centroid G. Then the sum of the squared distances of P from the three vertices exceeds the sum of the squared distances of the centroid G from the vertices by three times the squared distance between P and G:

....Nope  it seems that the 3rd dimension comes out always!

now I'll try with this assumption
Quote
A triangle's centroid is the point that maximizes the product of the directed distances of a point from the triangle's sidelines
reference: triangle's centroid is the point that maximizes the product of the directed distances of a point from the triangle's sidelines
see later
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: IN/ Out triangle: Help!
« Reply #14 on: June 24, 2020, 10:41:15 am »
Yes it looks like we are talking about 2D Triangles on same plane in both references.

The equation you point to in Geometry book is talking about Centroids alright, but they are not talking inside / outside of triangle let alone a plane.

That book looks interesting though, I will skim through it.
« Last Edit: June 24, 2020, 10:44:26 am by bplus »