Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Z曲線とかどうなの?
package com.ashigeru.appengine.query.tiling.controller.zorder;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.arnx.jsonic.JSON;
import org.slim3.controller.Controller;
import org.slim3.controller.Navigation;
import org.slim3.datastore.Datastore;
import com.ashigeru.appengine.query.tiling.meta.ZOrderVectorMeta;
import com.ashigeru.appengine.query.tiling.model.DistanceComparator;
import com.ashigeru.appengine.query.tiling.model.ZOrderVector;
import com.google.appengine.api.datastore.Query.FilterOperator;
import com.google.appengine.api.datastore.Query.SortDirection;
public class AddController extends Controller {
private static final int CANDIDATES = 10;
@Override
public Navigation run() throws Exception {
String name = asString("name");
Integer d1 = asInteger("d1");
Integer d2 = asInteger("d2");
Integer d3 = asInteger("d3");
Integer d4 = asInteger("d4");
if (name == null || d1 == null || d2 == null || d3 == null || d4 == null) {
return null;
}
ZOrderVector vector = new ZOrderVector(d1, d2, d3, d4);
vector.setName(name);
ZOrderVectorMeta m = ZOrderVectorMeta.get();
// Z-Orderingの前後を取得
List<ZOrderVector> front = Datastore.query(m)
.filter("ordering", FilterOperator.LESS_THAN_OR_EQUAL, vector.getOrdering())
.limit(CANDIDATES + 1)
.sort("ordering", SortDirection.DESCENDING)
.asList();
List<ZOrderVector> back = Datastore.query(m)
.filter("ordering", FilterOperator.GREATER_THAN, vector.getOrdering())
.limit(CANDIDATES)
.sort("ordering", SortDirection.ASCENDING)
.asList();
// ユークリッド距離で並べなおす
List<ZOrderVector> candidates = new ArrayList<ZOrderVector>();
candidates.addAll(front);
candidates.addAll(back);
Collections.sort(candidates, new DistanceComparator(vector));
// ついでに自分も保存しておく
Datastore.put(vector);
List<Map<String, Object>> results = new ArrayList<Map<String, Object>>();
for (int i = 0, n = Math.min(candidates.size(), 3); i < n; i++) {
Map<String, Object> entry = new HashMap<String, Object>();
ZOrderVector found = candidates.get(i);
entry.put("name", found.getKey().getName());
entry.put("vector", found.getVector());
entry.put("distance", vector.distanceTo(found));
results.add(entry);
}
JSON.encode(results, response.getWriter(), true);
return null;
}
}
package com.ashigeru.appengine.query.tiling.model;
/**
* バイト配列を操作する。
* @author ashigeru
*/
public class ByteArrayBuilder {
private byte[] bytes;
public ByteArrayBuilder(int numberOfBytes) {
bytes = new byte[numberOfBytes];
}
public static ByteArrayBuilder fromDouble(double value) {
ByteArrayBuilder result = new ByteArrayBuilder(8);
long bits = Double.doubleToRawLongBits(value);
for (int b = 0; b < 8; b++) {
result.bytes[b] = (byte) (bits >>> (Double.SIZE - (b + 1) * 8));
}
return result;
}
public static ByteArrayBuilder fromInt(int value) {
ByteArrayBuilder result = new ByteArrayBuilder(4);
for (int b = 0; b < 4; b++) {
result.bytes[b] = (byte) (value >>> (Integer.SIZE - (b + 1) * 8));
}
return result;
}
public void set(int offset, boolean value) {
int byteOffset = offset / 8;
int bitOffset = offset % 8;
byte mask = (byte) (0x80 >>> bitOffset);
if (value) {
bytes[byteOffset] |= mask;
}
else {
bytes[byteOffset] &= ~mask;
}
}
public boolean get(int offset) {
int byteOffset = offset / 8;
int bitOffset = offset % 8;
byte mask = (byte) (0x80 >>> bitOffset);
return (bytes[byteOffset] & mask) != 0;
}
public byte[] getBytes() {
return this.bytes;
}
}
package com.ashigeru.appengine.query.tiling.model;
import java.util.Comparator;
/**
* 基点からの距離を基にした比較。
* @author ashigeru
*/
public class DistanceComparator implements Comparator<ZOrderVector> {
private ZOrderVector origin;
public DistanceComparator(ZOrderVector origin) {
this.origin = origin;
}
public int compare(ZOrderVector o1, ZOrderVector o2) {
double d1 = origin.distanceTo(o1);
double d2 = origin.distanceTo(o2);
return Double.compare(d1, d2);
}
}
package com.ashigeru.appengine.query.tiling.model;
import java.util.Arrays;
import org.slim3.datastore.Attribute;
import org.slim3.datastore.Datastore;
import org.slim3.datastore.Model;
import com.google.appengine.api.datastore.Key;
import com.google.appengine.api.datastore.ShortBlob;
/**
* Z曲線用のビット列を持つ多次元ベクトル。
* @author ashigeru
*/
@Model
public class ZOrderVector {
@Attribute(primaryKey = true)
private Key key;
@Attribute(lob = true)
private int[] vector;
private ShortBlob ordering;
public ZOrderVector() {
return;
}
public ZOrderVector(int...vector) {
this.vector = vector;
ordering = new ShortBlob(computeOrder(vector));
}
private static byte[] computeOrder(int[] vector) {
int dimensions = vector.length;
ByteArrayBuilder results = new ByteArrayBuilder(dimensions * 8);
for (int i = 0; i < dimensions; i++) {
ByteArrayBuilder bits = ByteArrayBuilder.fromInt(vector[i]);
for (int offset = 0; offset < Integer.SIZE; offset++) {
results.set(offset * dimensions + i, bits.get(offset));
}
}
return results.getBytes();
}
public double distanceTo(ZOrderVector other) {
int[] v1 = vector;
int[] v2 = other.vector;
if (v1.length != v2.length) {
return Double.NaN;
}
double sum = 0.0;
for (int i = 0; i < v1.length; i++) {
double diff = v1[i] - v2[i];
sum += diff * diff;
}
return Math.sqrt(sum);
}
@Override
public String toString() {
return Arrays.toString(vector);
}
public Key getKey() {
return this.key;
}
public void setKey(Key key) {
this.key = key;
}
public int[] getVector() {
return this.vector;
}
public void setVector(int[] vector) {
this.vector = vector;
}
public ShortBlob getOrdering() {
return this.ordering;
}
public void setOrdering(ShortBlob order) {
this.ordering = order;
}
public void setName(String name) {
this.key = Datastore.createKey(ZOrderVector.class, name);
}
}
@ashigeru

This comment has been minimized.

Copy link
Owner Author

@ashigeru ashigeru commented May 12, 2010

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment