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

问题描述

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

我可能必须针对大量点运行此计算（例如50-200分）。

解决方案

1. 计算最接近的点是与多边形的每条边相切的。


2. 计算每个线段（多边形的边）上的最近点到所讨论的点。计算每条线段上距离最近点的距离。


3. 查找最小距离。
   

该算法的每一步都是线性时间（O（n））。 / p>

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

计算最近点与多边形的每条边相切。

• 让多边形边的一个端点为 p1 = {x1，y1} 。
  
• 设多边形边的另一个端点为 p2 = {x2， y2} 。


• 让您分析的多边形中的点为 p3 = {x3，y3}


• 设p1和p2之间距离的百分比，这是找到线上形成的点所需的百分比通过p1和p2，使得 p1 + u（p2-p1） =最接近p3的线上的点（此点和p3之间的线段也会发生垂直于通过p1和p2的线）。
  
• u =（（x 3-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}


• 对每个多边形边重复这些计算（即替换为新的p1和p2）
  
  
  

  计算每个线段（多边形的边）上的最近点到点
  

  点 pu 只是线段上最接近的点< 0 <= u <= 1 。否则，线段的适当端点是最接近该点的点。因此，对于在上述步骤中计算的每个 pu，p1，p2和u 执行以下操作：
  
  

  
  
  • 令pc = {xc，yc} 被表示为多边形边线段上的最接近的点到所讨论的点。
  
  
  • IF u <0 THEN pc = p1
  
  
  • 否则如果u> 1 THEN pc = p2
  
  
  • ELSE pc = pu
  
  
  >
  
  

  计算每条线段上距离最近点到所讨论点的距离。
  
  

  
  
  • 距离 p3 和 pc =`sqrt（（x3 - xc）^ 2 +（y3 - yc）^ 2）
  
  
  • 为所有电脑重复计算
    strong>找到最小距离。相应的距离最短的多边形是答案。
    
    
    
    
    
    • 遍历所有距离，直到找到最小距离。相应的多边形边是答案。
    
    
    
    
    

    以下图表可帮助您理解本文中的要点和术语：

    
    
    
    
    
    

    ....

    
    

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

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

    解决方案

    1. Calculate closest point on the line that is tangent to each edge of the polygon.
    2. Calculate closest point on each line segment (edge of the polygon) to the point in question.
    3. Calculate the distance from the closest point on each line segment to the point in question.
    4. Find the minimum distance. The corresponding polygonedge with the minimum distance is the answer.

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

    Here are the basic formulas for each of the steps:

    Calculate closest point on the line that is tangent to each edge of the polygon.

    • 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)

    Calculate closest point on each line segment (edge of the polygon) to the point in question.

    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:

    • 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

    Calculate the distance from the closest point on each line segment to the point in question.

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

    Find the minimum distance. The corresponding polygonedge with the minimum distance is the answer.

    • Iterate through all of the distances until you find the smallest one. The corresponding polygon edge is the answer.

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

    ....

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