MySQL的3D“颜色填充”实施

我有一个MySQL表结构如下：MySQL的3D“颜色填充”实施

CREATE TABLE IF NOT EXISTS `np_voxels` (
    `world` VARCHAR(16) NOT NULL, 
    `x` INT NOT NULL, 
    `y` INT NOT NULL, 
    `z` INT NOT NULL, 
    `value` DOUBLE NOT NULL DEFAULT 0, 
    `property_id` INT NULL, 
    PRIMARY KEY (`world`, `x`, `y`, `z`) , 
    INDEX `np_fk_voxels_properties_idx` (`property_id` ASC) , 
    CONSTRAINT `np_fk_voxels_properties` 
    FOREIGN KEY (`property_id`) 
    REFERENCES `np_properties` (`property_id`) 
    ON DELETE NO ACTION 
    ON UPDATE NO ACTION) 
ENGINE = InnoDB;

我想两个选择查询，可以找到一个给定的起始体素符合特定条件的所有连接的体素。一个WHERE world = @world AND value > @minvalue AND property_id IS NULL，另一个WHERE world = @world AND property_id = @property_id。所使用的洪水填充算法应该足够快到不会引起明显延迟的地方（这将在游戏服务器上使用）。还应该有一个以起始体素为中心的边界框，表示查询不能退出。在y轴上，这将从0到@ymax。默认值为31。对于x和z轴，这应该从起始x或z延伸出@hdistance。

输入

@world
@startx
@starty
@startz
@minvalue或@property_id（取决于什么程序所期待的。）
@hdistance默认：13
@ymax默认：31

我搜索谷歌，并没有发现在MySQL现有的实现。我不明白如何快速和更复杂的洪水填充算法努力尝试写我自己的。

来源

2015-09-27 Ruby

快速填充不应该在SQL中实现。您可以将所有需要的数据加载到适当的结构（可能是一些图形表示或3D数组，取决于数据密度），然后运行堆栈/队列或任何其他可以使用编程语言编写的实现。按照定义递归填充（即使通常通过循环实现），SQL不适用于递归，也不适用于循环。 – jkavalik

@jkavalik好点。我原本以为如果mysql做了这样的处理会更快。你可以重新发布这个答案，以便我可以将其标记为已接受吗？ – Ruby

快速填充不应该在SQL中实现。您可以将所有需要的数据加载到适当的结构（可能是一些图形表示或3D数组，取决于数据密度），然后运行堆栈/队列或任何其他可以使用编程语言编写的实现。按照定义递归填充（即使通常通过循环实现），SQL不适用于递归，也不适用于循环。

但有些东西可能会在mysql中使用，即使它不是一个普通的SQL解决方案。有一个特殊的引擎来处理图形 - OQGRAPH。它在MariaDB中可用，可能可以安装到MySQL。

它支持组合图的有效存储，其中网格只是一种特殊情况，它可以计算最短路径和可达性。从示例页面，它知道dijkstras和breadth_first - 后者应该可用作洪水填充实现。

根据您的需要，您应该可以编写更高性能的东西，因为您可以根据自己的需要定制它。但是如果你想试验和比较更多的实现，你可以尝试一下。

来源

2015-10-03 05:26:30 jkavalik

MySQL的3D“颜色填充”实施

回答

相关问题