Class StrategyFromPaper

  • All Implemented Interfaces:
    Searcher<HalfPlaneHint>
    Direct Known Subclasses:
    MinimumRectangleSearcher

    public class StrategyFromPaper
    extends java.lang.Object
    implements Searcher<HalfPlaneHint>
    This strategy implements the strategy from the paper "Deterministic Treasure Hunt in the Plane with Angular Hints" from Bouchard et al..

    Generally this strategy works in phases i=1, 2, ... in which it searchers the treasure in rectangles of the side length 2^i. The rectangles are centered in the start position of the searcher and are axis parallel. We will call the rectangle of the current phase the phase rectangle. The strategy uses a second rectangle, called the current rectangle, which equals the phase rectangle at the beginning of each phase. In some draws (most draws) the searcher can exclude a part of the current rectangle by using areas seen and the current hint gotten and lower its area. The previous rectangle is the current rectangle from the previous draw. When the current rectangle is small enough, the rectangle gets scanned which means the player walks a route in such a way that it sees all points of the current rectangle. When this happens the phase is incremented and the current rectangle is again set to the phase rectangle.

    For more information please look in the paper.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected SearchPath addState​(SearchPath move, org.locationtech.jts.geom.Coordinate[] currentRectanglePoints, org.locationtech.jts.geom.Coordinate[] phaseRectanglePoints)
      This method is used to visualize the current phases rectangle and the current search rectangle.
      protected org.locationtech.jts.geom.Coordinate[] currentPhaseRectangle()
      Returnes the rectangle of the current phase, by using the current phase index (equates to j in the paper or the phase-field in this implementation)
      void init​(org.locationtech.jts.geom.Point startPosition)
      SearchPath move()
      Use this to perform a initial move, without a hint given.
      SearchPath move​(HalfPlaneHint hint)
      protected org.locationtech.jts.geom.Coordinate[] phaseRectangle​(int phase)
      Returnes the rectangle of the current phase, by using a specified phase index
      protected boolean rectangleNotLargeEnough()  
      protected SearchPath returnHandling​(SearchPath move)  
      protected SearchPath specificRectangleScan​(org.locationtech.jts.geom.Coordinate rectangleCorner1, org.locationtech.jts.geom.Coordinate rectangleCorner2, org.locationtech.jts.geom.Coordinate rectangleCorner3, org.locationtech.jts.geom.Coordinate rectangleCorner4, SearchPath move)
      A specific rectangle scanner for this strategy, in case of StrategyFromPaper, the standard rectangleScanSpecificForStrategy from RoutinesFromPaper is used (this method is required for the MinimumRectangleStrategy which inherits from this class.)
      protected SearchPath specificRectangleScan​(org.locationtech.jts.geom.Point rectangleCorner1, org.locationtech.jts.geom.Point rectangleCorner2, org.locationtech.jts.geom.Point rectangleCorner3, org.locationtech.jts.geom.Point rectangleCorner4, SearchPath move)
      A specific rectangle scanner for this strategy, in case of StrategyFromPaper, the standard rectangleScanSpecificForStrategy from RoutinesFromPaper is used (this method is required for the MinimumRectangleStrategy which inherits from this class.)
      protected org.locationtech.jts.geom.Point[] splitRectangleHorizontally​(org.locationtech.jts.geom.Point A, org.locationtech.jts.geom.Point B, org.locationtech.jts.geom.Point C, org.locationtech.jts.geom.Point D, HalfPlaneHint hint, org.locationtech.jts.geom.LineSegment hintLine)
      If the checkIfHintGood is true and the hint is bad (i.e.
      protected org.locationtech.jts.geom.Point[] splitRectangleVertically​(org.locationtech.jts.geom.Point A, org.locationtech.jts.geom.Point B, org.locationtech.jts.geom.Point C, org.locationtech.jts.geom.Point D, HalfPlaneHint hint, org.locationtech.jts.geom.LineSegment hintLine)
      If the checkIfHintGood is true and the hint is bad (i.e.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • phase

        protected int phase
        phase equals i in Algorithm2 (TreasureHunt1) in the paper. In phase k, the algorithm checks, if the treasure is located in a rectangle with a side length of 2^k, centered at the initial position of the searcher.
      • searchAreaCornerA

        protected org.locationtech.jts.geom.Point searchAreaCornerA
        searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.
      • searchAreaCornerB

        protected org.locationtech.jts.geom.Point searchAreaCornerB
        searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.
      • searchAreaCornerC

        protected org.locationtech.jts.geom.Point searchAreaCornerC
        searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.
      • searchAreaCornerD

        protected org.locationtech.jts.geom.Point searchAreaCornerD
        searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched. This rectangle always lies in the rectangle of the current phase. The rectangle has the same function like the rectangle Ri in Algorithm2 (TreasureHunt1) in the paper. It is referred to as current search rectangle throughout the implementation.
      • phaseGotIncrementedThisMove

        protected boolean phaseGotIncrementedThisMove
    • Constructor Detail

      • StrategyFromPaper

        public StrategyFromPaper()
    • Method Detail

      • init

        public void init​(org.locationtech.jts.geom.Point startPosition)
        Specified by:
        init in interface Searcher<HalfPlaneHint>
        Parameters:
        startPosition - the Searcher starting position, he will initialized on.
      • rectangleNotLargeEnough

        protected boolean rectangleNotLargeEnough()
      • addState

        protected SearchPath addState​(SearchPath move,
                                      org.locationtech.jts.geom.Coordinate[] currentRectanglePoints,
                                      org.locationtech.jts.geom.Coordinate[] phaseRectanglePoints)
        This method is used to visualize the current phases rectangle and the current search rectangle. Adds their values to move
        Returns:
        the input with the visualisations of the current phase and the search rectangle added
      • splitRectangleHorizontally

        protected org.locationtech.jts.geom.Point[] splitRectangleHorizontally​(org.locationtech.jts.geom.Point A,
                                                                               org.locationtech.jts.geom.Point B,
                                                                               org.locationtech.jts.geom.Point C,
                                                                               org.locationtech.jts.geom.Point D,
                                                                               HalfPlaneHint hint,
                                                                               org.locationtech.jts.geom.LineSegment hintLine)
        If the checkIfHintGood is true and the hint is bad (i.e. does not divide one side of the rectangle ABCD in two parts such that both are bigger or equal to 1), null is returned. If the hint-line goes through AD and BC, the biggest axis parallel-rectangle which lies in ABCD and where the treasure could be located due to the information gained by the hint, is returned. Otherwise the return value is null.
      • specificRectangleScan

        protected SearchPath specificRectangleScan​(org.locationtech.jts.geom.Coordinate rectangleCorner1,
                                                   org.locationtech.jts.geom.Coordinate rectangleCorner2,
                                                   org.locationtech.jts.geom.Coordinate rectangleCorner3,
                                                   org.locationtech.jts.geom.Coordinate rectangleCorner4,
                                                   SearchPath move)
        A specific rectangle scanner for this strategy, in case of StrategyFromPaper, the standard rectangleScanSpecificForStrategy from RoutinesFromPaper is used (this method is required for the MinimumRectangleStrategy which inherits from this class.)
      • specificRectangleScan

        protected SearchPath specificRectangleScan​(org.locationtech.jts.geom.Point rectangleCorner1,
                                                   org.locationtech.jts.geom.Point rectangleCorner2,
                                                   org.locationtech.jts.geom.Point rectangleCorner3,
                                                   org.locationtech.jts.geom.Point rectangleCorner4,
                                                   SearchPath move)
        A specific rectangle scanner for this strategy, in case of StrategyFromPaper, the standard rectangleScanSpecificForStrategy from RoutinesFromPaper is used (this method is required for the MinimumRectangleStrategy which inherits from this class.)
      • splitRectangleVertically

        protected org.locationtech.jts.geom.Point[] splitRectangleVertically​(org.locationtech.jts.geom.Point A,
                                                                             org.locationtech.jts.geom.Point B,
                                                                             org.locationtech.jts.geom.Point C,
                                                                             org.locationtech.jts.geom.Point D,
                                                                             HalfPlaneHint hint,
                                                                             org.locationtech.jts.geom.LineSegment hintLine)
        If the checkIfHintGood is true and the hint is bad (i.e. does not divide one side of the rectangle ABCD in two parts such that both are bigger or equal to 1), null is returned. If the hint-line goes through AB and CD, the biggest axis-parallel rectangle which lies in ABCD and where the treasure could be located due to the information gained by the hint, is returned. Otherwise the return value is null.
      • currentPhaseRectangle

        protected org.locationtech.jts.geom.Coordinate[] currentPhaseRectangle()
        Returnes the rectangle of the current phase, by using the current phase index (equates to j in the paper or the phase-field in this implementation)
      • phaseRectangle

        protected org.locationtech.jts.geom.Coordinate[] phaseRectangle​(int phase)
        Returnes the rectangle of the current phase, by using a specified phase index
        Parameters:
        phase - the phase to which the phase's rectangle should be returned
        Returns:
        the points of the phase's rectangle