CODEWITHSUNDEEP
performancealgorithm
EOG
EOG

Reputation: 1747

Fastest way to find any point in triangle 2D

I need a fastest way to find any point inside triangle(not edges) in 2D. Any help?

Upvotes: 0

Views: 2670

Answers (4)

Kaganar
Kaganar

Reputation: 6570

If your triangle is expressed as points, you're going to have to take every coordinate into consideration, so Steve Jessop's answer is nearly optimal.

Note all you actually need to do is start at one point and bump it towards the two others a limited amount. That's what averaging accomplishes, but in a very specific way.

The addition is fast. The division may be slow depending on the platform and compiler.

For example, on modern ARM cores I'd choose this version any day over averaging:

xm = (x0 + (x1 + x2) / 2) / 2
ym = (y0 + (y1 + y2) / 2) / 2

If the variables are integer the compiler should optimize the divisions to bit shifts which, if scheduled correctly, are largely free in ARM. If the variables are floats or doubles the compiler should optimize them to simple exponent decrements. Floating point division is known to be relatively slow.

Ultimately, test and see. Unless you're doing relatively low level code optimization, you likely won't see a difference. On the other hand, if you're using this in a tight inner loop, you might.

To provide some intuition as to why this works: First we find the midpoint of the line segment formed by (x1, y1) and (x2, y2). Then we find the midpoint between the line segment formed by that point and (x0, y0). If you draw a diagram of a triangle and do this, it becomes immediately clear that this works.

Upvotes: 2

Steve Jessop
Steve Jessop

Reputation: 279195

The "average" of the three vertices (the centroid) is a point inside the triangle, and is probably as fast to calculate as any other.

It only lies on an edge in the degenerate case where the vertices are colinear. In that case every point in the triangle lies on an edge, so there's no solution.

Upvotes: 5

MBo
MBo

Reputation: 80107

Vertices A, B, C

vectors

AB = B-A

AC = C-A

P = A + t * AB + u* AC

t,u - any numbers (random?) in range [0..1], and t + u <= 1

Upvotes: 1

Rps
Rps

Reputation: 277

or: you could first calculate the surface of the triangle. Then you do a second calculation where your point devides the triangle in three other triangles. If the surface off these three subtriangles is bigger, than your point is outside of the triangle area. See what i mean?

Upvotes: 0

Related Questions