Существуют ли какие-либо алгоритмы, которые позволяют быстрый/эффективный поиск шестиугольников на основе местоположения ⇐ JAVA

[Anonymous]

Итак, у меня есть разделенная сфера икосаэдра (икосфера), и я просматриваю ее вершины и создаю логическую тайловую карту шестиугольников в месте каждой вершины массива. По сути, теперь мне нужно начать обнаруживать входные данные на тайловой карте, а перебирать 10 тысяч тайлов и выполнять проверку границ каждый раз, когда пользователь наводит указатель мыши на сферу или щелкает ее, слишком затратно в вычислительном отношении.
Мне нужен способ быстро и эффективно получить плитку, на которую пользователь нажимает или наводит курсор.
Моя текущая идея — создать 2D-массив плиток (широта/долгота). , конвертируйте положение плитки для значений широты и долготы и сохраните плитку по адресу tiles[lat][lon].
Проблема этого решения заключается в том, что широта и долгота сохраняются как значения с плавающей запятой - в этом В этом случае они (с точки зрения расстояния) находятся на «радиусе сферы» от центральной точки сферы. Если я это сделаю, мне придется резко увеличить сферу, и вполне вероятно, что в массиве будет много «неиспользуемых» слотов, содержащих нулевые значения. Это довольно грязно. Если бы мы сделали это, нам также пришлось бы найти какой-то способ гарантировать, что значение широты/долготы приблизительно сопоставляется непосредственно с координатой x/y тайла в массиве тайлов (т. е. мы могли бы просто сделать tiles[(int)lat] [(int)lon], чтобы получить плитку, но опять же, это создаст массив со многими пустыми слотами (что, насколько я понимаю, приводит к большому количеству потраченной впустую памяти, как дополнительный минус).
Я также мог бы хранить фрагменты в словаре словарей, при этом внешний словарь будет ArrayMap. Проблема в том, что я не совсем уверен, насколько производительно это действительно может быть - мы говорим о поиске массивов с сотнями или тысячами плиток на довольно регулярной основе.
Если я удостоверюсь, что плитки упорядочены, модифицированная реализация алгоритма двоичного поиска также может оказаться целесообразным.
Как вы думаете, как бы вы спроектировали быструю и эффективную систему координат?
Изменить: кто-то попросил меня опубликовать мой код:
public class Hexasphere
{
private Vector3 center;
private Array
points;
private Array faces;
private Model model;
private float radius = 3f;
private int subdivisions;

//ArrayMap latLon;
Float2ObjectArrayMap latLon;

public Hexasphere(int subdivisions)
{
points = new Array(true, 12);
faces = new Array(true, 20);
this.latLon = new Float2ObjectArrayMap(); //new ArrayMap();
this.center = new Vector3(0f, 0f, 0f);
this.subdivisions = subdivisions;

createIcosahedron();

subdivide(this.subdivisions);

tileIcosphere();

buildMesh();
}

//Based on the following articles:
// 1. http://blog.andreaskahler.com/2009/06/c ... -code.html
// 2. https://www.classes.cs.uchicago.edu/arc ... out-04.pdf
private void createIcosahedron()
{
float tao = 1.61803399f; //(float)(1.0f + Math.sqrt(5.0f)) / 2.0f;

Color[] colors = new Color[] {
Color.GREEN,
Color.RED,
Color.BLUE,
Color.BROWN,
Color.CHARTREUSE,
Color.CORAL,
Color.CYAN,
Color.DARK_GRAY,
Color.FIREBRICK,
Color.FOREST,
Color.GOLD,
Color.LIME,
Color.LIGHT_GRAY,
Color.OLIVE,
Color.SKY,
Color.SALMON
};

Point[] pnts = new Point[]
{
new Point(radius, tao * radius, 0),
new Point(-radius, tao * radius, 0),
new Point(radius,-tao * radius,0),
new Point(-radius,-tao * radius,0),
new Point(0, radius,tao * radius),
new Point(0,-radius,tao * radius),
new Point(0, radius,-tao * radius),
new Point(0,-radius,-tao * radius),
new Point(tao * radius,0, radius),
new Point(-tao * radius,0, radius),
new Point(tao * radius,0,-radius),
new Point(-tao * radius,0,-radius)
};

Triangle[] fces = new Triangle[]
{
new Triangle(this, 0, 1, 4, false),
new Triangle(this, 1, 9, 4, false),
new Triangle(this, 4, 9, 5, false),
new Triangle(this, 5, 9, 3, false),
new Triangle(this, 2, 3, 7, false),
new Triangle(this, 3, 2, 5, false),
new Triangle(this, 7, 10, 2, false),
new Triangle(this, 0, 8, 10, false),
new Triangle(this, 0, 4, 8, false),
new Triangle(this, 8, 2, 10, false),
new Triangle(this, 8, 4, 5, false),
new Triangle(this, 8, 5, 2, false),
new Triangle(this, 1, 0, 6, false),
new Triangle(this, 11, 1, 6, false),
new Triangle(this, 3, 9, 11, false),
new Triangle(this, 6, 10, 7, false),
new Triangle(this, 3, 11, 7, false),
new Triangle(this, 11, 6, 7, false),
new Triangle(this, 6, 0, 10, false),
new Triangle(this, 9, 1, 11, false)
};

for(int i = 0; i < pnts.length; i++)
{
Point p = pnts;
Color c = colors;
p.setColor(c);
points.add(p);
}

for(Triangle f : fces)
{
faces.add(f);
}
}

// Not implemented yet...
public void tileIcosphere()
{
for(int i = 0; i < points.size; i++)
{
Point p = points.get(i);
float polarAngle = (float)Math.acos(p.getPosition().z / getRadius());
float azimuthAngle = (float)Math.atan2(p.getPosition().y, p.getPosition().x);
float lat = 90f - polarAngle;
float lon = azimuthAngle;
//IcoSphereTile(this, points.get(i), IcoSphereTile.TileType.GRASS);
}
}

public void subdivide(int times)
{
// We are caching the old array of triangles because
// removeFace (called in the Triangle.subdivide() method) mutates our main array of triangles ("faces").
// If we just use "faces," then faces are removed and added during the loop,
// leading to infinite regression
// (size is always increasing faster than i is incrementing - by a factor
// of 4 new triangles per triangle iterated through)
// This is super inefficient for larger meshes/more subdivisions.
// We should be caching only the new triangles we create, and adding them to the main faces
for(int i = 0; i < times; i++)
{
var newFaces = new Array(faces);
for(int j = 0; j < newFaces.size; j++)
{
newFaces.get(j).subdivide();
}
//newFaces = new Array(faces);
}
}

public void addRawTriangle(Point p1, Point p2, Point p3)
{
short p1Idx, p2Idx, p3Idx;
p1Idx = (short)addPointIfDoesNotExist(p1);
p2Idx = (short)addPointIfDoesNotExist(p2);
p3Idx = (short)addPointIfDoesNotExist(p3);

Triangle tri = new Triangle(this, p1Idx, p2Idx, p3Idx);
faces.add(tri);
getPointAt(tri.getIdx1()).setIndex(tri.getIdx1());
getPointAt(tri.getIdx2()).setIndex(tri.getIdx2());
getPointAt(tri.getIdx3()).setIndex(tri.getIdx3());
}

//This doesn't remove vertices, it just removes the specific triangle/collection of indices that form the triangle.
public void removeTriangle(Triangle tri)
{
this.faces.removeValue(tri, true);
}

public void buildMesh()
{
ModelBuilder modelBuilder = new ModelBuilder();
MeshBuilder b = new MeshBuilder();

b.begin(VertexAttributes.Usage.Position | VertexAttributes.Usage.Normal |VertexAttributes.Usage.ColorUnpacked);
for(int i = 0; i < points.size; i++)
{
Point point = points.get(i);

b.vertex(
point.getPosition(),
point.getPosition(),
point.getColor(),
new Vector2(1, 1));
}
for(int i = 0; i < faces.size; i++)
{
b.index(faces.get(i).getIdx1());
b.index(faces.get(i).getIdx2());
b.index(faces.get(i).getIdx3());
}
Mesh mesh = b.end();
modelBuilder.begin();
modelBuilder.part("world", mesh, GL20.GL_TRIANGLES, new Material(ColorAttribute.createDiffuse(Color.WHITE)));
this.model = modelBuilder.end();
}

//Thank the Gods for this brave soul: https://gamedev.stackexchange.com/a/212473/60136
public ModelInstance instance()
{
return new ModelInstance(model);
}

public Point getPointAt(int index)
{
return points.get(index);
}

// Adds the point and returns its index if it does not exist.
// Returns the index of the point if it does exist.
public int addPointIfDoesNotExist(Point point)
{
int retval = -1;
for(int i = 0; i < points.size; i++)
{
Point other = points.get(i);
if(other == point || other.equals(point))
{
retval = i;
//Gdx.app.debug("Hexasphere", "Point " + point.getPosition() + " exists! Returning " + retval);
break;
}
}
if(retval == -1)
{
points.add(point);
retval = points.size - 1;
//Gdx.app.debug("Hexasphere", "Point " + point.getPosition() + " does not exist! Returning " + retval);
}

return retval;
}

public float getRadius()
{
return this.radius;
}

public Vector3 getCenter()
{
return this.center;
}

public void debugMesh(boolean verts, boolean faces)
{
String vertsDebug = "\n";
String facesDebug = "\n";

if(verts)
for(Point p : points)
vertsDebug += "point [" + p.getPosition().toString() + "]\n";
vertsDebug += "Vert Count: " + points.size;
if(faces)
for(Triangle f : this.faces)
facesDebug += "face [" + f.toString() + "]\n";
facesDebug += "Face Count: " + this.faces.size;
Gdx.app.log("Vertices", vertsDebug);
Gdx.app.log("Faces", facesDebug);
}
}

А это мой класс Triangle:
public class Triangle
{
private Hexasphere hexasphere;
private int index1, index2, index3;

public Triangle(Hexasphere hexasphere, int idx1, int idx2, int idx3)
{
this(hexasphere, idx1, idx2, idx3, false);
}

public Triangle(Hexasphere hexasphere, int idx1, int idx2, int idx3, boolean trackFaceInPoints)
{
this.hexasphere = hexasphere;
this.index1 = idx1;
this.index2 = idx2;
this.index3 = idx3;
}

public void subdivide()
{
//The three initial points.
Point p1 = hexasphere.getPointAt(index1);
Point p2 = hexasphere.getPointAt(index2);
Point p3 = hexasphere.getPointAt(index3);
Point[] oldPoints = new Point[] {p1, p2, p3};
projectToSphere(p1.getPosition(), hexasphere.getCenter());
projectToSphere(p2.getPosition(), hexasphere.getCenter());
projectToSphere(p3.getPosition(), hexasphere.getCenter());

//The three new points.
Point p4 = getMidPoint(hexasphere.getPointAt(index1), hexasphere.getPointAt(index2));
Point p5 = getMidPoint(hexasphere.getPointAt(index1), hexasphere.getPointAt(index3));
Point p6 = getMidPoint(hexasphere.getPointAt(index2), hexasphere.getPointAt(index3));
projectToSphere(p4.getPosition(), hexasphere.getCenter());
projectToSphere(p5.getPosition(), hexasphere.getCenter());
projectToSphere(p6.getPosition(), hexasphere.getCenter());

Point[] newPoints = new Point[] {p4, p5, p6};
for(int i = 0; i < newPoints.length; i++)
newPoints.setColor(oldPoints.getColor().cpy());

hexasphere.addRawTriangle(p6, p3, p5);
hexasphere.addRawTriangle(p5, p1, p4);
hexasphere.addRawTriangle(p4, p6, p5);
hexasphere.addRawTriangle(p6, p4, p2);

hexasphere.removeTriangle(this);
}

private Point getMidPoint(Point p1, Point p2)
{
Vector3 p1Pos = p1.getPosition();
Vector3 p2Pos = p2.getPosition();

float x1 = p1Pos.x, y1 = p1Pos.y, z1 = p1Pos.z;
float x2 = p2Pos.x, y2 = p2Pos.y, z2 = p2Pos.z;
return new Point((x1 + x2)/2f, (y1 + y2)/2f, (z1 + z2) / 2f);
}

private void projectToSphere(Vector3 objVector, Vector3 centerVector)
{
//Magnitude = sqrt((x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)²)
float xDistance = (float)(Math.pow((objVector.x-centerVector.x), 2d));
float yDistance = (float)(Math.pow((objVector.y-centerVector.y), 2d));
float zDistance = (float)(Math.pow((objVector.z-centerVector.z), 2d));
float magnitude = (float)Math.sqrt((xDistance + yDistance + zDistance));
objVector.x /= magnitude / hexasphere.getRadius();
objVector.y /= magnitude / hexasphere.getRadius();
objVector.z /= magnitude / hexasphere.getRadius();
}

public Point getPoint1()
{
return hexasphere.getPointAt(index1);
}

public Point getPoint2()
{
return hexasphere.getPointAt(index2);
}

public Point getPoint3()
{
return hexasphere.getPointAt(index3);
}

public short getIdx1()
{
return (short)index1;
}

public short getIdx2()
{
return (short)index2;
}

public short getIdx3()
{
return (short)index3;
}

@Override
public String toString()
{
return "{" + getIdx1() + ", " + getIdx2() + ", " + getIdx3() + "}";
}
}


Подробнее здесь: https://stackoverflow.com/questions/792 ... sed-on-loc