atavism.server.pathing
Class PathSynth

java.lang.Object
  atavism.server.pathing.PathSynth

public class PathSynth
extends java.lang.Object

This class contains machinery to synthesize a list of "CV" polygons and their arcs starting with a boundary polygon and a collection of obstacles in or overlapping with that boundary.

Nested Class Summary

static class	PathSynth.HullLine A line in a convex hull - - just a pair of HullPoints
static class	PathSynth.HullPoint A class that represents points around a convex hull.

Field Summary

static float	epsilon If a distance squared between a pair of AOVector points is less than epsilon, they are considered the same point.
protected static float	insideDistance
protected static Logger	log

Constructor Summary

PathSynth(PathPolygon boundary, java.util.List<PathPolygon> obstacles)

Method Summary

protected void	addCornersInRange(java.util.List<AOVector> newCorners, java.util.List<AOVector> oldCorners, int firstOldCorner, int lastOldCorner, int incr) Add the corners from the first to the last corner numbers to the newCorners list, wrapping if first is greater than last.
protected PathPolygon	breakBoundaryAroundObstacle(PathPolygon boundaryPoly, PathPolygon obstacle) Break a boundary polygon into two pieces around a convex obstacle which it wholly contains, changing the corner set of the original boundary polygon, and returning a new polygon.
protected void	combineBoundaryAndObstacles_old(PathPolygon boundaryPoly, java.util.List<PathPolygon> obstacles) Merge the boundary polygon with those obstacles whose sides intersect the sides of the boundary, and for obstacles that are wholly contained in the boundary, add them one-by-one, splitting the containing boundary polygons into two polygons for each one, so that the boundary polygons do not contain holes.
protected void	combineBoundaryAndObstacles(PathPolygon boundaryPoly, java.util.List<PathPolygon> obstacles) If there is more than one obstacle, start by computing the convex hull of all the obstacles, yielding a single obstacle.
java.util.List<PathSynth.HullLine>	computeConvexHull(java.util.List<PathPolygon> obstacles) N**3 algorithm to compute the convex hull of a set of polygons.
protected static java.lang.Float	computeSlope(AOVector point1, AOVector point2) Compute the slope of a pair of points, or return null if the slope would be infinite.
protected void	dumpPolygonsAndArcs(java.lang.String description)
protected void	generateConvexPolygons(PathPolygon poly) Updates the list of polygons, each of which is convex, and portals between the polygons required make the input polygon convex.
protected static PathSynth.HullPoint	hullVertex(PathSynth.HullPoint[] points, AOVector p) Returns the HullLine containing the point if the point is a vertex of the hull
static void	main(java.lang.String[] args) Calls a set of test cases for the generation of polygons and arcs from a boundary and obstacle.
protected void	mergeDoublyIntersectingObstacle(PathPolygon boundary, PathPolygon obstacle, java.util.List<PolyIntersection> intersections) Handle the case of an obstacle which intersects the line segments of the boundary in exactly two places.
protected static boolean	onLeft(AOVector point1, AOVector point2, java.lang.Float slope, AOVector p) Given a point, determine if that point is lying on the left side or right side of the first point of the line.
protected java.util.List<AOVector>	pointsInside(PathPolygon boundary, PathPolygon obstacle) Return true if all vertices of the obstacle are contained in the boundary; false otherwise.
protected static PathSynth.HullPoint[]	sortHullPoints(java.util.List<PathSynth.HullLine> lines) Produces an array of sorted HullPoint objects such that the points are in order around the perimeter of the hull.
protected java.util.List<PathPolygon>	spliceOutIntersections(PathPolygon boundary, java.util.List<PathPolygon> obstacles) For obstacles whose sides intersect the sides of the boundary, change the boundary by adding appropriate vertices.
protected boolean	whollyContained(PathPolygon boundary, PathPolygon obstacle) Returns true if the boundary contains every vertex of the obstacle; false otherwise.
static int	wrap(int index, int size)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

epsilon

public static final float epsilon

If a distance squared between a pair of AOVector points is less than epsilon, they are considered the same point.

See Also:

Constant Field Values

insideDistance

protected static float insideDistance

log

protected static final Logger log

Constructor Detail

PathSynth

public PathSynth(PathPolygon boundary,
                 java.util.List<PathPolygon> obstacles)

Method Detail

combineBoundaryAndObstacles

protected void combineBoundaryAndObstacles(PathPolygon boundaryPoly,
                                           java.util.List<PathPolygon> obstacles)

If there is more than one obstacle, start by computing the convex hull of all the obstacles, yielding a single obstacle. Then compute the collection of boundary polygons that surround that convex hull.

Now we must deal with the parts that are inside the hull but not inside any obstacle. For each line in the hull, if both points in the line come from the same obstacle, then that line forms a side of the hull. But if the two points belong to different obstacles, then the line is a side of a polygon must be added to the set of boundary polygons.

Start with an obstacle vertex in a direction that takes it inside of the hull. That vertex will be the first point in an "interior" polygon to be added to the boundary. Add that vertex, and each successive point until you again reach the boundary of the hull. Take the direction that is away from the side of the polygon contained in the hull, encountering a point in a different obstacle. Keep repeating the process until you arrive again at the original point, having created the interior boundary polygon. This polygon is most likely not convex, and may contain obstacles, but should no intersect any obstacles.

Two outstanding problems:

First, in the case of an obstacle that intersects the hull at only one point, how do we represent the hole? The code below will add all the obstacle points, which causes the single hull point to be represented twice, which no doubt messes up the code that tries to break convex polygons.

Second, the new boundary will in general contain obstacles. We can form a convex hull around those obstacles, but in general the hull will not lie completely inside of the boundary. The cure here is to prune the hull by based on intersections with the boundary. But we're adding a god-awful amount of machinery.

combineBoundaryAndObstacles_old

protected void combineBoundaryAndObstacles_old(PathPolygon boundaryPoly,
                                               java.util.List<PathPolygon> obstacles)

Merge the boundary polygon with those obstacles whose sides intersect the sides of the boundary, and for obstacles that are wholly contained in the boundary, add them one-by-one, splitting the containing boundary polygons into two polygons for each one, so that the boundary polygons do not contain holes. Finally, convert the concave boundary polygons into convex ones by splitting them up.

breakBoundaryAroundObstacle

protected PathPolygon breakBoundaryAroundObstacle(PathPolygon boundaryPoly,
                                                  PathPolygon obstacle)

Break a boundary polygon into two pieces around a convex obstacle which it wholly contains, changing the corner set of the original boundary polygon, and returning a new polygon.

addCornersInRange

protected void addCornersInRange(java.util.List<AOVector> newCorners,
                                 java.util.List<AOVector> oldCorners,
                                 int firstOldCorner,
                                 int lastOldCorner,
                                 int incr)

Add the corners from the first to the last corner numbers to the newCorners list, wrapping if first is greater than last.

wrap

public static int wrap(int index,
                       int size)

computeSlope

protected static java.lang.Float computeSlope(AOVector point1,
                                              AOVector point2)

Compute the slope of a pair of points, or return null if the slope would be infinite.

onLeft

protected static boolean onLeft(AOVector point1,
                                AOVector point2,
                                java.lang.Float slope,
                                AOVector p)

Given a point, determine if that point is lying on the left side or right side of the first point of the line.

hullVertex

protected static PathSynth.HullPoint hullVertex(PathSynth.HullPoint[] points,
                                                AOVector p)

Returns the HullLine containing the point if the point is a vertex of the hull

sortHullPoints

protected static PathSynth.HullPoint[] sortHullPoints(java.util.List<PathSynth.HullLine> lines)

Produces an array of sorted HullPoint objects such that the points are in order around the perimeter of the hull.

computeConvexHull

public java.util.List<PathSynth.HullLine> computeConvexHull(java.util.List<PathPolygon> obstacles)

N**3 algorithm to compute the convex hull of a set of polygons. We can always implement the nlogn algorithm if we notice the time.

spliceOutIntersections

protected java.util.List<PathPolygon> spliceOutIntersections(PathPolygon boundary,
                                                             java.util.List<PathPolygon> obstacles)

For obstacles whose sides intersect the sides of the boundary, change the boundary by adding appropriate vertices. Return those obstacles wholly contained in the boundary,

whollyContained

protected boolean whollyContained(PathPolygon boundary,
                                  PathPolygon obstacle)

Returns true if the boundary contains every vertex of the obstacle; false otherwise.

mergeDoublyIntersectingObstacle

protected void mergeDoublyIntersectingObstacle(PathPolygon boundary,
                                               PathPolygon obstacle,
                                               java.util.List<PolyIntersection> intersections)

Handle the case of an obstacle which intersects the line segments of the boundary in exactly two places.

pointsInside

protected java.util.List<AOVector> pointsInside(PathPolygon boundary,
                                                PathPolygon obstacle)

Return true if all vertices of the obstacle are contained in the boundary; false otherwise.

generateConvexPolygons

protected void generateConvexPolygons(PathPolygon poly)

Updates the list of polygons, each of which is convex, and portals between the polygons required make the input polygon convex. If the input polygon is already convex, then it returns a list containing that single polygon, and no portals.

dumpPolygonsAndArcs

protected void dumpPolygonsAndArcs(java.lang.String description)

main

public static void main(java.lang.String[] args)

Calls a set of test cases for the generation of polygons and arcs from a boundary and obstacle.