对于长度以矩形的最小和一组点的搜索。什么是算法?

问题描述 投票:0回答:2

美好的一天。

我发现在二维空间中的点的集合为其中的距离,以矩形的总和最小的任务。例如,对于两个矩形,其结果将是下一个区域(picture)。在这方面的任何点具有长度A和B的矩形的最小总和。这算法适用于找到一个区域,该区域的具有长度的最小和所有点?矩形的数目可以是不同的,它们是随机定位的。他们甚至可以相互重叠。矩形的边平行于坐标轴,并且不能转动。该区域必须是矩形或线或点。

c++ algorithm computational-geometry
2个回答
1
投票

暗示:

(映射任何点(x,y)提供到最近距离与矩形函数)的矩形的距离图由四个倾斜面(倾斜45°),四个四分之一锥和矩形本身,这是在地面电平,形成一个连续的表面。

为了获得全局距离图,它“足够”来概括个人矩形的距离地图。一个相当复杂的表面将产生。根据不同的几何形状,最低可能会在一个顶点,整个边缘或全脸来实现。

全球地图的建设似乎比一个line arrangement比较困难,由于圆锥补丁。在一般情况下,一个非常困难的问题,虽然轴线对齐约束可能会缓解它。


1
投票

添加在伊夫的答案。

如伊夫描述的,每个矩形“分化”平面成9份和的总和加上不同的距离的方法。中间部分(矩形)添加距离0,侧部添加坐标到侧距离,角部点距离添加到该角落。这种做法计划必须分为9 ^ n个部分,并且距离总和是通过将适当的矩形距离函数来计算。这是可行的,如果矩形的数量不会太大。

也许这并不需要计算所有部分,因为它很容易计算的最小值部分的一些约束,检查是不是需要在所有计算的一部分。

我不知道,但在我看来,全球距离图是凸函数。如果比它可以通过迭代类似的想法作为线性规划解决的情况下。

© www.soinside.com 2019 - 2024. All rights reserved.