Shapes and Segments in Java

Question

I have a Shape. I'm basically trying to split an area into two areas using a segment as the bisection.

public Shape divide(Shape a, Point2D p1, Point2D p2)  {    

        Shape str = new BasicStroke().createStrokedShape(new Line2D.Double(p1,p2));    
        Shape line = new Shape(str); 
        Shape temp = a;    
        line.intersect(temp);    
        temp.exclusiveOr(line);
        // temp is the shape with the line intersecting it

        AffineTransform t = new AffineTransform(); 
        double angle = Math.atan2(p2.getY() - p1.getY(), p2.getX() - p1.getX()); 

        t.rotate(angle, p1.getX(), p1.getY());          
        temp = temp.createTransformedArea(t);       

        return Shape ;

     }

I want to bisect the shape into two using the segment, but not sure how to go about it, I was looking at the intersection methods: http://docs.oracle.com/javase/7/docs/api/java/awt/geom/Area.html but still not sure how to get two Areas from one. I'm hoping to return something like:

return  firstHalf secondHalf;

Answer 1

Here is another https://stackoverflow.com/help/mcve (I started this "yesterday" at ~3:00 am, obviously Andrew Thompson is in a different time zone ;-))

The basic idea here is as follows:

The two given points define a line. That is, an infinite line, and not only a line segment. The corner points of the bounding box of the object are projected on this line and its perpendicular. This gives (an upper bound of) the extent of the object along these lines. These upper bounds can be used to define the "minimum half-spaces" above and below the line that are required to cover the respective half of the object. These half-spaces can then be intersected with the object to obtain the desired results.

The split method in this example receives a Graphics2D parameter. This is only used for "debugging" - that is, to show the intermediate results (extents, half-spaces) that are computed, and a preview of the final results. This Graphics g parameter (and the corresponding debugging output) can simply be removed (but it might also help to show the idea of the approach).

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Shape;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class ShapeSplit
{
    public static void main(String[] args) 
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }    

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().add(new ShapeSplitPanel());
        f.setSize(1100,600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

class ShapeSplitPanel extends JPanel implements MouseMotionListener
{
    private Shape inputShape = new Ellipse2D.Double(300,200,200,300);
    private Point2D point0 = new Point2D.Double(200,300);
    private Point2D point1 = new Point2D.Double(600,400);

    ShapeSplitPanel()
    {
        addMouseMotionListener(this);
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;
        g.setColor(Color.BLUE);
        g.fill(inputShape);

        g.setColor(Color.BLACK);
        g.draw(new Line2D.Double(point0, point1));
        g.fill(new Ellipse2D.Double(
            point0.getX() - 3, point0.getY()-3, 6, 6));
        g.fill(new Ellipse2D.Double(
            point1.getX() - 3, point1.getY()-3, 6, 6));

        split(new Area(inputShape), point0, point1, g);

    }


    private static Area[] split(Area a, Point2D p0, Point2D p1, Graphics2D g)
    {
        // Compute the direction of the line (L)
        // and its perpendicular (P)
        double dx = p1.getX() - p0.getX();
        double dy = p1.getY() - p0.getY();
        double length = Math.hypot(dx, dy);
        double dirLx = dx / length;
        double dirLy = dy / length;
        double dirPx = -dirLy;
        double dirPy = dirLx;

        // Compute the minimum and maximum of all dot 
        // products that describe the distance of the
        // projection of the corner points of the 
        // bounding box on on the line (L) and its
        // perpendicular (P). These are upper limits
        // for the extents of the object along these
        // directions 
        double minDotL = Double.MAX_VALUE;
        double maxDotL = -Double.MAX_VALUE;
        double minDotP = Double.MAX_VALUE;
        double maxDotP = -Double.MAX_VALUE;
        Rectangle2D bounds = a.getBounds2D();
        for (int i=0; i<4; i++)
        {
            Point2D corner = getCorner(bounds, i);
            double pdx = corner.getX() - p0.getX();
            double pdy = corner.getY() - p0.getY();

            double dotL = dirLx * pdx + dirLy * pdy;
            minDotL = Math.min(minDotL, dotL);
            maxDotL = Math.max(maxDotL, dotL);

            double dotP = dirPx * pdx + dirPy * pdy;
            minDotP = Math.min(minDotP, dotP);
            maxDotP = Math.max(maxDotP, dotP);
        }

        // Compute the start- and end points of 
        // the line segments describing the 
        // extent of the bounds along the line
        // and the perpendicular
        Point2D extentLmin = new Point2D.Double(
            p0.getX() + minDotL * dirLx, 
            p0.getY() + minDotL * dirLy); 

        Point2D extentLmax = new Point2D.Double(
            p0.getX() + maxDotL * dirLx, 
            p0.getY() + maxDotL * dirLy); 

        Point2D extentPmin = new Point2D.Double(
            p0.getX() + minDotP * dirPx, 
            p0.getY() + minDotP * dirPy); 

        Point2D extentPmax = new Point2D.Double(
            p0.getX() + maxDotP * dirPx, 
            p0.getY() + maxDotP * dirPy);

        // Compute the two rectangles that cover
        // each half of the object based on 
        // the given line
        Path2D half0 = new Path2D.Double();
        half0.moveTo(extentLmin.getX(), extentLmin.getY());
        half0.lineTo(
            extentLmin.getX() + minDotP * dirPx, 
            extentLmin.getY() + minDotP * dirPy);
        half0.lineTo(
            extentLmax.getX() + minDotP * dirPx, 
            extentLmax.getY() + minDotP * dirPy);
        half0.lineTo(extentLmax.getX(), extentLmax.getY());
        half0.closePath();

        Path2D half1 = new Path2D.Double();
        half1.moveTo(extentLmin.getX(), extentLmin.getY());
        half1.lineTo(
            extentLmin.getX() + maxDotP * dirPx, 
            extentLmin.getY() + maxDotP * dirPy);
        half1.lineTo(
            extentLmax.getX() + maxDotP * dirPx, 
            extentLmax.getY() + maxDotP * dirPy);
        half1.lineTo(extentLmax.getX(), extentLmax.getY());
        half1.closePath();

        // Compute the resulting areas by intersecting
        // the original area with both halves
        Area a0 = new Area(a);
        a0.intersect(new Area(half0));

        Area a1 = new Area(a);
        a1.intersect(new Area(half1));

        // Debugging output
        if (g != null)
        {
            g.setColor(Color.GRAY);
            g.draw(bounds);

            g.setColor(Color.RED);
            g.draw(new Line2D.Double(extentLmin, extentLmax));

            g.setColor(Color.GREEN);
            g.draw(new Line2D.Double(extentPmin, extentPmax));

            g.setColor(Color.YELLOW.darker());
            g.draw(half0);

            g.setColor(Color.MAGENTA);
            g.draw(half1);

            g.setColor(Color.BLUE);
            g.fill(AffineTransform.getTranslateInstance(400, -20).
                createTransformedShape(a0));

            g.setColor(Color.BLUE);
            g.fill(AffineTransform.getTranslateInstance(400, +20).
                createTransformedShape(a1));
        }
        return new Area[] { a0, a1 };
    }

    private static Point2D getCorner(Rectangle2D r, int corner)
    {
        switch (corner)
        {
            case 0: return new Point2D.Double(r.getMinX(), r.getMinY());
            case 1: return new Point2D.Double(r.getMinX(), r.getMaxY());
            case 2: return new Point2D.Double(r.getMaxX(), r.getMaxY());
            case 3: return new Point2D.Double(r.getMaxX(), r.getMinY());
        }
        return null;
    }



    @Override
    public void mouseDragged(MouseEvent e)
    {
        point1.setLocation(e.getPoint());
        repaint();
    }


    @Override
    public void mouseMoved(MouseEvent e)
    {
    }
}

---

EDIT An aside: Technically, it could be easier (or even more elegant) to transform the original shape and the line so that the line matches the x-axis, then defining the half-spaces to be clipped against (which in this case could be simple Rectangle2Ds), and transforming the clipped results back into the original orientation. But I wanted to compute it "in-place", without having to create many transformed shapes.

---

EDIT2: Another snippet for the comment, to be inserted directly before the // Debugging output

AffineTransform t = new AffineTransform(); 
double angle = Math.atan2(p1.getY() - p0.getY(), p1.getX() - p0.getX()); 
t.rotate(-angle, p0.getX(), p0.getY());
a0 = a0.createTransformedArea(t);
a1 = a1.createTransformedArea(t);

---

EDIT3 The second approach, only the relevant method this time

private static Area[] split(Area a, Point2D p0, Point2D p1, Graphics2D g)
{
    // Compute the angle of the line to the x-axis
    double dx = p1.getX() - p0.getX();
    double dy = p1.getY() - p0.getY();
    double angleRadToX = Math.atan2(dy, dx); 

    // Align the area so that the line matches the x-axis
    AffineTransform at = new AffineTransform();
    at.rotate(-angleRadToX);
    at.translate(-p0.getX(), -p0.getY());
    Area aa = a.createTransformedArea(at);

    // Compute the upper and lower halves that the area
    // has to be intersected with
    Rectangle2D bounds = aa.getBounds2D();

    double half0minY = Math.min(0, bounds.getMinY());
    double half0maxY = Math.min(0, bounds.getMaxY());
    Rectangle2D half0 = new Rectangle2D.Double(
        bounds.getX(), half0minY, 
        bounds.getWidth(), half0maxY-half0minY);

    double half1minY = Math.max(0, bounds.getMinY());
    double half1maxY = Math.max(0, bounds.getMaxY());
    Rectangle2D half1 = new Rectangle2D.Double(
        bounds.getX(), half1minY, 
        bounds.getWidth(), half1maxY-half1minY);

    // Compute the resulting areas by intersecting
    // the original area with both halves, and 
    // transform them back to their initial position
    Area a0 = new Area(aa);
    a0.intersect(new Area(half0));

    Area a1 = new Area(aa);
    a1.intersect(new Area(half1));

    try
    {
        at.invert();
    }
    catch (NoninvertibleTransformException e)
    {
        // Always invertible
    }
    a0 = a0.createTransformedArea(at);
    a1 = a1.createTransformedArea(at);

    // Debugging output
    if (g != null)
    {
        g.setColor(Color.GRAY);
        g.draw(bounds);

        g.setColor(Color.RED);
        g.draw(aa);

        g.setColor(Color.YELLOW.darker());
        g.draw(half0);

        g.setColor(Color.MAGENTA);
        g.draw(half1);

        g.setColor(Color.BLUE.darker());
        g.fill(AffineTransform.getTranslateInstance(400, -20).
            createTransformedShape(a0));

        g.setColor(Color.BLUE.brighter());
        g.fill(AffineTransform.getTranslateInstance(400, +20).
            createTransformedShape(a1));
    }

    return new Area[] { a0, a1 };
}

Answer 2

I'd do it something like this. Note the code has a bug for when the point that start out to the right and lower ends up to the left of the upper left point. Left as an exercise for the user.

import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.geom.*;
import java.awt.image.BufferedImage;
import javax.swing.*;

class SplitArea {

    int s = 100;
    JPanel gui = new JPanel(new BorderLayout());
    BufferedImage[] images = new BufferedImage[4];
    Point p1 = new Point(s / 4, s / 4);
    Point p2 = new Point(s * 3 / 4, s * 3 / 4);
    Ellipse2D ellipse = new Ellipse2D.Float(
            s / 5, s / 5, s * 3 / 5, s * 3 / 5);
    Rectangle2D bg = new Rectangle2D.Float(0, 0, s, s);

    SplitArea() {
        JToolBar tb = new JToolBar();
        gui.add(tb, BorderLayout.PAGE_START);
        final JToggleButton tob = new JToggleButton("Primary Point");
        tb.add(tob);

        JPanel view = new JPanel(new GridLayout(1, 0, 4, 4));
        gui.add(view, BorderLayout.CENTER);
        for (int ii = 0; ii < images.length; ii++) {
            BufferedImage bi = new BufferedImage(
                    s, s, BufferedImage.TYPE_INT_RGB);
            images[ii] = bi;
            JLabel l = new JLabel(new ImageIcon(bi));
            if (ii == 0) {
                l.addMouseListener(new MouseAdapter() {

                    @Override
                    public void mouseClicked(MouseEvent e) {
                        if (tob.isSelected()) {
                            p1 = e.getPoint();
                        } else {
                            p2 = e.getPoint();
                        }
                        drawImages();
                    }
                });
            }
            view.add(l);
        }

        drawImages();
    }

    public final void drawImages() {
        Graphics2D g;

        // image 0
        g = images[0].createGraphics();
        g.setColor(Color.BLACK);
        g.fill(bg);

        g.setColor(Color.CYAN);
        g.fill(ellipse);
        g.setColor(Color.WHITE);
        g.draw(ellipse);

        g.setColor(Color.red);
        drawPoint(g, p1);
        drawPoint(g, p2);

        g.dispose();

        int xDiff = p1.x - p2.x;
        int yDiff = p1.y - p2.y;
        Point2D xAxis;
        Point2D xSAxis;
        if (xDiff == 0) {
            xAxis = new Point2D.Double(p1.x, 0);
            xSAxis = new Point2D.Double(p1.x, s);
        } else if (yDiff == 0) {
            xAxis = new Point2D.Double(0, p1.y);
            xSAxis = new Point2D.Double(s, p1.y);
        } else {
            System.out.println("Not vertical or horizontal!");
            // will throw a NaN if line is vertical
            double m = (double) yDiff / (double) xDiff;
            System.out.println("m: " + m);

            double b = (double) p1.y - (m * (double) p1.x);
            System.out.println("b: " + b);

            // crosses x axis at.. 
            xAxis = new Point2D.Double(0d, b);
            double pointS = (s - b) / m;
            xSAxis = new Point2D.Double(pointS, s);
        }

        // image 1
        g = images[1].createGraphics();
        g.setColor(Color.BLACK);
        g.fill(bg);

        g.setColor(Color.CYAN);
        g.fill(ellipse);
        g.setColor(Color.WHITE);
        g.draw(ellipse);

        g.setColor(Color.YELLOW);
        System.out.println(xAxis);
        System.out.println(xSAxis);
        g.drawLine(
                (int) xAxis.getX(), (int) xAxis.getY(),
                (int) xSAxis.getX(), (int) xSAxis.getY());

        g.setColor(Color.red);
        drawPoint(g, p1);
        drawPoint(g, p2);

        g.dispose();

        // image 2
        g = images[1].createGraphics();
        g.setColor(Color.BLACK);
        g.fill(bg);

        g.setColor(Color.CYAN);
        g.fill(ellipse);
        g.setColor(Color.WHITE);
        g.draw(ellipse);

        g.setColor(Color.YELLOW);
        System.out.println(xAxis);
        System.out.println(xSAxis);
        g.drawLine(
                (int) xAxis.getX(), (int) xAxis.getY(),
                (int) xSAxis.getX(), (int) xSAxis.getY());

        g.setColor(Color.red);
        drawPoint(g, p1);
        drawPoint(g, p2);

        g.dispose();

        // split the regions
        Rectangle2D.Double all = new Rectangle2D.Double(0, 0, s, s);
        Area a1 = new Area(all);
        Area a2 = new Area(all);
        GeneralPath aPart = new GeneralPath();
        aPart.moveTo(0, 0);
        aPart.lineTo(0, s);
        aPart.lineTo(xSAxis.getX(), xSAxis.getY());
        aPart.lineTo(xAxis.getX(), xAxis.getY());
        aPart.closePath();
        a1.subtract(new Area(aPart));
        a2.subtract(a1);

        Area ellipsePartA = new Area(ellipse);
        ellipsePartA.subtract(a1);
        Area ellipsePartB = new Area(ellipse);
        ellipsePartB.subtract(a2);

        // image 3
        g = images[2].createGraphics();
        g.setColor(Color.BLACK);
        g.fill(bg);

        g.setColor(Color.CYAN);
        g.fill(ellipsePartA);
        g.setColor(Color.WHITE);
        g.draw(ellipsePartA);

        g.setColor(Color.red);
        drawPoint(g, p1);
        drawPoint(g, p2);

        g.dispose();

        // image 4
        g = images[3].createGraphics();
        g.setColor(Color.BLACK);
        g.fill(bg);

        g.setColor(Color.CYAN);
        g.fill(ellipsePartB);
        g.setColor(Color.WHITE);
        g.draw(ellipsePartB);

        g.setColor(Color.red);
        drawPoint(g, p1);
        drawPoint(g, p2);

        g.dispose();

        gui.repaint();
    }

    public final void drawPoint(Graphics g, Point2D p) {
        g.setColor(new Color(255, 0, 0, 128));
        int x = (int) p.getX();
        int y = (int) p.getY();
        g.drawLine(x - 1, y, x - 5, y);
        g.drawLine(x + 1, y, x + 5, y);
        g.drawLine(x, y - 1, x, y - 5);
        g.drawLine(x, y + 1, x, y + 5);
    }

    public Area[] split(Area a, Point2D p1, Point2D p2) {

        Shape str = new BasicStroke().createStrokedShape(new Line2D.Double(p1, p2));
        Area line = new Area(str);
        Area temp = a;
        line.intersect(temp);
        temp.exclusiveOr(line);
        // temp is the shape with the line intersecting it          

        Area[] areas = {new Area(temp)};

        return areas;
    }

    public JComponent getGui() {
        return gui;
    }

    public static void main(String[] args) {
        Runnable r = new Runnable() {

            @Override
            public void run() {
                SplitArea sa = new SplitArea();
                JOptionPane.showMessageDialog(null, sa.getGui());
            }
        };
        // Swing GUIs should be created and updated on the EDT
        // http://docs.oracle.com/javase/tutorial/uiswing/concurrency
        SwingUtilities.invokeLater(r);
    }
}

Answer 3

Interesting question.

There are no methods that help you with this directly, but by calculating the bounding rectangle and intersecting with two opposing rectangles from your dividing line, you should be able to create such a method.

The general idea is to

1. Find the bounding rectangle of your original area: either getBounds() or getBounds2D().
2. Calculate two rectangles from your line that overlaps your area on both sides of the line. When doing this you will have to take several special cases into account (like is the line long enough, does it intersect the area at all, does the rectangles completely overlap each side of the original area, etc). The size of the rectangles should be decided by the bounding rectangle of your original area.
3. Get the two areas by intersecting each of the two rectangles with your original area, i.e. by using the intersect() method