CODEWITHSUNDEEP
algorithm
Young
Young

Reputation: 81

Algorithm about how to find three points

Given a set of points named S, and a point P. How to find three points in the set S, s.t these three points can form triangle T and P is in triangle T with lowest time complexity?

Any programming language is okay. And pseudocode is just fine.

Greate thanks!

Upvotes: 0

Views: 124

Answers (2)

Tilak Putta
Tilak Putta

Reputation: 778

  • Iterate through the set of elements
  • Select three points a,b,c
  • Check whether all the points lie on same line
  • If they do not lie on same line, then they can form a triangle
  • now take the point p
  • calculate area of triangles ABC, PAB, PBC, PAC
  • Check whether areas of ABC = PAB+PBC+PAC
  • If they are equal then P lies inside ABC triangle.

Upvotes: 0

mcdowella
mcdowella

Reputation: 19621

Draw a point inside a triangle and draw lines from the point to the corners. You should see that the angles between these lines are all less than 180 degrees, and that as the point moves outside the triangle one of the angles between the lines reaches 180 degrees when it crosses a side of the triangle.

So if you think of the points as being on a map, take the compass bearing from P to every other point and then sort the results. If there is a gap anywhere greater than or equal to 180 degrees between the sorted values (including the wrap-around from 360 to 0) then P is not inside any triangle.

Assuming that test passed, think of all the points laid out according to their compass bearings on a circle and pick an arbitrary point and draw a diameter through the circle at that point, splitting it in two. There must be other points to either side of that diameter, or we would have a gap of 180. Pick the two points in each half furthest from the arbitrary point. If they are >= 180 degrees apart, we have a gap of 180 degrees. If not, all points are within 180 degrees of each other and we have three points that enclose the original point.

The complexity of this is O(n log n) which seems reasonable to me but is not necessarily average case fastest, although I suspect its worst case is reasonable. Depending on your data and how it is presented there may be speed-ups which involve first picking a small number of points at random in the hope that they will include a triangle that encloses P.

Upvotes: 2

Related Questions