Administrace komentářů

Ahoj,

nevím jak efektivně řešit tento problém. Mám pole bodů, a potřeboval bych funkci, která by co nejefektivněji našla nejkratší vzdálenost pro danou pozici. Naprosto triviálně to lze řešit lineárním prohledáváním, ale to je z hlediska výkonu nepoužitelné. Pro lepší porozumění předložím malý prototyp, kterým bych chtěl lépe vysvětlit, o co mi jde:

struct DistancePoint
{
  double x, y;
};

struct DistanceFinder
{
  DistanceFinder();
  ~DistanceFinder();

  bool init(const DistancePoint* p, int count);
  void free();
  double find(double inX, double inY);
  void findSpan(double x, double y, int count, double* results);

  DistancePoint* _data;
  int _count;
};

DistanceFinder::DistanceFinder() :
  _data(NULL)
{
}

DistanceFinder::~DistanceFinder()
{
  free();
}

bool DistanceFinder::init(const DistancePoint* p, int count)
{
  free();
  if (!count) return false;

  _data = (DistancePoint*)malloc(count * sizeof(DistancePoint));
  if (!_data) return false;

  memcpy(_data, p, count * sizeof(DistancePoint));
  return true;
}

void DistanceFinder::free()
{
  if (_data) { ::free(_data); _data = NULL; }
}

double DistanceFinder::find(double x, double y)
{
  double dist = fabs((_data[0].x - x) * (_data[0].y - y));

  for (int i = 1; i < _count; i++)
  {
    double d = fabs((_data[i].x - x) * (_data[i].y - y));
    if (dist > d) dist = d;
  }

  return sqrt(dist);
}

a teď stručně charakteristiku a pár typů k optimalizaci:

• množství bodů se po initializaci nebude měnit, init() tedy má možnost vytvořit a inicializovat další datové struktury potřebné k hledání (binární stromy, atd).
• protože to chci použít v počítačové grafice, jedna z optimalizací může využít fakt, že budu potřebovat hledat vždy pozice, které mají stejnou Y souřanici a na ose X budu přičítat 1.0.

void DistanceFinder::findSpan(double x, double y, int count, double* results)
{
  for (int i = 0; i < count; i++, x += 1.0) 
    results[i] = find(x, y);
}

Tak co, věděl by někdo, jakým směrem mám jít? Potřeboval bych vědět, jaké nejlepší datové struktury a algoritmy volit pro vytvoření dat, které použiju k efektivnímu vyhledání. Budu používat metodu findSpan(), takže samotná find() není vůbec důležitá.

Chtěl bych to použít na generování podobných obrázků jako tyto.