CODEWITHSUNDEEP
geometry
MKS
MKS

Reputation: 786

triangle points around a point

I have given the coordinates of 1000 triangles on a plane (triangle number (T0001-T1000) and its coordinates (x1,y1) (x2,y2),(x3,y3)). Now, for a given point P(x,y), I need to find a triangle which contains the point P.

One option might be to check all the triangles and find the triangle that contain P. But, I am looking for efficient solution for this problem.

Upvotes: 2

Views: 458

Answers (2)

Andy
Andy

Reputation: 251

Several different ways you could search through your triangles. I would start by eliminating impossibilities.

Find a lowest left corner for each triangle and eliminate any that lie above and/or to the right of your point. continue search with the other triangles and you should eliminate the vast majority of the original triangles.

Take what you have left and use the polar coordinate system to gather the rest of the needed information based on angles between the corners and the point (java does have some tools for this, I do not know about other languages).

Some things to look at would be convex hull (different but somewhat helpful), Bernoullies triangles, and some methods for sorting would probably be helpful.

Upvotes: 0

David Grayson
David Grayson

Reputation: 87386

You are going to have to check every triangle at some point during the execution of your program. That's obvious right? If you want to maximize the efficiency of this calculation then you are going to create some kind of cache data structure. The details of the data structure depend on your application. For example: How often do the triangles change? How often do you need to calculate where a point is?

One way to make the cache would be this: Divide your plane in to a finite grid of boxes. For each box in the grid, store a list of the triangles that might intersect with the box.

Then when you need to find out which triangles your point is inside of, you would first figure out which box it is in (this would be O(1) time because you just look at the coordinates) and then look at the triangles in the triangle list for that box.

Upvotes: 2

Related Questions