Skip to content

Instantly share code, notes, and snippets.

@fuCtor
Created January 18, 2017 05:37
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save fuCtor/a4ebb23df0b644e25bc55a953b097ba1 to your computer and use it in GitHub Desktop.
#include "TileInfo.h"
#include <cstdlib>
#include <math.h>
#include <QDebug>
#define PACK_LEVEL 3
#define MAX_LEVEL 18
#define EDGE_LEVEL 12
#define SIZE pow(4.0, MAX_LEVEL)
#define INDEX_MIX_SEGMENT(x,y, i) ((x & (1 << (i))) << (i)) | ((y & (1 << (i))) << (i+1))
using namespace std;
void ConvertToLocal(int oX, int oY, QPoint &point)
{
point.setX(point.x() - oX);
point.setY(point.y() - oY);
}
TileInfo::TileInfo(uint32_t oZ, uint32_t oX, uint32_t oY)
{
OffsetX = oX;
OffsetY = oY;
OffsetZ = oZ;
Offset = GetIndex(oX, oY);
OffsetP = GetIndex((oX >> PACK_LEVEL * 2) , (oY >> PACK_LEVEL * 2));
MAX_LOCAL_LEVEL = MAX_LEVEL - OffsetZ;
uint32_t dimension = (uint32_t)pow(4.0, (int)(MAX_LOCAL_LEVEL - PACK_LEVEL));
Tiles.resize(dimension);
Tiles.fill(0);
};
TileInfo::~TileInfo()
{
};
void TileInfo::SetOffsetX(uint32_t oX)
{
OffsetX = oX;
};
void TileInfo::SetOffsetY(uint32_t oY)
{
OffsetY = oY;
};
uint64_t TileInfo::GetIndex(uint32_t x, uint32_t y)
{
uint64_t result = 0;
int i = 0;
result = INDEX_MIX_SEGMENT(x,y, 0) |
INDEX_MIX_SEGMENT(x,y, 1) |
INDEX_MIX_SEGMENT(x,y, 2) |
INDEX_MIX_SEGMENT(x,y, 3) |
INDEX_MIX_SEGMENT(x,y, 4) |
INDEX_MIX_SEGMENT(x,y, 5) |
INDEX_MIX_SEGMENT(x,y, 6) |
INDEX_MIX_SEGMENT(x,y, 7);
result = result |
INDEX_MIX_SEGMENT(x,y, 8) |
INDEX_MIX_SEGMENT(x,y, 9) |
INDEX_MIX_SEGMENT(x,y, 10) |
INDEX_MIX_SEGMENT(x,y, 11) |
INDEX_MIX_SEGMENT(x,y, 12) |
INDEX_MIX_SEGMENT(x,y, 13) |
INDEX_MIX_SEGMENT(x,y, 14) |
INDEX_MIX_SEGMENT(x,y, 15);
result = result |
INDEX_MIX_SEGMENT(x,y, 16) |
INDEX_MIX_SEGMENT(x,y, 17) |
INDEX_MIX_SEGMENT(x,y, 18) |
INDEX_MIX_SEGMENT(x,y, 19) |
INDEX_MIX_SEGMENT(x,y, 20) |
INDEX_MIX_SEGMENT(x,y, 21) |
INDEX_MIX_SEGMENT(x,y, 22) |
INDEX_MIX_SEGMENT(x,y, 23);
result = result |
INDEX_MIX_SEGMENT(x,y, 24) |
INDEX_MIX_SEGMENT(x,y, 25) |
INDEX_MIX_SEGMENT(x,y, 26) |
INDEX_MIX_SEGMENT(x,y, 27) |
INDEX_MIX_SEGMENT(x,y, 28) |
INDEX_MIX_SEGMENT(x,y, 29) |
INDEX_MIX_SEGMENT(x,y, 30) |
INDEX_MIX_SEGMENT(x,y, 31);
return result;
};
int TileInfo::GetValue(uint32_t x, uint32_t y, uint32_t z)
{
if(z < EDGE_LEVEL)
{
int sx = x << (EDGE_LEVEL - z),
sy = y << (EDGE_LEVEL - z),
fx = (x+1) << (EDGE_LEVEL - z),
fy = (y+1) << (EDGE_LEVEL - z);
for(x = sx; x < fx; ++x)
{
for(y = sy; y < fy; ++y)
{
if(GetValue(x,y, EDGE_LEVEL))
return 1;
}
}
return 0;
}
uint64_t N = GetIndex(x, y);
uint32_t tmp_x = (x << (MAX_LEVEL - z)),
tmp_y = (y << (MAX_LEVEL - z));
tmp_x = qMax(tmp_x, OffsetX);
tmp_y = qMax(tmp_y, OffsetY);
uint64_t StartIndex = GetIndex(tmp_x - OffsetX, tmp_y - OffsetY);
uint64_t FinishIndex = StartIndex + (1 << ((MAX_LEVEL - z) *2));
if (z <= MAX_LEVEL - PACK_LEVEL)
{
int id = 0; // Показывает, что обнаружена единица
StartIndex = StartIndex >> (PACK_LEVEL*2);//(PACK_LEVEL * 2);
FinishIndex = FinishIndex >> (PACK_LEVEL*2 );//(PACK_LEVEL * 2);
for (int i = StartIndex; i < FinishIndex; i++)
{
if ( i >= Tiles.count() || Tiles[i] != 0)
{
id = 1;
break;
}
}
return id;
}
else
{
int Index = StartIndex >> (PACK_LEVEL*2);
StartIndex = (StartIndex ) % 64;
uint64_t Mask;
if(Index >= Tiles.count())
return 1;
switch(MAX_LEVEL - z)
{
case 0:
Mask = 0x1;
Mask = (Mask << StartIndex) & Tiles[Index];
return Mask?1:0;
case 1:
Mask = 0xF;
Mask = (Mask << StartIndex) & Tiles[Index];
return Mask?1:0;
case 2:
Mask = 0xFFFF;
Mask = (Mask << StartIndex) & Tiles[Index];
return Mask?1:0;
}
}
};
void TileInfo::WriteValue(uint32_t x, uint32_t y, uint32_t Value)
{
uint64_t StartIndex = GetIndex(x - OffsetX, y - OffsetY);
int Index = StartIndex >> (PACK_LEVEL*2); // Номер элемента массива из 64-разрядных чисел
if (Index >= Tiles.count())
{
return;
}
StartIndex %= 64;
if (Value)
{
uint64_t Mask = 0x1;
uint64_t Temp = Mask << StartIndex;
Tiles[Index] = Tiles[Index] | Temp;
}
else
{
uint64_t Mask = 0x1;
uint64_t Temp = Mask << StartIndex;
Temp = ~Temp;
Tiles[Index] = Tiles[Index] & Temp;
}
};
int round(double number)
{
return (number >= 0) ? (int)(number + 0.5) : (int)(number - 0.5);
};
void TileInfo::DDAline(float x1, float y1, float x2, float y2)
{
int i, L, xstart, ystart, xend, yend;
float dX, dY, x[1000], y[1000];
xstart = round(x1);
ystart = round(y1);
xend = round(x2);
yend = round(y2);
L = max(abs(xend-xstart), abs(yend-ystart));
dX = (x2-x1)/L;
dY = (y2-y1)/L;
i = 0;
x[i] = x1;
y[i] = y1;
i++;
while (i < L)
{
x[i] = x[i-1] + dX;
y[i] = y[i-1] + dY;
i++;
}
x[i] = x2;
y[i] = y2;
i = 0;
while (i <= L)
{
/*WriteValue(ceil(x[i]), ceil(y[i]), 1);
WriteValue(floor(x[i]), floor(y[i]), 1);
WriteValue(ceil(x[i]), floor(y[i]), 1);
WriteValue(floor(x[i]), ceil(y[i]), 1);
*/
WriteValue(ceil(x[i]-1), ceil(y[i]), 1);
WriteValue(floor(x[i]-1), floor(y[i]), 1);
WriteValue(ceil(x[i]-1), floor(y[i]), 1);
WriteValue(floor(x[i]-1), ceil(y[i]), 1);
WriteValue(ceil(x[i]+1), ceil(y[i]), 1);
WriteValue(floor(x[i]+1), floor(y[i]), 1);
WriteValue(ceil(x[i]+1), floor(y[i]), 1);
WriteValue(floor(x[i]+1), ceil(y[i]), 1);
WriteValue(ceil(x[i]), ceil(y[i]-1), 1);
WriteValue(floor(x[i]), floor(y[i]-1), 1);
WriteValue(ceil(x[i]), floor(y[i]-1), 1);
WriteValue(floor(x[i]), ceil(y[i]-1), 1);
WriteValue(ceil(x[i]), ceil(y[i]+1), 1);
WriteValue(floor(x[i]), floor(y[i]+1), 1);
WriteValue(ceil(x[i]), floor(y[i]+1), 1);
WriteValue(floor(x[i]), ceil(y[i]+1), 1);
i++;
}
};
void TileInfo::FullPolygon(QVector<QPoint> TP)
{
int minX, minY, maxX, maxY;
minX = maxX = TP[0].x();
minY = maxY = TP[0].y();
if (TP.size() == 1)
{
WriteValue(minX, minY, 1);
return;
}
else
{
for(int i = 1 ; i < TP.size() ; ++i) // Расчет границ прямоугольника, охватывающего полигон
{
minX = minX <= TP[i].x() ? minX : TP[i].x();
maxX = maxX >= TP[i].x() ? maxX : TP[i].x();
minY = minY <= TP[i].y() ? minY : TP[i].y();
maxY = maxY >= TP[i].y() ? maxY : TP[i].y();
}
for (int i = 0; i < TP.size() - 1; i++) // Заполнение границ полигона
{
int X1 = TP[i].x();
int Y1 = TP[i].y();
int X2 = (i == TP.size() - 1 ? TP[0].x() : TP[i+1].x());
int Y2 = (i == TP.size() - 1 ? TP[0].y() : TP[i+1].y());
DDAline (X1, Y1, X2, Y2);
}
int Width = maxX - minX;
int Height = maxY - minY;
QVector<bool> Mask((Width + 1) * (Height + 1));
for (int i = 0; i < (Width + 1) * (Height + 1); i++) Mask[i] = true;
int j = 0;//minY;
for (int i = 0; i <= Width; i++)
{
while (!GetValue(i + minX, j + minY, MAX_LEVEL))
{
Mask[Width*j + i] = false;
j++;
}
j = 0;
}
j = Height;//maxY;
for (int i = 0; i <= Width; i++)
{
while (!GetValue(i + minX, j + minY, MAX_LEVEL))
{
Mask[Width*j + i] = false;
j--;
}
j = Height;
}
int i = 0;//minX;
for (int j = 0; j <= Height; j++)
{
while (!GetValue(i + minX, j + minY, MAX_LEVEL))
{
Mask[Width*j + i] = false;
i++;
}
i = 0;
}
i = Width;//maxX;
for (int j = 0; j <= Height; j++)
{
while (!GetValue(i + minX, j + minY, MAX_LEVEL))
{
Mask[Width*j + i] = false;
i--;
}
i = Width;
}
for (int j = 0; j < Height ; j++) // Заполняем полигон
{
for (int i = 0; i < Width; i++)
if (Mask[Width*j + i]) WriteValue(i + minX, j + minY, 1);
}
}
}
#pragma once
#include <QVector>
#include <vapi\utils\inttypes.h>
class TileInfo
{
private:
QVector<uint64_t> Tiles;
uint32_t MAX_LOCAL_LEVEL;
uint32_t OffsetX;
uint32_t OffsetY;
uint32_t OffsetZ;
uint32_t Offset, OffsetP;
public:
TileInfo(uint32_t oZ, uint32_t oX, uint32_t oY);
~TileInfo();
uint64_t GetIndex(uint32_t x, uint32_t y);
int GetValue(uint32_t x, uint32_t y, uint32_t z);
void WriteValue(uint32_t x, uint32_t y, uint32_t Value);
void DDAline(float x1, float y1, float x2, float y2);
void FullPolygon(QVector<QPoint> TP);
void SetOffsetX(uint32_t oX);
void SetOffsetY(uint32_t oY);
};
int round(double number);
void ConvertToLocal(int oX, int oY, QPoint & point);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment