Java2D – Remove Non-Visible Lines
The following code adjusts a list of Line2D objects so that the lines stay within the viewable area. For example, if the viewable area is 100×100 and the line goes from point 50,50 to 200,50, the line will be adjusted so that its points are 50,50 to 100,50. This is useful when doing a perspective transformation because lines that are drawn too far outside of the viewable area gives unwanted results when the transformation is applied to them.
/**
* @param linesToDraw lines that are meant to be drawn
* @param width width of the rendering area
* @param height height of the rendering area
* @return a list of lines which have been adjusted to be within the rendering area.
*/
public List<Line2D> removeNonVisibleLines(List<Line2D> linesToDraw, int width,
int height) {
Iterator<Line2D> it;
Line2D line2d;
List<Line2D> oldLines = new ArrayList<Line2D>(linesToDraw.size());
List<Line2D> newLines = new ArrayList<Line2D>();
oldLines.addAll(linesToDraw);
// adjust lines to be their minimum size
it = oldLines.iterator();
while (it.hasNext()) {
line2d = it.next();
line2d = limitToVisibleArea(line2d, width, height);
if (line2d == null) {
it.remove();
} else {
newLines.add(line2d);
}
}
return newLines;
}
/**
* @param line2d the original line which may or may not be within the viewable area
* @param width the width of the viewable area
* @param height the height of the viewable area
* @return the original line, adjusted to only be within the viewiable area, or null
* if the line is completely outside of the viewable area.
*/
protected Line2D limitToVisibleArea(Line2D line2d, int width, int height) {
// there are basically 4 cases: 1) neither point is within the visible area and the line does not
// pass through the visible area.
// 2) neither point is in the visible area and the line does pass through the visible area.
// 3) both points are within the visible area.
// 4) one points is within the visible area and the other is not.
// The equation works in this way:
// 1) Assume the line is infinite and find the two points where the line passes through the
// edges of the visible area.
// 2) All four points are added to a list.
// 3) Remove points from the list which are outside of the visible area.
// If there are 0 points left then the line does not pass through the visible area.
// If there are 2 points left then use those two as the line.
// If there are 3 points left then one of the original points was within the visible area and
// we must remove the point which doesn't belong - this is the point whose distance to the line
// is > 0.
Point2D p1 = line2d.getP1();
Point2D p2 = line2d.getP2();
Set<Point2D> newPoints = new HashSet<Point2D>(4);
Point2D point2d = new Point2D.Double(-1, -1);
double intersections[] = new double[4];
Iterator<Point2D> it;
Line2D newLine2d = null;
double maxDifference = .00000000001; // points this close are the same point
// if the two points are equal then the "line" is just a point
if (p1.distance(p2) == 0) {
if (pointIsWithinVisibleArea(p1, width, height)) {
return line2d;
} else {
return null;
}
}
// add the original points to the list of points. one or more of them may be the points
// used in the final line returned.
newPoints.add(line2d.getP1());
newPoints.add(line2d.getP2());
// line equation is y = mx + b
// line equation is y = (slope) * x + b
double yDiff = p1.getY() - p2.getY() + 0;
double xDiff = p1.getX() - p2.getX();
double slope = yDiff / xDiff;
// p1.getY() = slope * p1.getX() + b
// b = p1.getY() - (slope * p1.getX())
double b = p1.getY() - (slope * p1.getX());
// now we have the slope and b, so we can solve for x given any y, and for y given any x
if (xDiff != 0) {
// y = slope * 0 + b;
intersections[0] = b; // intersects with the left most line at x = 0
intersections[1] = slope * width + b; // intersects with the right most line at x = width
// x = (y - b) / m
intersections[2] = (0 - b) / slope; // intersects with the upper most line at y = 0
intersections[3] = (height - b) / slope; // intersects with the lower most line at y = height
} else {
// this is a vertical line. x is always the same.
intersections[0] = Double.POSITIVE_INFINITY;
intersections[1] = Double.POSITIVE_INFINITY;
intersections[2] = p1.getX();
intersections[3] = p1.getX();
}
// intersections[] now stores where our two points intersect with each of the sides of the
// viewable area (i.e. the line intersects at 0 for x, width for x, 0 for y, and height for y).
// if the intersection point at x = 0 is within the viewable area then save the point
if ((intersections[0] >= 0) && (intersections[0] <= height)) {
newPoints.add(new Point2D.Double(0, intersections[0]));
}
// if the intersection point at x = width is within the viewable area then save the point
if ((intersections[1] >= 0) && (intersections[1] <= height)) {
newPoints.add(new Point2D.Double(width, intersections[1]));
}
// if the intersection point at y = 0 is within the viewable area then save the point
if ((intersections[2] >= 0) && (intersections[2] <= width)) {
newPoints.add(new Point2D.Double(intersections[2], 0));
}
// if the intersection point at y = height is within the viewable area then save the point
if ((intersections[3] >= 0) && (intersections[3] <= width)) {
newPoints.add(new Point2D.Double(intersections[3], height));
}
// remove the points which are not within the visible area
it = newPoints.iterator();
while (it.hasNext()) {
point2d = it.next();
if (!pointIsWithinVisibleArea(point2d, width, height)) {
// this point is not in the visible area. get rid of it.
it.remove();
}
}
// remove points with a distance to the line greater than 0. this covers the situations
// where the line does not pass through the visible area and when one point on the line
// is already within the visible area.
it = newPoints.iterator();
while (it.hasNext()) {
point2d = it.next();
if (this.getDistance(point2d, line2d) > maxDifference) {
it.remove();
}
}
// if there are 3 points then two of them are likely actually the same, but slightly
// different enough to not be seen as the same. i.e. 188.999999999999 and 189.0. so try
// to correct the issue.
if (newPoints.size() == 3) {
it = newPoints.iterator();
point2d = it.next(); // get the three points.
p1 = it.next();
p2 = it.next();
if (p1.distance(p2) < maxDifference) {
p2 = null; // only keep p1
} else if (p1.distance(point2d) < maxDifference) {
point2d = null; // only keep p1
} else if (p2.distance(point2d) < maxDifference) {
point2d = null; // only keep p2
}
// we now have only two points.
newPoints.clear();
newPoints.add(p1);
if (p2 != null) {
newPoints.add(p2);
}
if (point2d != null) {
newPoints.add(point2d);
}
}
if ((newPoints.size() == 1) &&
((diff(p1.getX(), 0) < maxDifference) || (diff(p1.getX(), width) < maxDifference) ||
(diff(p1.getY(), 0) < maxDifference) || (diff(p1.getY(), height) < maxDifference) ||
(diff(p2.getX(), 0) < maxDifference) || (diff(p2.getX(), width) < maxDifference) ||
(diff(p2.getY(), 0) < maxDifference) || (diff(p2.getY(), height) < maxDifference)
)) {
// the line ends on the border of the image. we'll include the point just in case.
it = newPoints.iterator();
p1 = it.next();
newLine2d = new Line2D.Double(p1, p1);
} else if ((newPoints.size() != 0) && (newPoints.size() != 2)) {
throw new RuntimeException("Wrong # of points from algorithm.");
} else if (newPoints.size() == 2) {
// these are the two points to use. yay
newLine2d = new Line2D.Double(newPoints.toArray(new Point2D[]{})[0], newPoints.toArray(new Point2D[]{})[1]);
}
return newLine2d;
}
This is not the most efficient way to accomplish this, but it seems to work.