Point Inside A triangle

[ceaser]

Thanks Wolfgang...it helped. It seems to be faster than using the area method.

My only problem is that, like DeeCee says, if you have 10 000 triangles. It can take some time when the triangle that you are working with is the last one!

Thanks
Michael

[klaus]

Hi DeeCee and Ceasar,

I was on travel the last weeks, so I didn't answer your post before.

I have made some tests finding the triangle where the point is in.
Attached 3 test programs:
The programs checks 10000 triangles, the point is in the last one.

3 methods are used:
1)Check triangle:
- checks if the point lies in the triangle
2)Check rectangle:
- calculates the coordinates of the surrounding rectangle
- checks if the point lies in the surrounding rectangle
- if yes, checks if the point lies in the triangle
3)Check X Y Max Min:
- the xmin, xmax, ymin and ymax of the surrounding rectangle for each triangle are precalculated somewhere else in the program and memorized
- checks if the point lies in the surrounding rectangle
- if yes, checks if the point lies in the triangle

Checking if a point lies in a rectangle is faster then checking for a triangle.

TestFindTriangle1:
- standard variables
- 10000 triangles with the 3 coordinates

TestFindTriangle2:
- variables declared as Double
- 10000 triangles with the 3 coordinates

TestFindTriangle3: variables declared as Double
- variables declared as Double
- 4 points with their coordinates
- 10000 triangles with the vertex point indexes

Test results optimized compiled on my htc Touch HD in seconds:

<font size="2"><font face="Courier New"><font size="2"><font face="Courier New">  Test1 Test2 Test3</font></font></font></font>
<font size="2"><font face="Courier New"><font color="#800080"><font size="2"><font face="Courier New"><font color="#800080"><font size="2"><font face="Courier New"><font color="#800080">1</font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font face="Courier New"><font size="2">) </font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">43    </font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">30    33</font></font></font></font></font></font></font></font></font>
<font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">2</font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font face="Courier New"><font size="2">) </font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">40    13</font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">    15</font></font></font></font></font></font></font></font></font>
<font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">3</font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font face="Courier New"><font size="2">) </font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">12     4</font></font></font></font></font></font></font></font></font><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080"><font face="Courier New"><font size="2"><font color="#800080">     5</font></font></font></font></font></font></font></font></font>

Hope this could help you.

Best regards.

[agraham]

Be sure to check out my new http://www.basic4ppc.com/forum/addit...html#post28926 which should give a performance boost to this sort of calculation. You could probably do the Delauney calculation in Basic4ppc now.

[ceaser]

Hi Agraham

Thanks for that. I did have a look at it, but have not played with it yet.

I suppose I could also use it in my surveying program, as there are routines which are based on some heavy maths. For instance the calculations involved in a spiral, cross-section calcs, or even in the CAD....

Thanks
Michael