Class StrategyFromPaper
- java.lang.Object
-
- com.treasure.hunt.strategy.searcher.impl.strategyFromPaper.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
StrategyFromPaper.HintQuality
-
Field Summary
Fields Modifier and Type Field Description protected HalfPlaneHint
currentHint
protected LastHintBadSubroutine
lastHintBadSubroutine
protected int
phase
phase equals i in Algorithm2 (TreasureHunt1) in the paper.protected boolean
phaseGotIncrementedThisMove
protected HalfPlaneHint
previousHint
protected StrategyFromPaper.HintQuality
previousHintQuality
protected org.locationtech.jts.geom.Point
searchAreaCornerA
searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.protected org.locationtech.jts.geom.Point
searchAreaCornerB
searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.protected org.locationtech.jts.geom.Point
searchAreaCornerC
searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.protected org.locationtech.jts.geom.Point
searchAreaCornerD
searchCornerPointA, -B, -C and -D are the corners of the rectangle where the treasure is currently searched.
-
Constructor Summary
Constructors Constructor Description StrategyFromPaper()
-
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 indexprotected 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.
-
-
-
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.
-
previousHint
protected HalfPlaneHint previousHint
-
currentHint
protected HalfPlaneHint currentHint
-
previousHintQuality
protected StrategyFromPaper.HintQuality previousHintQuality
-
lastHintBadSubroutine
protected LastHintBadSubroutine lastHintBadSubroutine
-
phaseGotIncrementedThisMove
protected boolean phaseGotIncrementedThisMove
-
-
Method Detail
-
init
public void init(org.locationtech.jts.geom.Point startPosition)
- Specified by:
init
in interfaceSearcher<HalfPlaneHint>
- Parameters:
startPosition
- theSearcher
starting position, he will initialized on.
-
move
public SearchPath move()
Use this to perform a initial move, without a hint given. This is for the case, the searcher starts. (as he does normally)- Specified by:
move
in interfaceSearcher<HalfPlaneHint>
- Returns:
SearchPath
theSearchPath
the searcher did
-
move
public SearchPath move(HalfPlaneHint hint)
- Specified by:
move
in interfaceSearcher<HalfPlaneHint>
- Parameters:
hint
- the hint, theHider
gave last.- Returns:
SearchPath
theSearchPath
, this searcher chose.
-
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
-
returnHandling
protected SearchPath returnHandling(SearchPath move)
-
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
-
-