8
$\begingroup$

Actually, I have no knowledge in Mathematica. I posted a mathematical problem in math.SE, but user170231 suggested me to post it here.

He said it can be solved using "way of image processing".

If possible to solve it by "way of image processing", then it will be as a verification only.

Also, I want to note again that: "All triangles must be considered, even tiny ones. Otherwise, the coordinates will not be given in this way" (All triangles, including those which do not lie on the boundary of the 3-4-5-triangle).


My Original Post:

While reading a pdf Arabic math book, counting chapter, I found this question:

enter image description here

It says:

The points $(0,0),(0,3),(4,0)$ are jointed to each other. Also, the points:

$(0,1),(0,2),(0.8,2.4),(1,0),(1.6,1.8),(2,0),(2.4,1.2),(3,0),(3.2,0.6)$ are jointed to each other and to the vertices of the $3-4-5-$triangle. What is the total number of triangle? (Note: All triangles must be considered).


I tried to use simple formulas of counting triangles in simple shapes, like the big triangle is divided by joining a straight line from a vertex to the opposite side, we just count the number of bases on the divided side, we apply the formula $N=n(n+1)/2$. Also for adjacent equilateral triangles we can use the formula $N=n(n+2)(2n+2)/8$ and then we round down, where $n$ is the number triangles on one side of the big one, .... and some other simple shapes. I tried to combine some of the together, but noway.

What I knew about the given points is to make fixed total number of triangles. Moving a point slightly may change the answer. THERE ARE SMALL TRIANGLES!


But this one is so complected, and without calculation, I think the total number of triangles is so large number. Maybe it is okay to keep the answer in a form containing factorials or $^aC_b$ or or $^aP_b$ such forms. I am not sure how to begin.

If the vertices of the triangles that to be counted lie on the boundaries of the $3-4-5-$triangle, then this is:

$$^{12}C_3-^6C_3-^5C_3-^4C_3=186$$

But this is not the case, the required is to find the total number of possible triangles in the figure. Note: listing the coordinates implies an interest in the tiny triangles. Also, note that: because of these particular given coordinates, we have some intersection points of $3$ lines, and some of only $2$ lines, resulting some tiny triangles to be considered.

EDIT:

Here is a big figure, I used desmos to make it:

enter image description here


Any help would be really appreciated. THANKS!

Any help would be really appreciated. THANKS!

$\endgroup$
  • 2
    $\begingroup$ "See My Original Post" - as much as possible, please keep questions self-contained; include enough information so that other users don't have to refer to your other link. $\endgroup$ – J. M.'s discontentment May 29 at 16:50
  • $\begingroup$ Also, you might consider looking at this previous thread, and see if you can adapt that to your problem. (It's easy to count 3-cycles in a graph, once you have it.) $\endgroup$ – J. M.'s discontentment May 29 at 16:54
  • $\begingroup$ @J.M. Good suggestion, I will copy it and paste it here. Thanks. $\endgroup$ – Hussain-Alqatari May 29 at 16:55
  • 1
    $\begingroup$ @J.M.: The subtlety with using the graph theory subroutines here is that two points can form the side of a triangle without being directly connected (i.e. without any vertices between them.) For example, if you naïvely imported the image and turned it into a graph, with all of the intersections becoming vertices, then there wouldn't be a 3-cycle including the corners of the original triangle. $\endgroup$ – Michael Seifert May 29 at 21:20
  • $\begingroup$ @Michael, you're right; collinear edges that could merge to a bigger edge would be missed by my proposal. $\endgroup$ – J. M.'s discontentment May 30 at 5:55
8
$\begingroup$

Create a list of line segments in the graph (this is rather kludgey, but I couldn't find a slick way to eliminate edges that were colinear with the edges):

corners = {{0, 0}, {0, 3}, {4, 0}}
sidepoints = {{0, 1}, {0, 2}, {1, 0}, {2, 0}, {3, 0}, {4/5, 12/5}, {8/
   5, 9/5}, {12/5, 6/5}, {16/5, 3/5}}
sides = Subsets[corners, {2}]
lines1 = Tuples[{corners[[1 ;; 1]], sidepoints[[6 ;; 9]]}];
lines2 = Tuples[{corners[[2 ;; 2]], sidepoints[[3 ;; 5]]}];
lines3 = Tuples[{corners[[3 ;; 3]], sidepoints[[1 ;; 2]]}];
lines4 = Tuples[{sidepoints[[1 ;; 2]], sidepoints[[3 ;; 5]]}];
lines5 = Tuples[{sidepoints[[3 ;; 5]], sidepoints[[6 ;; 9]]}];
lines6 = Tuples[{sidepoints[[6 ;; 9]], sidepoints[[1 ;; 2]]}];
lines = Join[sides, lines1, lines2, lines3, lines4, lines5, lines6];

Create a function that checks whether three line segments form a triangle. To do this, they must each intersect each other, and they must not all intersect at the same point.

triangleQ[{line1_, line2_, line3_}] 
 := (! RegionDisjoint[Line[line1], Line[line2]]) 
    && (! RegionDisjoint[Line[line2], Line[line3]]) 
    && (! RegionDisjoint[Line[line3], Line[line1]]) 
    && (RegionMeasure[RegionIntersection[Line[line1], Line[line2], Line[line3]]] == 0) 

Look at all triplets of lines in the graph, and select those which form triangles:

candidates = Subsets[lines, {3}];
triangles = Select[candidates, triangleQ];
Length[triangles]

(* 3201 *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ First of all, thank you very much for sharing this answer. Even I do not have knowledge in Mathematica, I am more, but not totally, convinced with the answer. Edward Porcella answered: $3172$ triangles. Secondly, if you check Edward Porcella answer, you may know which one is wrong, possibly both are wrong? How sure you are? Thanks again dear. math.stackexchange.com/questions/3630441/… $\endgroup$ – Hussain-Alqatari May 29 at 20:28
  • $\begingroup$ @Hussain-Alqatari: Edward Porcella's answer is a pretty involved, and it's difficult to check; having done similar brute-force enumeration proofs in my work, I know how easy it is to make a mistake there. But I don't use Mathematica's geometric calculation features on a regular basis and it's possible I have an error too. If I had to guess, I'd say that it's about equally likely that one of us has made an error. $\endgroup$ – Michael Seifert May 29 at 21:25
  • $\begingroup$ Well, can Mathematica list (all) those possible triangles in terms of the vertices? For example, the triangle $((\frac{32}{15},\frac{2}{5}),(\frac{23}{10},\frac{9}{10}),(\frac{144}{55},\frac{27}{55}))$ appears in the list. If possible, can you please help me for that? Thanks in advance. $\endgroup$ – Hussain-Alqatari May 30 at 12:53
7
$\begingroup$

I also get 3201 triangles. I've created a Manipulate so you can see all the triangles flash past your eyes. They are sorted in order of increasing area. Some frames are skipped, but I can assure you all the triangles, including the last full triangle are present if you run the real thing. Hopefully by playing with this Manipulate you'll be convinced:

points = DeleteDuplicates[Join[
    {0, 3*#} & /@ Subdivide[3],
    {4*#, 0} & /@ Subdivide[4],
    {0, 3} # + (1 - #) {4, 0} & /@ Subdivide[5]
    ]];

outertriangle = {
  Line[{{0, 0}, {0, 3}}],
  Line[{{0, 0}, {4, 0}}], 
  Line[{{0, 3}, {4, 0}}]};
triunion = RegionUnion[outertriangle];

(* remove lines co-linear with the boundary triangle *)
lines = Select[Line /@ Subsets[points, {2}], 
   RegionMeasure[RegionIntersection[#, triunion], 1] == 0 &];

(* put the longest boundary lines back *)
lines = Join[lines, outertriangle];

intersections[lines_] := Union[
  RegionIntersection @@ # & /@ Subsets[lines, {2}]]

triangleQ[linetriple_] := Block[{isects = intersections[linetriple]},
  (Length[isects] == 3) && AllTrue[isects, Head[#] == Point &]]

alltriangles = Select[Subsets[lines, {3}], triangleQ];
Length@alltriangles
(* result 3201 *)

sortedtris = 
  SortBy[{#, Triangle[intersections[#] /. Point[{x_}] :> x]} & /@ 
    alltriangles, Area[#[[2]]] &];
Manipulate[Graphics[{
   lines, Red, Thick, sortedtris[[i, 1]], Opacity[.5], Blue, sortedtris[[i, 2]]
 }], {i, 1, Length@sortedtris, 1}]

triangles manipulate

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.