javageometrycoordinate

Determine if a shape is above another shape

I'm attempting to determine if one four sided shape is above another one, and returning the ratio of the amount that is uncovered. My definition of "uncovered" is if there is no other shape above the one being examined on the y-axis, and if there is how much they are intersecting on the x-axis.

Example:

two shapes

In the above image, the desired output should be 0.6363. Out of the 110 pixels, 70 are intersecting with the object above it, and 70/110=0.6363

Another Example:

example 2

In this example the desired output would be 0.3636.

What I have attempted so far is that I am starting with double out = 1; and then if the y-axis of shape 2 is less than shape 1, I subtract the amount the two shapes intersect on the x axis from the ratio with some variant of out-=(c.getX2()-b.getX2())/Math.abs(c.getX1()-c.getX2());

However, this doesn't seem to be working, and my attempts at correcting the code seem to just be adding more and more unnecessary complexity. I assume there is a much easier way to do what I'm trying to do, but I'm not great with geometry.

c is the current shape being examined, and b is the one it is being compared to.

if(((b.getX2() < c.getX2()) && (b.getX2()>c.getX1()))||((b.getX2()>c.getX2())&&(b.getX2()<c.getX1()))||((b.getX1()>c.getX2())&&(b.getX1()<c.getX1()))) {
    if(b.getY2() < c.getY2()) {
        if((b.getX2() < c.getX2()) && (b.getX2()>c.getX1())) {
            out-= (c.getX2()-b.getX2())/Math.abs(c.getX1()-c.getX2());
        }
        if(((b.getX2()>c.getX2())&&(b.getX2()<c.getX1()))) {
            out-=(b.getX2()-c.getX2())/Math.abs(c.getX1()-c.getX2());
        }
        if(((b.getX1()>c.getX2())&&(b.getX1()<c.getX1()))) {
            out-=(c.getX2()-b.getX2())/Math.abs(c.getX1()-c.getX2());
        }
    }
}
Solution

  • I think your approach is way to complicated, and you might just have got lost in all the different possible conditions and configurations.

    If I understood you correctly, then the simplest solution would be to base the computations on the minimum and maximum X-values of both shapes.

    Side note:

    You did not say what type your "shape" objects b and c are. From the methods that you are calling, they might be a java.awt.geom.Line2D objects, but these are not really "four sided". In any case, you can compute the minimum and maximum values as

    double bMinX = Math.min(b.getX1(), b.getX2());
double bMaxX = Math.max(b.getX1(), b.getX2());
double cMinX = Math.min(c.getX1(), c.getX2());
double cMaxX = Math.max(c.getX1(), c.getX2());

    In the program below, I'm using actual Shape objects and call the getBounds2D method to obtain the bounding boxes, which offer these min/max values conveniently. But you can also do this manually.

    When you have these minimum/maxmimum values, you can rule out the cases where an object is either entirely left or entirely right of the other object. If this is not the case, they are overlapping. In this case, you can compute the minimum and maximum of the overlap, and then divide this by the width of the object in question.

    Here is a program where a example objects are created based on the coordinates you gave in the question. You can drag around the objects with the mouse. The overlap is painted and its value is printed.

    Overlap

    The computation takes place in the computeOverlap method.

    import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.awt.geom.Path2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

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


public class ShapeOverlap
{
    public static void main(String[] args) throws IOException
    {
        SwingUtilities.invokeLater(() -> createAndShowGUI());
    }

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

class ShapeOverlapPanel extends JPanel
    implements MouseListener, MouseMotionListener
{
    private final List<Point2D> points0;
    private final List<Point2D> points1;
    private final List<Point2D> draggedPoints;
    private Point previousMousePosition;

    ShapeOverlapPanel()
    {
        points0 = new ArrayList<Point2D>();
        points0.add(new Point2D.Double(160, 200));
        points0.add(new Point2D.Double(180, 200));
        points0.add(new Point2D.Double(270, 260));
        points0.add(new Point2D.Double(250, 260));

        points1 = new ArrayList<Point2D>();
        points1.add(new Point2D.Double(200, 280));
        points1.add(new Point2D.Double(220, 280));
        points1.add(new Point2D.Double(310, 340));
        points1.add(new Point2D.Double(290, 340));

        draggedPoints = new ArrayList<Point2D>();

        addMouseListener(this);
        addMouseMotionListener(this);
    }


    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;
        g.setRenderingHint(
            RenderingHints.KEY_ANTIALIASING,  
            RenderingHints.VALUE_ANTIALIAS_ON);
        g.setColor(Color.WHITE);
        g.fillRect(0, 0, getWidth(), getHeight());

        Shape s0 = createShape(points0);        
        Shape s1 = createShape(points1);

        g.setColor(Color.RED);
        g.fill(s0);
        g.setColor(Color.BLUE);
        g.fill(s1);

        g.setColor(Color.GRAY);
        drawOverlap(g, s0, s1);

        double overlap = computeOverlap(s0, s1);
        g.drawString("Overlap of red from blue: "+overlap, 10, 20);
    }

    private static double computeOverlap(Shape s0, Shape s1)
    {
        Rectangle2D b0 = s0.getBounds2D();
        Rectangle2D b1 = s1.getBounds2D();

        if (b0.getMaxX() < b1.getMinX())
        {
            System.out.println("Shape 0 is left of shape 1");
            return Double.NaN;
        }
        if (b0.getMinX() > b1.getMaxX())
        {
            System.out.println("Shape 0 is right of shape 1");
            return Double.NaN;
        }

        double overlapMinX = Math.max(b0.getMinX(), b1.getMinX());
        double overlapMaxX = Math.min(b0.getMaxX(), b1.getMaxX());
        double overlapSize = overlapMaxX - overlapMinX;

        double relativeOverlap = overlapSize / b0.getWidth();
        return relativeOverlap;
    }

    private void drawOverlap(Graphics2D g, Shape s0, Shape s1)
    {
        Rectangle2D b0 = s0.getBounds2D();
        Rectangle2D b1 = s1.getBounds2D();

        if (b0.getMaxX() < b1.getMinX())
        {
            return;
        }
        if (b0.getMinX() > b1.getMaxX())
        {
            return;
        }

        double overlapMinX = Math.max(b0.getMinX(), b1.getMinX());
        double overlapMaxX = Math.min(b0.getMaxX(), b1.getMaxX());

        g.drawLine((int)overlapMinX, 0, (int)overlapMinX, getHeight());
        g.drawLine((int)overlapMaxX, 0, (int)overlapMaxX, getHeight());
    }


    private static Shape createShape(Iterable<? extends Point2D> points)
    {
        Path2D path = new Path2D.Double();
        boolean first = true;
        for (Point2D p : points)
        {
            if (first)
            {
                path.moveTo(p.getX(), p.getY());
                first = false;
            }
            else
            {
                path.lineTo(p.getX(), p.getY());
            }
        }
        path.closePath();
        return path;
    }

    @Override
    public void mouseDragged(MouseEvent e)
    {
        int dx = e.getX() - previousMousePosition.x;
        int dy = e.getY() - previousMousePosition.y;
        for (Point2D p : draggedPoints)
        {
            p.setLocation(p.getX() + dx, p.getY() + dy);
        }
        repaint();
        previousMousePosition = e.getPoint();
    }

    @Override
    public void mouseMoved(MouseEvent e)
    {
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
    }

    @Override
    public void mousePressed(MouseEvent e)
    {
        draggedPoints.clear();
        Shape s0 = createShape(points0);
        Shape s1 = createShape(points1);
        if (s0.contains(e.getPoint()))
        {
            draggedPoints.addAll(points0);
        }
        else if (s1.contains(e.getPoint()))
        {
            draggedPoints.addAll(points1);
        }
        previousMousePosition = e.getPoint();
    }

    @Override
    public void mouseReleased(MouseEvent e)
    {
        draggedPoints.clear();
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
    }

    @Override
    public void mouseExited(MouseEvent e)
    {
    }


}