对于不规则多边形中的一个点，选择最接近该点的边的最有效方法是什么? [英] For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point?

问题描述

给定一个不规则多边形和该多边形内的一个点，我如何确定多边形中的哪条边最接近该点?

Given an irregular polygon and a point within that polygon, how do I determine which edge in the polygon is closest to the point?

我可能需要对多边形内的大量点(例如 50-200 个点)运行此计算.

I will likely have to run this calculation for a large set of points within the polygon (e.g. 50-200 points).

推荐答案

1. 计算与多边形每条边相切的直线上的最近点.
2. 计算每条线段(多边形的边缘)上离相关点最近的点.
3. 计算每条线段上最近点到相关点的距离.
4. 求最小距离.距离最短的对应多边形边就是答案.

这个算法的每一步都是线性时间(O(n)).

Each step of this algorithm is linear time (O(n)).

以下是每个步骤的基本公式:

Here are the basic formulas for each of the steps:

计算与多边形每条边相切的直线上的最近点.

• 令多边形的边的一个端点为p1 = {x1, y1}.
• 令多边形的边的另一端点为p2 = {x2, y2}.
• 让您正在分析的多边形中的点为 p3 = {x3,y3}.
• 令 u 为 p1 和 p2 之间距离的百分比，这是在 p1 和 p2 形成的直线上找到点所需的距离，使得 p1+u(p2-p1) = 直线上最接近 p3 的点(此点与 p3 之间的线段也恰好垂直于通过 p1 和 p2 的线).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1))/((x2 - x1)^2 + (y2 - y1)^2)
• 设p1和p2组成的直线上离p3最近的点为pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• 就像我们之前说的 pu = {xu, yu}
• 对每个多边形边缘重复这些计算(即替换为新的 p1s 和 p2s)

• Let the one endpoint of an edge of a polygon be p1 = {x1, y1}.
• Let the other endpoint of an edge of a polygon be p2 = {x2, y2}.
• Let the point in the polygon you are analyzing be p3 = {x3,y3}.
• Let u be the percentage of the distance between p1 and p2, that is needed to find the point on the line formed by p1 and p2, such that p1+u(p2-p1) = the point on the line that is closest to p3 (the line segment between this point and p3 also happens to be perpendicular to the line going through p1 and p2).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2)
• Let the point closest to p3 on the line formed by p1 and p2 be known as pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• And like we said before pu = {xu, yu}
• Repeat these calculations for every polygon edge (i.e. substitute in new p1s and p2s)

计算每条线段(多边形的边缘)上离相关点最近的点.

pu点只是0 <= u <= 1时线段上最近的点.否则，线段的适当端点是离相关点最近的点.因此，对于上述步骤中计算的每个 pu、p1、p2 和 u，请执行以下操作:

The point pu is only the closest point on the line segment when 0 <= u <= 1. Otherwise the appropriate endpoint of the line segment is the closest point to the point in question. Thus for each pu, p1, p2, and u calculated in the above step do the following:

• 设 pc = {xc, yc} 表示为多边形边的线段上离相关点最近的点.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

• Let pc = {xc, yc} be denoted as the closest point on the line segment of the polygon edge to the point in question.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

计算每条线段上最近点到相关点的距离.

• p3 和 pc 之间的距离 = `sqrt((x3 - xc)^2 + (y3 - yc)^2)
• 对所有电脑重复此计算

• Distance between p3 and pc = `sqrt((x3 - xc)^2 + (y3 - yc)^2)
• Repeat this calculation for all pc's

求最小距离.距离最短的对应多边形边就是答案.

• 遍历所有距离，直到找到最小的距离.对应的多边形边就是答案.

这是一个图表，可帮助您理解本文中的要点和术语所代表的含义:

Here is a diagram to help you understand what the points and terminology in this post represent:

....

这篇关于对于不规则多边形中的一个点，选择最接近该点的边的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！