CODEWITHSUNDEEP
algorithm
Bhaskar
Bhaskar

Reputation: 700

Efficient method to check if point is within a diamond

I have an array of diamonds as shown in the image and I know the position of every diamond and the distance from the origin of the diamond to any vertex (They are all the same distance from the center). I am also given a point. Given that information what is the most efficient method to find which diamond the point is in.

I know that I can just check the distance of the point from the position of every diamond but that seems way too cpu intensive as I have to do this multiple times.

enter image description here

Also, this shouldn't matter, but I am using C# and Unity 3D to do this.

Upvotes: 1

Views: 921

Answers (2)

MBo
MBo

Reputation: 80197

Diamonds border line have equations

x + y = a0 + u * Size
y - x = b0 + v * Size

where a0, b0 are coordinates of the some vertex of base diamond (that has cell coordinates 0, 0), u and v are cell coordinates, Size is edge length. So to find what diamond point (px, py) belongs to, you can calculate

u = Floor((px + py - a0) / Size))
v = Floor((py - px - b0) / Size))

Upvotes: 0

AnT stands with Russia
AnT stands with Russia

Reputation: 320611

If your diamonds form a regular pattern as in your picture, then just perform coordinate transformation to rotate the whole thing 45 degrees CW or CCW with (0, 0) as the origin. After that the problem becomes trivial: locating a point in a regular orthogonal grid.

Upvotes: 3

Related Questions