1. 定义

驻留点：驻留点（Stay Point）是车辆在行驶过程中的停留信息，是由一系列连续的GPS点组成(特殊的轨迹段)，GPS在空间上非常接近，但是时间跨度很大。通俗地讲，如果一个车辆在一个小的空间范围内持续出现了很长时间，则认为车辆在该范围内驻留了。
驻留点检测：从一条轨迹中检测出所有的驻留点所在的位置称为驻留点检测。

图1 轨迹驻留点示意图[1]

图1表示了一条轨迹中的驻留点信息，从开始，后续的点、、与的空间距离都比较小，且到的时间跨度很大时，{}便被认为是一个驻留点。驻留点包含了丰富的时空语义信息，例如：驻留点比较多的地方可能是一个商场(图1B))、公园(图1C))等。

2. 算法描述

从定义中可以得到驻留点的两个特征：空间范围小，时间跨度大。驻留点检测算法的关键就在如何定义这个小和大。

我们称驻留点的起始GPS点称为锚点(Anchor)，下面从空间和时间两个维度对驻留点检测算法进行阐述。

2.1 空间范围检测：

在空间上，从锚点开始，找到锚点之后连续的n个与锚点距离小于最大驻留距离(Maximum Stay Distance)的GPS点。用公式表示为：，其中 ，并且
满足。

如图2所示，当取5，并以作为锚点anchor进行驻留点检测时，,,都小于5，而大于5。则本次空间范围检测中找到了3个与锚点距离小于的GPS点{}。

图2 驻留点检测示意图

2.2 时间跨度检测：

对于锚点anchor和其后检测到的n个连续的距离小于的GPS点，如果，则认为车辆驻留的时间足够大，可以将anchor及其后面的连续n个GPS点识别成一个驻留点（共n+1个GPS），其中是用户设置的最小驻留时间（Minimum Stay Time）。

在图2中，如果，则{}构成了一个驻留点，否则，不认为这是一个驻留点。因为虽然这4个GPS点的空间距离很小，但是时间跨度也很小，有可能是车辆在缓慢移动（比如在等待红绿灯）。

3. 算法分类

上文中描述了给定一个锚点anchor，根据空间范围和时间跨度检测驻留点的方法。如果检测到一个驻留点，那么下一个锚点anchor应该怎么选呢，这就引出了两种驻留点检测算法的划分。

3.1 基础的驻留点检测[文献1]

如果当前锚点anchor及其后面的n个GPS点组成一个驻留点，则下一次检查的锚点取；否则下一次检测的锚点为，即当前锚点的下一个GPS点。

这种检测方法得到的驻留点可能存在驻留点相邻的情况，比如检测到 = {}和 = {}这两个相邻的驻留点。

3.2 基于密度合并的驻留点检测[文献2]

无论当前锚点anchor是否检测到驻留点，下一次检测锚点都取anchor的下一个GPS点。

这种检测方法首先检测出所有的驻留点，比如 = {}， = {}和 = {}这3个驻留点；然后将相互重叠的驻留点合并成一个最终的驻留点，比如将进行合并，最终得到驻留点={}和。

4. 代码实现

完整的Scala代码请查看我的GitHub。

4.1 驻留点检测父类

代码实现的主要逻辑是利用calStayPointBounds抽象方法计算出驻留点在轨迹GPS点序列中的位置，然后在detect方法中将这些GPS点摘取出来，组成驻留点（StayPoint）。

abstract class AbstractStayPointDetector {
  def detect(trajectory: Trajectory): Array[StayPoint] = {
    val gpsCoordinates = trajectory.getCoordinatesGPS
    val stayPointBounds = calStayPointBounds(gpsCoordinates)

    for ((startIndex, endIndex) <- stayPointBounds) yield {
      val stayPointCoordinates = gpsCoordinates.slice(startIndex, endIndex + 1)
      new StayPoint(stayPointCoordinates.toList.asJava, trajectory.oid)
    }
  }

  /**
   * Find all the stay points' bound in trajectory's coordinates
   *
   * @param gpsCoordinates trajectory's gps coordinates containing longitude latitude and time
   * @return bound of each stay point, consisting of start index and end index(include)
   */
   def calStayPointBounds(gpsCoordinates: Array[CoordinateGPS]): Array[(Int, Int)]

  /**
   * Calculate the position of gps coordinate whose distance
   * to anchor firstly exceeds the max stay point distance threshold
   *
   * @param gpsCoordinates gps coordinates of trajectory
   * @param anchorIndex    anchor position in gpsCoordinates
   * @param maxDistInM     max stay point distance in unit meter
   * @return the position of first coordinate whose distance from anchor is further than maxDistInM
   */
  protected def getFirstExceedIndex(gpsCoordinates: Array[CoordinateGPS],
                                    anchorIndex: Int, maxDistInM: Double): Int = {

    val anchor = gpsCoordinates(anchorIndex)
    var currIndex = anchorIndex + 1
    while (currIndex < gpsCoordinates.length) {
      val distInM = DistanceCalculator.distInMeter(anchor, gpsCoordinates(currIndex))
      if (distInM > maxDistInM) {
        return currIndex
      }
      currIndex += 1
    }
    currIndex
  }

  /**
   * Judge whether start to end time interval of stay point exceeds the specific threshold
   *
   * @param startTime        time of stay point's start coordinate
   * @param endTime          time of stay point's end coordinate
   * @param minStayTimeInSec minimum stay point time interval in unit second
   * @return whether time interval from start to end coordinate exceeds the threshold
   */
  protected def isExceedMinTimeThreshold(startTime: Timestamp, endTime: Timestamp,
                                         minStayTimeInSec: Double): Boolean = {
    val timeIntervalInSec = endTime.toInstant.getEpochSecond - startTime.toInstant.getEpochSecond
    timeIntervalInSec > minStayTimeInSec
  }
}

4.2 基础的驻留点检测

实现父类中的calStayPointBounds方法，检测出的驻留点可能相邻。

class ClassicStayPointDetector(maxStayDistInMeter: Double, minStayTimeInSecond: Double) extends AbstractStayPointDetector {

  /**
   * Find all the stay points' bound in trajectory's coordinates
   *
   * @param gpsCoordinates trajectory's gps coordinates containing longitude latitude and time
   * @return bound of each stay point, consisting of start index and end index(include)
   */
  override def calStayPointBounds(gpsCoordinates: Array[CoordinateGPS]): Array[(Int, Int)] = {
    val stayPointBounds = new ArrayBuffer[(Int, Int)]()

    var currIndex = 0
    while (currIndex < gpsCoordinates.length) {
      val endIndex = super.getFirstExceedIndex(gpsCoordinates, currIndex, maxStayDistInMeter) - 1

      val anchorTime = gpsCoordinates(currIndex).time
      val endTime = gpsCoordinates(endIndex).time
      val isExceedTime = super.isExceedMinTimeThreshold(anchorTime, endTime, minStayTimeInSecond)
      if (!isExceedTime) {
        stayPointBounds += ((currIndex, endIndex))
        currIndex = endIndex + 1
      } else {
        currIndex += 1
      }
    }

    stayPointBounds.toArray
  }
}

4.3 基于密度合并的驻留点检测

实现父类的calStayPointBounds方法，检测出基于密度合并后的驻留点

class DensityStayPointDetector(maxStayDistInMeter: Double, minStayTimeInSecond: Double) extends AbstractStayPointDetector {
  /**
   * Find all the stay points' bound in trajectory's coordinates
   *
   * @param gpsCoordinates trajectory's gps coordinates containing longitude latitude and time
   * @return bound of each stay point, consisting of start index and end index(include)
   */
  override def calStayPointBounds(gpsCoordinates: Array[CoordinateGPS]): Array[(Int, Int)] = {
    val stayPointBounds = new ArrayBuffer[(Int, Int)]()

    var startIndex: Option[Int] = None
    var endIndex: Option[Int] = None
    for (currIndex <- gpsCoordinates.indices) {
      val tempEndIndex = super.getFirstExceedIndex(gpsCoordinates, currIndex, maxStayDistInMeter) - 1

      val anchorTime = gpsCoordinates(currIndex).time
      val endTime = gpsCoordinates(tempEndIndex).time
      val isExceedTime = super.isExceedMinTimeThreshold(anchorTime, endTime, minStayTimeInSecond)
      if (!isExceedTime) {
        //detected stay point
        if (startIndex.isEmpty) {
          startIndex = Some(currIndex)
        }
        if (endIndex.isEmpty || endIndex.get < tempEndIndex) {
          endIndex = Some(tempEndIndex)
        }
      }

      if (endIndex.isDefined && endIndex.get == currIndex) {
        stayPointBounds += ((startIndex.get, endIndex.get))
        startIndex = None
        endIndex = None
      }
    }

    stayPointBounds.toArray
  }
}

5. 总结

驻留点检测是指检测轨迹GPS点序列中表示车辆驻留信息的GPS子序列，轨迹的驻留信息会在很多轨迹分析挖掘算法中得到广泛应用。

参考文献

[1] Zheng Y. Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3): 1-41.
[2] Yuan J, Zheng Y, Zhang L, et al. Where to find my next passenger[C]//Proceedings of the 13th international conference on Ubiquitous computing. 2011: 109-118.