A Study on Voronoi Diagrams with Obstacles in the Architectural and Urban Space

建筑与城市空间中含障碍物的Voronoi图研究

• 批准号: 18560592
• 负责人: FUJII Akira
• 金额: $ 1.44万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18560592/
• 关键词: Voronoi diagram; Delaunay network; shortest-path distance; spatial tessellation; automated external defibrillator; facility location; 都市計画・建築計画; 計算機科学; 地域分析; 計算幾何学

This research consists of two parts, the first part is the methodology of the Voronoi diagrams with obstacles, and the second one is the application of the method to the actual architectural and urban space, which shows the efficiency and benefit by this method.In the first part, we propose a method for constructing Voronoi diagrams with two-dimensional obstacles by a simple and practical computer algorithm, using the shortest-path distance of a Delaunay network of many random vertices, which we termed as rDn. By measuring the shortest-path distance of the rDn for the detour distance, this method provides an approximate solution for the Voronoi diagrams with obstacles. We verify the isotropy and stability of the ratio of the shortest-path distance of the rDn and the Euclid distance by a computer experiment. We then show the reliability of the approximate solution by comparing with the exact solution in a simple case, and the effectiveness of this method by solving a sample problem with free shaped obstacles.The second part describes the construction and application of Voronoi diagrams with obstacles. By applying the model, we analyzed the domain of Automated External Defibrillators (AED) around Ueno Park in Tokyo, Japan, and indicated a more efficient AED location by including the necessary time for the rescuer and his or her helper both of whom happened to be near the victim of Sudden Cardiac Arrest (SCA), to get an AED avoiding various obstacles: pond, building, planting, fence, in the park. After indicating the current location of AEDs, we proposed a new location plan with additional AEDs placed in public facilities in the park with no AED that will improve the average shortest-path distance from 343m to 119m, which is equivalent to almost 18% improvement in survival rate.

本研究由两部分组成，第一部分是带有障碍物的Voronoi图的方法论，第二部分是该方法在实际建筑和城市空间中的应用，这表明了该方法的效率和效益。第一部分，我们提出了一种利用Delaunay最短路径距离，通过简单实用的计算机算法构建带有二维障碍物的Voronoi图的方法。 许多随机顶点的网络，我们称之为 rDn。该方法通过测量绕行距离的rDn的最短路径距离，为有障碍物的Voronoi图提供近似解。我们通过计算机实验验证了rDn最短路径距离与欧几里得距离之比的各向同性和稳定性。然后我们通过简单情况下与精确解的比较来展示近似解的可靠性，并通过解决具有自由形状障碍物的示例问题来展示该方法的有效性。第二部分描述了具有障碍物的Voronoi图的构造和应用。通过应用该模型，我们分析了日本东京上野公园周围自动体外除颤器（AED）的范围，并指出了更有效的 AED 位置，包括救援者及其助手（两人恰好在心脏骤停（SCA）受害者附近）避开公园内的各种障碍物（池塘、建筑物、植物、栅栏）获得 AED 所需的时间。在指出目前AED的位置后，我们提出了新的位置规划，在公园内没有AED的公共设施中额外放置AED，将平均最短路径距离从343m提高到119m，相当于生存率提高了近18%。

项目成果

障害物の配置された平面におけるボロノイ図に関する研究-ドローネ網における最短距離を用いた作図法の提案-

有障碍平面上的 Voronoi 图研究 - 一种使用 Delaunay 网络中最短距离的构造方法的提出 -

• 发表时间: 2007
• 期刊: 都市計画論文集 42
• 作者: 高見沢実;高見沢実;高見沢実;今井公太郎・藤井明
• 通讯作者: 今井公太郎・藤井明

A study on Voronoi diagrams with two-dimensional obstacles- An approximate construction using the shortest-path distance of a Delaunay network

二维障碍物 Voronoi 图的研究 - 使用 Delaunay 网络最短路径距离的近似构造

• 发表时间: 2007
• 期刊: Journal of the City Planning Institute of Japan No.42
• 作者: Imai;K. and Fujii;A.
• 通讯作者: A.

障害物の配置された平面におけるボロノイ図に関する研究

有障碍物平面上的 Voronoi 图研究

• 发表时间: 2007
• 作者: Imai;K. and Fujii;A.;今井公太郎・藤井明
• 通讯作者: 今井公太郎・藤井明