检测点何时将离开矩形区域的算法

本文介绍了检测点何时将离开矩形区域的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

假设我们有一个矩形或正方形，并且知道其角(4个角)的x，y坐标.

Assume that we have a rectangle or a square and we know the x,y coordinates of its corners (4 corners).

还假定我们在该正方形内有一个点，该点我们知道其坐标(x，y)，其速度(km/h)，其航向(航向以方向度为单位，北为0，南为180等等)，并且该时间点具有这些属性(以秒为单位的时间).

Also assume that we have a point inside that square for which we know its coordinates (x,y), its speed (km/h), its heading (heading is measured in directional degrees, 0 for north, 180 for south and so on) and the time point it has these attributes (epoch time in seconds).

我们如何计算该点将离开矩形的时间点(以秒为单位的时间)以及出口的坐标(x，y)?

How can we calculate the time point (epoch time in seconds) in which the point will exit the rectangle as well as the coordinates (x,y) of the exit ?

推荐答案

您需要先找到相交的边.建立沿两个坐标移动的方程式，并计算相交的第一次时间.

You need to find what edge is intersected first. Make equations for moving along both coordinates and calculate the first time of intersection.

请注意，对于地理坐标，您可能需要更复杂的计算，因为纬度/经度坐标定义的矩形"实际上是地球表面上弯曲的梯形.请参阅此页面获取旅行时间.

Note that for geographic coordinates you might need more complex calculations because "rectangle" defined by Lat/Lon coordinates is really curvy trapezoid on the Earth surface. Look at "Intersection of two paths given start points and bearings" chapter on this page to get travel time.

vx = V * Cos(heading + Pi/2) //for y-axis north=0 vy = V * Sin(heading + Pi/2) x = x0 + vx * t y = y0 + vy * t //potential border positions if vx > 0 then ex = x2 else ex = x1 if vy > 0 then ey = y2 else ey = y1 //check for horizontal/vertical directions if vx = 0 then return cx = x0, cy = ey, ct = (ey - y0) / vy if vy = 0 then return cx = ex, cy = y0, ct = (ex - x0) / vx //in general case find times of intersections with horizontal and vertical edge line tx = (ex - x0) / vx ty = (ey - y0) / vy //and get intersection for smaller parameter value if tx <= ty then return cx = ex, cy = y0 + tx * vy, ct = tx else return cx = x0 + ty * vx, cy = ey, ct = ty