/*
* Copyright (c) 2005-2010 KOM – Multimedia Communications Lab
*
* This file is part of PeerfactSim.KOM.
*
* PeerfactSim.KOM is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* any later version.
*
* PeerfactSim.KOM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with PeerfactSim.KOM. If not, see .
*
*/
package de.tud.kom.p2psim.impl.topology.waypoints.strong;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Vector;
import javax.swing.JComponent;
import org.apache.commons.math3.random.JDKRandomGenerator;
import org.apache.commons.math3.random.RandomGenerator;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import de.tud.kom.p2psim.api.scenario.ConfigurationException;
import de.tud.kom.p2psim.api.topology.obstacles.Obstacle;
import de.tud.kom.p2psim.api.topology.waypoints.WaypointModel;
import de.tud.kom.p2psim.api.util.geo.maps.Node;
import de.tud.kom.p2psim.api.util.geo.maps.Way;
import de.tud.kom.p2psim.impl.simengine.Simulator;
import de.tud.kom.p2psim.impl.topology.util.PositionVector;
import de.tud.kom.p2psim.impl.topology.views.VisualizationTopologyView.VisualizationInjector;
import de.tud.kom.p2psim.impl.topology.views.VisualizationTopologyView.VisualizationInjector.DisplayString;
import de.tud.kom.p2psim.impl.topology.waypoints.StrongWaypointSupport;
import de.tud.kom.p2psim.impl.topology.waypoints.graph.StrongWaypoint;
import de.tud.kom.p2psim.impl.topology.waypoints.graph.WeakWaypoint;
import de.tud.kom.p2psim.impl.util.Tuple;
import de.tud.kom.p2psim.impl.util.geo.maps.osm.OSMMap;
import de.tud.kom.p2psim.impl.util.geo.maps.osm.OSMNode;
import de.tud.kom.p2psim.impl.util.geo.maps.osm.OSMObstacle;
import de.tudarmstadt.maki.simonstrator.api.Monitor;
import de.tudarmstadt.maki.simonstrator.api.Monitor.Level;
public class OSMHotspotStrategy extends StrongWaypointStrategy {
protected ArrayList hotspotMoveLerpPositions = new ArrayList();
private static String AMENITIES_FILENAME = "data/maps/valid_amenities.ordering";
private RandomGenerator rnd;
protected int placementRetries = 1000;
// The number of strong waypoints that shall be added to the map
protected int noOfWaypoints = 1000;
// Holds the actually existing amenities in the map (given that they are
// valid)
ArrayList existingAmenities;
private WaypointModel model = null;
/**
* A list of the most used amenities in open street map sorted by the
* likelihood of being hotspots where many people meet.
*/
private static ArrayList validAmenities = new ArrayList();
public OSMHotspotStrategy() {
// The fresh random generator based on the configured seed
// ensures that the amount of waypoints and their positioning is
// reproducible
rnd = new JDKRandomGenerator();
rnd.setSeed(Simulator.getSeed());
validAmenities = readAmenitiesFromFile();
}
/**
* Reads the valid amenities from the file AMENETIES_FILENAME and returns
* them as a list of strings.
*
* @return
*/
private ArrayList readAmenitiesFromFile() {
File ordering = new File(AMENITIES_FILENAME);
if (!ordering.exists())
throw new ConfigurationException(
"Unable to read the amenities file (" + AMENITIES_FILENAME
+ ")");
ArrayList amenities = new ArrayList();
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(ordering));
String line = reader.readLine();
while (line != null) {
if (!line.equals("")) {
amenities.add(line);
}
line = reader.readLine();
}
reader.close();
} catch (FileNotFoundException e) {
throw new ConfigurationException(
"Unable to read the amenities file (" + AMENITIES_FILENAME
+ ")", e);
} catch (IOException e) {
throw new ConfigurationException(
"Unable to read the amenities file (" + AMENITIES_FILENAME
+ ")", e);
} finally {
try {
reader.close();
} catch (Exception e) {
// ...
}
}
return amenities;
}
@Override
public void generateStrongWaypoints(WaypointModel wpModel) {
this.model = wpModel;
if (!(wpModel instanceof StrongWaypointSupport))
throw new ConfigurationException(
"OSMHotspotStrategy requires a waypoint model with strong waypoint support to work correctly.");
if (!(model.getMap() instanceof OSMMap))
throw new ConfigurationException(
"OSMHotspotStrategy requires a OSMMap to work correctly.");
OSMMap map = (OSMMap) model.getMap();
StrongWaypointSupport sws = (StrongWaypointSupport) wpModel;
noOfWaypoints = sws.getNoOfWaypoints();
// Find hotspots based on the validAmenities list
final List hotspots = findHotspots(map);
// Filter the existing valid amenities
existingAmenities = existingAmenity(hotspots);
// Assign radii based on the priority of the amenities
assignRadii(hotspots, map);
// Move the hotspots if they are inside of an obstacle
if (obstacleModel != null) {
moveWaypointsBasedOnObstacles(hotspots);
}
// Add the number of specified way points distributed by the radius size
addStrongWaypoints(hotspots);
// Inject the JComponent for displaying the hotspots
VisualizationInjector.injectComponent("Hotspots", 0, new ShowHotspots(
hotspots, model), false);
VisualizationInjector.addDisplayString(new DisplayString() {
@Override
public String getDisplayString() {
int distinctAmenities = 0;
if (existingAmenities != null)
distinctAmenities = existingAmenities.size();
return "OSM[Waypoints (strong/weak): "
+ model.getNumberOfWaypoints(StrongWaypoint.class)
+ "/" + model.getNumberOfWaypoints(WeakWaypoint.class)
+ ", Hotspots: " + hotspots.size()
+ ", Distinct amenities: " + distinctAmenities
+ ", Highest amenity: " + hotspots.get(0).amenity + "]";
}
});
}
/**
* Uses the information provided by the obstacle model to move the hotspots
* outside of the obstacles should the be completely covered.
*/
private void moveWaypointsBasedOnObstacles(List hotspots) {
for (Hotspot hotspot : hotspots) {
createHotspotGeometry(hotspot);
Obstacle obstacle = isHotspotInsideObstacle(hotspot);
if (obstacle == null)
continue;
hotspot.wasHidden = true;
Tuple closestEdges = findClosestEdgest(
hotspot, obstacle);
double t = rnd.nextDouble();
PositionVector a = closestEdges.getA();
PositionVector b = closestEdges.getB();
PositionVector newPosition = a.clone();
PositionVector p = b.minus(newPosition);
p.multiplyScalar(t);
newPosition.add(p);
PositionVector direction = a.clone();
p = b.minus(direction);
p.multiplyScalar(0.5);
direction.add(p);
direction = direction.minus(hotspot.position);
direction.normalize();
direction.multiplyScalar(hotspot.radius / 2);
newPosition.add(direction);
HotspotDeplacmentInfo lerpPos = new HotspotDeplacmentInfo(
closestEdges.getA(), closestEdges.getB(), newPosition,
hotspot.position);
hotspotMoveLerpPositions.add(lerpPos);
hotspot.position = newPosition;
}
}
private Tuple findClosestEdgest(
Hotspot hotspot, Obstacle obstacle) {
Geometry geometry = obstacle.getGeometry();
Coordinate[] coordinates = geometry.getCoordinates();
PositionVector[] positionCache = new PositionVector[coordinates.length];
double closestDistance = -1;
int closestIdx = -1;
for (int i = 0; i < coordinates.length; i++) {
positionCache[i] = new PositionVector(coordinates[i].x,
coordinates[i].y);
double d = positionCache[i].distanceTo(hotspot.position);
if (closestDistance > d || closestDistance == -1) {
closestDistance = d;
closestIdx = i;
}
}
PositionVector before = positionCache[closestIdx - 1 == -1 ? coordinates.length - 1
: closestIdx - 1];
PositionVector after = positionCache[closestIdx + 1 == coordinates.length ? 0
: closestIdx + 1];
if (before.distanceTo(hotspot.position) < after
.distanceTo(hotspot.position)) {
return new Tuple(
positionCache[closestIdx].clone(), before);
} else {
return new Tuple(
positionCache[closestIdx].clone(), after);
}
}
private Obstacle isHotspotInsideObstacle(Hotspot hotspot) {
for (Obstacle obstacle : obstacleModel.getObstacles()) {
if (obstacle.contains(hotspot.geometry)) {
return obstacle;
}
}
return null;
}
/**
* Uses the validAmenities list to find hotspots in the map and returns a
* list newly created Hotspots.
*
* @param map
* @return
*/
private List findHotspots(OSMMap map) {
List hotspots = new ArrayList();
Collection nodes = map.getNodes();
Collection ways = map.getWays();
List obstacles = map.getObstacles();
// Node and Way are currently the only retained
// information and also the most used
// TODO: Add a MovementStrategy that doesn't use waypoints but avoids
// obstacles
// TODO: Add a MovementStrategy that uses the waypoints but doesn't move
// in a straight line
// TODO: Add an option to assign StrongWaypoints based on the density of
// WeakWaypoints or convert some WeakWaypoints to StrongWaypoints
for (Obstacle o : obstacles) {
OSMObstacle obstacle = (OSMObstacle) o;
if (obstacle.containsAttribute("amenity")) {
if (getAmenityIndex(obstacle.getAttribute("amenity"),
validAmenities) < 0)
continue;
Hotspot hotspot = new Hotspot();
hotspot.position = obstacle.getVertices().get(0);
hotspot.amenity = obstacle.getAttribute("amenity");
hotspot.type = obstacle.getAttribute("name");
hotspots.add(hotspot);
}
}
/*
* for (Node n : nodes) { OSMNode node = (OSMNode)n; if
* (node.containsAttribute("amenity")) { if
* (getAmenityIndex(node.getAttribute("amenity"), validAmenities) < 0)
* continue;
*
* Hotspot hotspot = new Hotspot(); hotspot.position =
* node.getWorldPosition(); hotspot.amenity =
* node.getAttribute("amenity"); hotspot.type = "node";
*
* hotspots.add(hotspot); } }
*
* for (Way w : ways) { OSMWay way = (OSMWay)w; if
* (way.containsAttribute("amenity")) { if
* (getAmenityIndex(way.getAttribute("amenity"), validAmenities) < 0)
* continue;
*
* PositionVector center = getCenter(way.getNodes());
*
* Hotspot hotspot = new Hotspot(); hotspot.position = center;
* hotspot.amenity = way.getAttribute("amenity"); hotspot.type = "way";
*
* hotspots.add(hotspot); } }
*/
Collections.sort(hotspots, new HotspotComparator(validAmenities));
return hotspots;
}
/**
* Filters the existing amenities based on the validAmenities list
*
* @param hotspots
* Hotspots with amenities
* @return List of existing valid amenities
*/
public ArrayList existingAmenity(List hotspots) {
ArrayList list = new ArrayList();
for (String vh : validAmenities) {
for (Hotspot h : hotspots) {
if (h.amenity.equals(vh)) {
list.add(vh);
break;
}
}
}
return list;
}
/**
* Returns the center of a list of nodes
*
* @param points
* @return
*/
private PositionVector getCenter(Vector points) {
PositionVector centroid = new PositionVector(0, 0);
for (Node n : points) {
centroid.add(n.getWorldPosition());
}
centroid.multiplyScalar(1 / (double) points.size());
return centroid;
}
/**
* Calculates the maximum radius size based on the map size and assigns the
* radii based on the hotspots amenities priority.
*
* The hotspot with the highest priority e.g. the first hotspot in the list
* receives the maximum radius.
*
* Note: This method also creates the Geometry object for the hotspot
*
* @param hotspots
* Hotspots whos radius shall be calculated
* @param map
* The current map
*/
private void assignRadii(List hotspots, OSMMap map) {
PositionVector dimensions = map.getDimensions();
double llsqrt = Math.sqrt(dimensions.getX() + dimensions.getY());
double defaultRadius = 0.630 * llsqrt; // 0.887
int idx;
for (Hotspot h : hotspots) {
idx = getAmenityIndex(h.amenity, existingAmenities);
h.radius = (defaultRadius / (idx + 1));
h.geometry = createHotspotGeometry(h);
}
}
private Geometry createHotspotGeometry(Hotspot h) {
int points = 20;
double slice = 2 * Math.PI / points;
ArrayList coordinates = new ArrayList();
for (int i = 0; i < points; i++) {
double angle = slice * i;
int newX = (int) (h.position.getX() + h.radius * Math.cos(angle));
int newY = (int) (h.position.getY() + h.radius * Math.sin(angle));
coordinates.add(new Coordinate(newX, newY));
}
coordinates.add(coordinates.get(0));
Coordinate[] coordinateArray = new Coordinate[coordinates.size()];
GeometryFactory gf = new GeometryFactory();
return gf.createLinearRing(coordinates.toArray(coordinateArray));
}
/**
* Adds strong way points to the graph that are used for the navigation of
* AbstractWaypointMovementModel implementations.
*
* FIXME: Find a way to place all waypoints (currently only used x retries)
* FIXME: Remove hotspots that are fully contained in an obstacle!!
*
* @param hotspots
* Hotspots to whom the new way points shall be added
*/
private void addStrongWaypoints(List hotspots) {
double radiiSum = 0.0;
for (Hotspot h : hotspots) {
radiiSum += h.radius;
}
double wps = noOfWaypoints / radiiSum;
int wpCount = 0;
addHotspots: {
for (Hotspot h : hotspots) {
int nrWps = (int) (Math.round(wps * h.radius));
int retries = 0;
for (int i = 0; i < nrWps; i++) {
PositionVector loc = selectRandomLocation(h);
if (obstacleModel != null) {
if (!obstacleModel.contains(loc)) {
model.addWaypoint(new StrongWaypoint