blocks|key|149922|text|也许Frechet的距离就是你想要的？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|149923|计算两条多边形曲线之间的Fréchet距离|offset|length|149924|计算简单多边形之间的Fréchet距离|149925|entityMap|0|LINK|mutability|MUTABLE|url|http://web.archive.org/web/20120805031535/http://www.cim.mcgill.ca/~stephane/cs507/Project.html|1|http://eurocg.org/06/delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/25.pdf^0|0|0|L|0|0|0|J|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

Maybe the Frechet Distance is what your looking for?

<a href="http://web.archive.org/web/20120805031535/http://www.cim.mcgill.ca/~stephane/cs507/Project.html" rel="nofollow noreferrer">Computing the Fréchet distance between two polygonal curves</a> 
<a href="http://eurocg.org/06/delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/25.pdf" rel="nofollow noreferrer">Computing the Fréchet Distance Between Simple Polygons</a>

blocks|key|1149092|text|天真的方法是找出红色和50个蓝色物体之间的距离--所以你要看50个3d毕达哥拉斯计算%2B排序来找到答案。不过，这只会有效地找到中心点之间的距离。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1149093|如果你想要任意多边形，也许你最好是一个射线跟踪解决方案，从红色多边形表面发射射线相对于正常，并报告何时另一个多边形被击中。|1149094|混合算法可能有效--我们可以找到距离中心点的距离，假设我们对蓝色多边形的相对大小有一些概念，我们可以将结果集中到其中最接近的位置，然后使用光线跟踪缩小真正最接近的多边形。|1149095|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

The naive approach is to find the distance between the red and 50 blue objects -- so you're looking at 50 3d Pythagorean calculations + sorting to find the answer. That would only really work for finding the distance between center points though.

If you want arbitrary polygons, maybe your best best is a raytracing solution that emits rays from the surface of the red polygon with respect to the normal, and reports when another polygon is hit. 

A hybrid might work -- we could find the distance from the center points, assuming we had some notion of the relative size of the blue polygons, we could cull the result set to the closest among those, then use raytracing to narrow down the truly closest polygon(s).

blocks|key|149963|text|对于具有合理数目的边界点的多边形形状，例如在GIS或游戏应用程序中，可能更容易进行一系列测试。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|149964|对于红色多边形中的每个顶点，计算出与蓝色多边形中每个顶点的距离，并找到最近的(提示，比较距离%5E2，这样就不需要sqrt()查找最近的顶点)，然后检查找到的红色和蓝色顶点的两边的顶点，以决定哪些线段是最近的，然后在两个线段之间找到最近的方法。|149965|请参阅http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/+(对于2d的情况来说很容易)|offset|length|149966|entityMap|0|LINK|mutability|MUTABLE|url|http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/^0|0|0|3|1M|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

For polygon shapes with a reasonable number of boundary points such as in a GIS or games application it might be quicker easier to do a series of tests.

For each vertex in the red polygon compute the distance to each vertex in the blue polygons and find the closest (hint, compare distance^2 so you don't need the sqrt() )
Find the closest, then check the vertex on each side of the found red and blue vertex to decide which line segments are closest and then find the closest approach between two line segments.

See <a href="http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/" rel="nofollow noreferrer">http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/</a> (it's easy to simply for the 2d case)

blocks|key|150026|text|我怀疑是否有更好的解决方案，比计算红色的距离和每一个蓝色的距离和排序的长度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|150027|关于排序，通常情况下，QuickSort在性能上很难超越(优化后的性能将在小于7项的情况下切断递归，并切换到类似于InsertionSort+(可能是ShellSort)的内容)。|150028|因此，我想问题是如何快速计算两个多边形之间的距离，毕竟，你需要做这个计算50次。|150029|以下方法也适用于3D，但可能不是最快的方法：|150030|二维空间中的最小多边形距离|offset|length|150031|问题是，你愿意用精确来换取速度吗？例如，您可以将所有多边形打包到包围框中，其中盒的两侧与坐标系轴线平行。3D游戏经常使用这种方法。为此，您需要找到每个坐标(x、y、z)的最大值和最小值，以构造虚拟边界框。然后，计算这些包围盒的距离是一项非常琐碎的任务。|150032|下面是一个更高级的包围框的示例图像，它们与坐标系轴不平行：|150033|定向包围盒-+OBB|150034|然而，这使得距离计算变得不那么简单。它用于碰撞检测，因为不需要知道距离，您只需要知道一个边界框的一个边缘是否位于另一个边界框内。|150035|下面的图像显示了一个轴对齐包围框：|150036|轴对齐包围盒AABB|150037|OOB更精确，AABB更快。也许你会喜欢读这篇文章：|150038|先进的碰撞检测技术|150039|这总是假设，你愿意用精确来换取速度。如果精度比速度更重要，你可能需要一种更先进的技术。|150040|entityMap|0|LINK|mutability|MUTABLE|url|http://cgm.cs.mcgill.ca/~orm/mind2p.html|1|http://xna-uk.net/photos/screen_shots/images/1291/original.aspx|2|http://www.gamasutra.com/features/20000330/bobic_05.gif|3|http://www.gamasutra.com/features/20000330/bobic_pfv.htm^0|0|0|0|0|0|D|0|0|0|0|0|A|1|0|0|0|0|A|2|0|0|0|9|3|0|0^^$0|@$1|2|3|4|5|6|7|1H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1J|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|1K|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1L|8|@]|9|@$J|1M|K|1N|1|1O]]|A|$]]|$1|L|3|M|5|6|7|1P|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1R|8|@]|9|@$J|1S|K|1T|1|1U]]|A|$]]|$1|R|3|S|5|6|7|1V|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1W|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1X|8|@]|9|@$J|1Y|K|1Z|1|20]]|A|$]]|$1|X|3|Y|5|6|7|21|8|@]|9|@]|A|$]]|$1|Z|3|10|5|6|7|22|8|@]|9|@$J|23|K|24|1|25]]|A|$]]|$1|11|3|12|5|6|7|26|8|@]|9|@]|A|$]]|$1|13|3|-4|5|6|7|27|8|@]|9|@]|A|$]]]|14|$15|$5|16|17|18|A|$19|1A]]|1B|$5|16|17|18|A|$19|1C]]|1D|$5|16|17|18|A|$19|1E]]|1F|$5|16|17|18|A|$19|1G]]]]

I doubt there is better solution than calculating the distance between the red one and every blue one and sorting these by length.

Regarding sorting, usually QuickSort is hard to beat in performance (an optimized one, that cuts off recursion if size goes below 7 items and switches to something like InsertionSort, maybe ShellSort).

Thus I guess the question is how to quickly calculate the distance between two polygons, after all you need to make this computation 50 times.

The following approach will work for 3D as well, but is probably not the fastest one:

<a href="http://cgm.cs.mcgill.ca/~orm/mind2p.html" rel="noreferrer">Minimum Polygon Distance in 2D Space</a>

The question is, are you willing to trade accuracy for speed? E.g. you can pack all polygons into bounding boxes, where the sides of the boxes are parallel to the coordinate system axes. 3D games use this approach pretty often. Therefor you need to find the maximum and minimum values for every coordinate (x, y, z) to construct the virtual bounding box. Calculating the distances of these bounding boxes is then a pretty trivial task.

Here's an example image of more advanced bounding boxes, that are not parallel to the coordinate system axes:

<a href="http://xna-uk.net/photos/screen_shots/images/1291/original.aspx" rel="noreferrer">Oriented Bounding Boxes - OBB</a>

However, this makes the distance calculation less trivial. It is used for collision detection, as you don't need to know the distance for that, you only need to know if one edge of one bounding box lies within another bounding box.

The following image shows an axes aligned bounding box:

<a href="http://www.gamasutra.com/features/20000330/bobic_05.gif" rel="noreferrer">Axes Aligned Bounding Box - AABB</a>

OOBs are more accurate, AABBs are faster. Maybe you'd like to read this article:

<a href="http://www.gamasutra.com/features/20000330/bobic_pfv.htm" rel="noreferrer">Advanced Collision Detection Techniques</a>

This is always assuming, that you are willing to trade precision for speed. If precision is more important than speed, you may need a more advanced technique.

blocks|key|150052|text|您可能会减少问题，然后对一个小集合进行密集的搜索。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|150053|首先处理每个多边形，方法是：|150054|多边形中心|unordered-list-item|150055|多边形的最大半径(即在离所定义的中心最远的多边形的边缘/表面/顶点上的点)|150056|现在你可以收集，比如说，5-10个最接近红色的多边形(找到距离中心到中心，减去半径，排序列表，取前5)，然后做一个更详尽的例程。|150057|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|P|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|Q|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|L|$]]

You might be able to reduce the problem, and then do an intensive search on a small set.

Process each polygon first by finding:

<ul>
<li>Center of polygon</li>
<li>Maximum radius of polygon (i.e., point on edge/surface/vertex of the polygon furthest from the defined center)</li>
</ul>

Now you can collect, say, the 5-10 closest polygons to the red one (find the distance center to center, subtract the radius, sort the list and take the top 5) and then do a much more exhaustive routine.

blocks|key|837530|text|您可以从比较边框之间的距离开始。测试矩形之间的距离比测试多边形之间的距离容易，而且您可以立即消除任何超过nearest_rect+%2B+its_diagonal的多边形(可能您可以进一步细化)。然后，您可以测试剩余的多边形，以找到最近的多边形。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|837531|有一些算法可以找到多边形附近-我相信维基百科对它们有一个很好的评论。如果我没记错的话，那些只允许凸多边形的，要快得多。|837532|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

You could start by comparing the distance between the bounding boxes. Testing the distance between rectangles is easier than testing the distance between polygons, and you can immediately eliminate any polygons that are more than nearest_rect + its_diagonal away (possibly you can refine that even more). Then, you can test the remaining polygons to find the closest polygon.

There are algorithms for finding polygon proximity - I'm sure Wikipedia has a good review of them. If I recall correctly, those that only allow convex polygons are substantially faster.

blocks|key|841601|text|我知道你说的是“最短的距离”，但你真的是说最优的解决方案还是“好的/非常好的”解决方案对你的问题是好的？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|841602|因为如果需要找到最优的解决方案，就必须计算出所有源和目的地的政治界限(不仅仅是顶点)之间的距离。如果你在3D空间，那么每一个边界都是一个平面。这可能是一个大问题(O(n%5E2))，这取决于您有多少个顶点。|841603|因此，如果你有顶点计数，使得正方形成一个斯卡斯特数，而一个“好/非常好”的解对你来说是很好的，那就去做一个启发式的解或近似。|841604|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

I know you said "the shortest distance" but you really meant the optimal solution or a "good/very good" solution is fine for your problem?

Because if you need to find the optimal solution, you have to calculate the distance between all of your source and destination poligon bounds (not only vertexes). If you are in 3D space then each bound is a plane. That can be a big problem (O(n^2)) depending on how many vertexes you have.

So if you have vertex count that makes that squares to a scarry number AND a "good/very good" solution is fine for you, go for a heuristic solution or approximation.

blocks|key|150105|text|这种筛选技术的目的是减少平均情况下需要执行的距离计算的次数，而不影响结果的准确性。它工作在凸多边形和凹多边形上。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|150106|找到每个顶点之间的最小距离，这样一个顶点是红色顶点，另一个是蓝色顶点。称它为r。多边形之间的距离最多是r。从红色多边形构造一个新的区域，其中每个线段由r向外移动，并以半径r的弧线连接到它的邻居，并以顶点为中心。查找从该区域内的每个顶点到与此区域相交的相反颜色的每个线段的距离。|150107|当然，您可以添加一个近似方法，例如包围框，以快速确定哪些蓝色多边形不可能与红色区域相交。|150108|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

This screening technique is intended to reduce the number of distance computations you need to perform in the average case, without compromising the accuracy of the result. It works on convex and concave polygons.

Find the the minimum distance between each pair of vertexes such that one is a red vertex and one is a blue. Call it r. The distance between the polygons is at most r. Construct a new region from the red polygon where each line segment is moved outward by r and is joined to its neighbors by an arc of radius r is centered at the vertex. Find the distance from each vertex inside this region to every line segment of the opposite color that intersects this region.

Of course you could add an approximate method such as bounding boxes to quickly determine which of the blue polygons can't possibly intersect with the red region.

blocks|key|1149236|text|你可能想看看沃罗内的淘汰。这里的纸和视频：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1149237|http://www.cs.unc.edu/~geom/DVD/|offset|length|1149238|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|W|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

You might want to look at Voronoi Culling. Paper and video here:

<a href="http://www.cs.unc.edu/~geom/DVD/" rel="nofollow noreferrer">http://www.cs.unc.edu/~geom/DVD/</a>

blocks|key|150155|text|正如其他人提到的，使用边界区域(框、圆圈)可能允许您放弃一些多边形-多边形交互作用。这方面有几种策略。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|150156|选择任何蓝色多边形并找到距离红色多边形的距离。现在选择任何其他多边形。如果边界区域之间的最小距离大于已经找到的距离，则可以忽略此多边形。对所有多边形继续。|ordered-list-item|150157|找到红色多边形和所有蓝色多边形之间的最小距离/质心距离。对距离进行排序，首先考虑最小的距离。计算实际的最小距离，并继续通过排序列表，直到多边形之间的最大距离大于到目前为止找到的最小距离。|150158|您选择的圆圈/轴向对齐框或定向框可能会对算法的性能产生很大影响，这取决于输入多边形的实际布局。|150159|对于实际的最小距离计算，可以使用Yang等人的“基于Voronoi图的两个不相交凸多边形距离的快速计算算法”，即O(log+%2B+log+)。|offset|length|150160|entityMap|0|LINK|mutability|MUTABLE|url|http://www.zju.edu.cn/jzus/2006/A0609/A060909.pdf^0|0|0|0|0|O|T|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|W|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|X|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|Y|8|@]|9|@$K|Z|L|10|1|11]]|A|$]]|$1|M|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T]]]]

As others have mentioned using bounding areas (boxes, circles) may allow you to discard some polygon-polygon interactions. There are several strategies for this, e.g.

<ol>
<li>Pick any blue polygon and find the distance from the red one. Now pick any other polygon. If the minimum distance between the bounding areas is greater than the already found distance you can ignore this polygon. Continue for all polygons.</li>
<li>Find the minimum distance/centroid distance between the red polygon and all the blue polygons. Sort the distances and consider the smallest distance first. Calculate the actual minimum distance and continue through the sorted list until the maximum distance between the polygons is greater than the minimum distance found so far.</li>
</ol>

Your choice of circles/axially aligned boxes, or oriented boxes can have a great affect on performance of the algorithm, dependent on the actual layout of the input polygons.

For the actual minimum distance calculation you could use Yang et al's '<a href="http://www.zju.edu.cn/jzus/2006/A0609/A060909.pdf" rel="nofollow noreferrer">A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram</a>' which is O(log n + log m).

blocks|key|1149299|text|马上就要去参加葬礼了，但是如果你把你的多边形分解成凸子，你可以做一些优化。你可以在每个多边形上进行二进制搜索，找出最近的顶点，然后我相信最接近的点应该是那个顶点，或者一个相邻的边缘。这意味着您应该能够在log(log+m+*+n)中这样做，其中m是多边形上的平均顶点数，n是polies的数目。这有点像哈斯蒂，所以可能是错的。如果需要的话稍后会给出更多细节。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1149300|entityMap^0|2T|E|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

Gotta run off to a funeral in a sec, but if you break your polygons down into convex subpolies, there are some optimizations you can do. You can do a binary searches on each poly to find the closest vertex, and then I believe the closest point should either be that vertex, or an adjacent edge. This means you should be able to do it in <code>log(log m * n)</code> where m is the average number of vertices on a poly, and n is the number of polies. This is kind of hastey, so it could be wrong. Will give more details later if wanted.

blocks|key|150223|text|我相信你正在寻找的是A*算法，它用于路径查找。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|150224|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I believe what you are looking for is the A* algorithm, its used in pathfinding.

I have 1 red polygon say and 50 randomly placed blue polygons - they are situated in geographical 2D space. What is the quickest/speediest algorithim to find the the shortest distance between a red polygon and its nearest blue polygon?

Bear in mind that it is not a simple case of taking the points that make up the vertices of the polygon as values to test for distance as they may not necessarily be the closest points.

So in the end - the answer should give back the closest blue polygon to the singular red one.

This is harder than it sounds!

What is the quickest way to find the shortest cartesian distance between two polygons

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有1红色多边形和50随机放置的蓝色多边形-他们位于地理2D空间。寻找红色多边形与其最近的蓝色多边形之间最短距离的最快/最快算法是什么？请记住，这不是一个简单的情况，即把构成多边形顶点的点作为值来测试距离，因为它们不一定是最近的点。因此，在最后-答案应该返回最近的蓝色多边形的单数红色。这比听起来难多了！

问找出两个多边形之间最短的笛卡儿距离的最快方法是什么？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找出两个多边形之间最短的笛卡儿距离的最快方法是什么？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找出两个多边形之间最短的笛卡儿距离的最快方法是什么？
EN