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.

 Posted by at 9:14 pm

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)