Сферическая диаграмма Вороного, разбиение двоичного подхода


Редактировать: мой код не работает, смотри https://gis.stackexchange.com/questions/294380/if-rectangle-corner-points-have-same-nearest-neighbor-does-whole-interior

Дали 5 (в настоящее время жестко) городов, этот код использует карты Google, чтобы раскол мира на 5 регионов, каждый регион является точки ближе к данного города, чем другие 4.

Он работает, но медленно в двух смыслах:

  • Программа занимает много времени, особенно когда $minarea мала.

  • Программа генерирует множество полигонов, замедляя карте Google выше. С меньшими '$minarea', я даже выбежать на JavaScript стекового пространства.

Подумал: что-то ж/ qhull быть быстрее?

В bvoronoi подпрограмма делает большую часть работы:

#!/bin/perl

# Unusual approach to Voronoi diagram of Earth sphere: cut into 4
# pieces and compare closest point for 4 vertices

# TODO: this program is long and clumsy and can doubtless be improved

use POSIX;

# defining constants here is probably bad
$PI = 4.*atan(1);
$EARTH_RADIUS = 6371/1.609344; # miles

open(A,">/home/barrycarter/BCINFO/sites/TEST/gvorbin.txt");

# latitude and longitude of points
%points = (
 "Albuquerque" => "35.08 -106.66",
 "Paris" => "48.87 2.33",
 "Barrow" => "71.26826 -156.80627",
 "Wellington" => "-41.2833 174.783333",
 "Rio" => "-22.88  -43.28"
);

# primartish colors
%colors = (
 "Albuquerque" => "#ff0000",
 "Paris" => "#00ff00",
 "Barrow" => "#0000ff",
 "Wellington" => "#ffff00",
 "Rio" => "#ff00ff",
 "BORDER" => "#000000"
);

# stop at what gridsize
$minarea = .5;

# the four psuedo-corners of the globe
$nw = bvoronoi(0,90,-180,0);
$ne = bvoronoi(0,90,0,180);
$sw = bvoronoi(-90,0,-180,0);
$se = bvoronoi(-90,0,0,180);

for $i (split("\n","$nw\n$ne\n$sw\n$se")) {
  # create google filled box
  my($latmin, $latmax, $lonmin, $lonmax, $closest) = split(/\s+/, $i);

  # build up the coords
  print A << "MARK";

var myCoords = [
 new google.maps.LatLng($latmin, $lonmin),
 new google.maps.LatLng($latmin, $lonmax),
 new google.maps.LatLng($latmax, $lonmax),
 new google.maps.LatLng($latmax, $lonmin),
 new google.maps.LatLng($latmin, $lonmin)
];

myPoly = new google.maps.Polygon({
 paths: myCoords,
 strokeColor: "$colors{$closest}",
 strokeOpacity: 1,
 strokeWeight: 0,
 fillColor: "$colors{$closest}",
 fillOpacity: 0.5
});

myPoly.setMap(map);

MARK
;

}

# workhorse function: given a "square" (on an equiangular map),
# determine the closest point of 4 vertices; if same, return square
# and point; otherwise, break square into 4 squares and recurse

sub bvoronoi {
  # Using %points as global is ugly
  my($latmin, $latmax, $lonmin, $lonmax) = @_;
  my($mindist, $dist, %closest);

  # compute distance to each %points for each corner
  # TODO: this is wildly inefficient, since I just need relative
  # distance, not exact!
  for $lat ($latmin,$latmax) {
    for $lon ($lonmin,$lonmax) {
      # TODO: has to be easier way to do this?
      $mindist = 0; $dist= 0;
      for $point (keys %points) {
        my($plat,$plon) = split(/\s+/, $points{$point});
        $dist = gcdist($lat, $lon, $plat, $plon);
        if ($dist < $mindist || !$mindist) {
          $mindist = $dist;
          $minpoint = $point;
        }
      }
      # this point is closest to one vertex of the square
      # TODO: should abort loop if we already have two different closest points
      $closest{$minpoint} = 1;
    }
  }

  # if there's just one point closest to all four corners, return it
  my(@keys) = keys %closest;

  # if @keys has length 1, return it
  unless ($#keys) {
    return "$latmin $latmax $lonmin $lonmax $keys[0]";
  }

  # if we've hit a border point, return it (area too small)
  my($area) = ($latmax-$latmin)*($lonmax-$lonmin);

  if ($area <= $minarea) {
    return "$latmin $latmax $lonmin $lonmax BORDER";
  }

  # split square and recurse
  my($latmid) = ($latmax+$latmin)/2.;
  my($lonmid) = ($lonmax+$lonmin)/2.;

  my(@sub) = ();
  push(@sub, bvoronoi($latmin, $latmid, $lonmin, $lonmid));
  push(@sub, bvoronoi($latmid, $latmax, $lonmin, $lonmid));
  push(@sub, bvoronoi($latmin, $latmid, $lonmid, $lonmax));
  push(@sub, bvoronoi($latmid, $latmax, $lonmid, $lonmax));

  return join("\n", @sub);
}

=item gcdist($x,$y,$u,$v)

Great circle distance between latitude/longitude x,y and
latitude/longitude u,v in miles Source: http://williams.best.vwh.net/avform.htm

=cut

sub gcdist {
    my(@x)=@_;
    my($x,$y,$u,$v)=map {$_*=$PI/180} @x;
    my($c1) = cos($x)*cos($y)*cos($u)*cos($v);
    my($c2) = cos($x)*sin($y)*cos($u)*sin($v);
    my($c3) = sin($x)*sin($u);
    return ($EARTH_RADIUS*acos($c1+$c2+$c3));
}

Еще один неудачный подход

Редактировать: спасибо всем, кто поставили плюс за это. Я сейчас исправил http://test.barrycarter.info/gmap8.php ссылку и я в том числе скриншоте ниже:

enter image description here



Комментарии
1 ответ

Короче, попробовать cssgrid от НЦАИ графика.

В длину:

Есть похожие вопросы на StackOverflow, но это не принято отвечать.

Так вот ответ, если вы позволите два извинения. 1. Я оставлю Карты Google работать на вас. 2. Я не внимательно прочитал ваш код.

Время работы алгоритма должно быть выше того, чем сортировка за o(n записей N). По крайней мере, "диаграммы Вороного на сфере", открыто доступен в Утрехтском университете доклад, утверждает, что результат в Кевин Кинтин коричневый диссертации. Кроме того,"на строительстве Вороного сетки на сфере" требований в абстрактной для построения сетки в o(Н).

Похоже, qhull не делать все, что вам нужно, но я нашел еще кое-что. В cssgrid пакет нашли в GPL-лицензированных НЦАИ графическое программное обеспечение и делает то, что вам нужно, в C, Fortran и НЦАИ-конкретных Привязок. Вы можете скачать все НЦАИ графика от его страницы (США), Национальный центр атмосферных исследований. Если вы хотите, вы можете использовать глоток, чтобы сделать соответствующие с обязательным имеющиеся в Perl.

В cssgrid пакет имеет свою собственную документацию страницы онлайн. Функции *csvoro* (вороной) и *css2c* (сферических в декартовы, то есть широты и долготы в Х-Y-Z координаты) являются наиболее актуальными.

Пакет cssgrid базируется на STRIPACK с разрешения автора STRIPACK по. STRIPACK поднимается выше, в интернете и бесплатно для некоммерческого использования. Однако, STRIPACK себя как АСМ Томс алгоритм является ни общественным достоянием и не совместима с GPL. Также это Фортран 90 код без предоставленных c обязательным, хотя эти трудности могут быть преодолимы с помощью FortWrap.

5
ответ дан 19 марта 2012 в 04:03 Источник Поделиться