gpt4 book ai didi

java - 在矩形流中进行快速点搜索

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:23:34 25 4
gpt4 key购买 nike

问题是:

我有一个轴对齐的矩形流,由它们的对角线端点 [x1,y1] 和 [x2,y2] 描述,其中 x1 < x2 和 y1 < y2。

在某些时候,我会得到一个点:[x,y]。我需要找到包含该点的所有矩形。

最快的方法是什么?我想以插入为代价优化查找时间。由于它是流,因此我不必在查找期间从头开始构建此结构。

我不确定范围树是否适合这个,因为 [x1,y1] 和 [x2,y2] 不是独立的。

编辑:请注意,在获得查询后,我将从流中获得更多矩形,然后是另一个查询点,依此类推。另外,我也可能会被要求忽略矩形,所以应该也支持删除。如果我可以使用现有的 Java 库而无需实现我自己的区间/线段树,则可加分。

最佳答案

我认为你可以通过分别考虑这两个维度来简化这个问题。

构建一个有序的数据结构,该结构对于范围的每个部分都有一个条目,该范围共享同一组封闭矩形 X 维度范围。到目前为止,分割点将是输入中 x1 或 x2 的值。对于每个子范围,存储其 X 维度范围覆盖该子范围的矩形集。

对 Y 维度做同样的事情。

要查找 [x, y],请使用二进制搜索或类似方法找到包含 x 的 X 维度子范围和包含 y 的 Y 维度子范围。这两个子范围的矩形集的交集是每个包含 [x,y] 的矩形集。

这是 Java 中的基本概念验证实现,与其说是完整的实现,不如说是阐明想法的伪代码。我做了非常有限的测试。我使用 ArrayList 来跟踪范围 - 真正的实现更有可能使用某种形式的平衡树。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RectangleTest {
RangeList xRanges = new RangeList();
RangeList yRanges = new RangeList();


public static void main(String[] args) {
RectangleTest rectangleTest = new RectangleTest();
rectangleTest.test();
}

private void test() {
Rectangle[] rectangles = new Rectangle[]{
new Rectangle(2,100,4,102),
new Rectangle(2,102,4,200),
};
add(rectangles[0]);
add(rectangles[1]);
testit(0,0);
testit(3,101);
testit(4,101);
testit(4,102);
delete(rectangles[0]);
testit(3,101);
testit(4,101);
testit(4,102);
}

private void testit(int x, int y){
System.out.println("("+x+","+y+") is in "+getRectangles(x,y));
}

void add(Rectangle rectangle) {
System.out.println("Adding: "+rectangle);
xRanges.addRectangle(rectangle.x1, rectangle.x2, rectangle);
yRanges.addRectangle(rectangle.y1, rectangle.y2, rectangle);
}

void delete(Rectangle rectangle){
System.out.println("Deleting: "+rectangle);
xRanges.deleteRectangle(rectangle.x1, rectangle.x2, rectangle);
yRanges.deleteRectangle(rectangle.y1, rectangle.y2, rectangle);
}

Set<Rectangle> getRectangles(int x, int y){
Set<Rectangle> result = xRanges.lookup(x);
result.retainAll(yRanges.lookup(y));
return result;
}
}

/* A Range represents a range of locations in one dimension, and
* and associated set of rectangles.
*/
class Range {
int start;
Set<Rectangle> rectangles;

Range(int start) {
this(start, new HashSet<Rectangle>());
}

Range(int start, Set<Rectangle> rectangles) {
this.start = start;
this.rectangles = rectangles;
}

void add(Rectangle rectangle) {
rectangles.add(rectangle);
}

void remove(Rectangle rectangle) {
rectangles.remove(rectangle);
}
}

/* A RangeList represents all ranges in one dimension.*/
class RangeList {
List<Range> ranges = new ArrayList<Range>();
static final int endAll = Integer.MAX_VALUE;

RangeList() {
ranges.add(new Range(0));
}

void addRectangle(int start, int end, Rectangle rectangle) {
int startIndex = getIndex(start);
Range startRange = ranges.get(startIndex);
if (start > startRange.start) {
// Need to split the start range
startIndex++;
ranges.add(startIndex, new Range(start, new HashSet<Rectangle>(
startRange.rectangles)));
}
int endIndex = getIndex(end);
Range endRange = ranges.get(endIndex);
if (end > endRange.start) {
// Need to split the end range
ranges.add(endIndex + 1, new Range(end, new HashSet<Rectangle>(
endRange.rectangles)));
}
// Add the rectangle to its ranges
for (int i = startIndex; i <= endIndex; i++) {
ranges.get(i).rectangles.add(rectangle);
}

}

void deleteRectangle(int start, int end, Rectangle rectangle) {
int startIndex = getIndex(start);
int endIndex = getIndex(end);
// Remove the rectangle from each range it is in
for (int i = startIndex; i <= endIndex; i++) {
ranges.get(i).rectangles.remove(rectangle);
}
// Merge ranges that now have equal rectangle sets
for (int i = endIndex; i >= Math.max(startIndex, 1); i--) {
if (ranges.get(i).rectangles.equals(ranges.get(i - 1).rectangles)) {
ranges.remove(i);
}
}
}

Set<Rectangle> lookup(int location) {
int index = getIndex(location);
Range range = ranges.get(index);
Set<Rectangle> result = new HashSet<Rectangle>(range.rectangles);
if (location == range.start && index > 0) {
// On the boundary, include ranges ending at location
result.addAll(ranges.get(index - 1).rectangles);
}
return result;
}

/* Find the index of the range containing the location. For this
* purpose only, ranges are treated as being closed on the left, open
* on the right, so that every point is in exactly one range.
*/
int getIndex(int location) {
int rangeCount = ranges.size();
if (rangeCount == 1) {
return 0;
}
return getIndex(location, 0, rangeCount - 1);
}

/* Get the index of the range containing the location, as above, but
* assuming the index is in [start,end]. Recursive binary search.
*/
private int getIndex(int location, int start, int end) {
if (start == end) {
return start;
}
int mid = (start + end + 1) >>> 1;
if (location < ranges.get(mid).start) {
return getIndex(location, start, mid - 1);
} else {
return getIndex(location, mid, end);
}
}
}

class Rectangle {
int x1;
int y1;
int x2;
int y2;

public Rectangle(int x1, int y1, int x2, int y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x1;
result = prime * result + x2;
result = prime * result + y1;
result = prime * result + y2;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Rectangle other = (Rectangle) obj;
if (x1 != other.x1)
return false;
if (x2 != other.x2)
return false;
if (y1 != other.y1)
return false;
if (y2 != other.y2)
return false;
return true;
}

public String toString() {
return "[" + x1 + "," + y1 + "][" + x2 + "," + y2 + "]";
}
}

关于java - 在矩形流中进行快速点搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29358500/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com