Determining if an arc contains/covers another arc

Question

I am, first of all, drawing two arcs randomly using the Graphics drawArc and fillArc methods. One arc, say arc1 is bigger than the other arc, say arc2. Now i want to see if arc1, contains(wholly or partly) arc2. I have tried various ways but to no avail. Forexample, first of all calculating the distances between them and then taking the dot product of these two and seeing if its greater than the radius of the first arc multiplied by the cosine of its orientation. Still no success, any help or suggestions offered will be greatly appreciated. Is there a better/another approach to achieve this? Is it also possible to estimate how much of arc2 is covered by arc1? thanks,

Answer 1

The answer by gpash lists several options. As mentioned in a comment, I'd recommend Area-based apprach for the generic case. Although area computations (like computing the intersection, for this example) can be expensive, they are likely a good tradeoff between the image-based and the purely analytical approaches:

• The image-based approach raises some questions, e.g. regarding the image size. Additionally, the runtime and memory consumption may be large for "large" shapes (imagine shapes that cover a region of, say, 1000x1000 pixels).
• The purely analytical solution may be rather mathematically involved. One could consider breaking it down to simpler tasks, and it's certainly doable, but not trivial. Maybe more importantly: This approach does not generalize for other Shape types.

With the Area based solution, computing the intersection between two arbitrary shapes s0 and s1 (which may be Arc2D, or any other shape) is fairly trivial:

    Area a = new Area(s0);
    a.intersect(new Area(s1));

(that's it).

---

A side note: One could consider performing a conservative test: The shapes can not intersect if their bounding volumes do not intersect. So for certain use-cases, one could consider doing something like this:

Shape s0 = ...;
Shape s1 = ...;
if (!s0.getBounds().intersects(s1.getBounds()))
{
    // The bounds do not intersect. Then the shapes 
    // can not intersect.
    return ...;
}
else
{
    // The bounds DO intesect. Perform the Area-based 
    // intersection computation here:
    ...
}

---

What is left then is the computation of the area of an Area - that is, the size of the intersection area. The Area class has a method that can be used to check whether the area isEmpty. But it does not have a method to compute the size of the area. However, this can be computed by converting the resulting area into a polygon using a (flattening!) PathIterator, and then computing the polygon area as, for example in the answers to this question.

What may be tricky about this is that in general, areas can be signed (that is, they can be positive or negative, depending on whether the vertices of the polygon are given in counterclockwise or or clockwise order, respectively). Additionally, the intersection between two shapes does not necessarily result in a single, connected shape, but may result in different closed regions, as shown in this image:

The image is a screenshot from the following MCVE that allows dragging around the given shapes with the mouse, and prints the area of the shapes and their intersection.

_{This uses some utility methods for the area computation that are taken from a set of utilites for geometry in general, and shapes in particular, which I started collecting a while ago)}

import java.awt.Color;
import java.awt.Font;
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.AffineTransform;
import java.awt.geom.Arc2D;
import java.awt.geom.Area;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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


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

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        f.getContentPane().add(new ShapeIntersectionAreaTestPanel());

        f.setSize(800,800);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}


class ShapeIntersectionAreaTestPanel extends JPanel
    implements MouseListener, MouseMotionListener
{
    private Shape shape0;
    private Shape shape1;
    private Shape draggedShape;
    private Point previousMousePosition;

    ShapeIntersectionAreaTestPanel()
    {
        shape0 = new Arc2D.Double(100, 160, 200, 200, 90, 120, Arc2D.PIE);
        shape1 = new Arc2D.Double(300, 400, 100, 150, 220, 260, Arc2D.PIE);

        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.RED);
        g.fill(shape0);
        g.setColor(Color.BLUE);
        g.fill(shape1);

        Shape intersection = 
            ShapeIntersectionAreaUtils.computeIntersection(shape0, shape1);
        g.setColor(Color.MAGENTA);
        g.fill(intersection);

        double area0 = Math.abs( 
            ShapeIntersectionAreaUtils.computeSignedArea(shape0, 1.0));
        double area1 = Math.abs( 
            ShapeIntersectionAreaUtils.computeSignedArea(shape1, 1.0));
        double areaIntersection = Math.abs( 
            ShapeIntersectionAreaUtils.computeSignedArea(intersection, 1.0));
        g.setColor(Color.BLACK);
        g.setFont(new Font("Monospaced", Font.PLAIN, 12));
        g.drawString(String.format("Red area         : %10.3f", area0), 10, 20);
        g.drawString(String.format("Blue area        : %10.3f", area1), 10, 40);
        g.drawString(String.format("Intersection area: %10.3f", areaIntersection), 10, 60);
    }


    @Override
    public void mouseDragged(MouseEvent e)
    {
        int dx = e.getX() - previousMousePosition.x;
        int dy = e.getY() - previousMousePosition.y;
        AffineTransform at = 
            AffineTransform.getTranslateInstance(dx, dy);
        if (draggedShape == shape0)
        {
            shape0 = at.createTransformedShape(draggedShape);
            draggedShape = shape0;
        }
        if (draggedShape == shape1)
        {
            shape1 = at.createTransformedShape(draggedShape);
            draggedShape = shape1;
        }
        repaint();
        previousMousePosition = e.getPoint();
    }

    @Override
    public void mouseMoved(MouseEvent e)
    {
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
    }

    @Override
    public void mousePressed(MouseEvent e)
    {
        draggedShape = null;
        if (shape0.contains(e.getPoint()))
        {
            draggedShape = shape0;
        }
        if (shape1.contains(e.getPoint()))
        {
            draggedShape = shape1;
        }
        previousMousePosition = e.getPoint();
    }

    @Override
    public void mouseReleased(MouseEvent e)
    {
        draggedShape = null;
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
    }

    @Override
    public void mouseExited(MouseEvent e)
    {
    }

}

// Utility methods related to shape and shape area computations, mostly taken from 
// https://github.com/javagl/Geom/blob/master/src/main/java/de/javagl/geom/Shapes.java
class ShapeIntersectionAreaUtils
{
    public static Shape computeIntersection(Shape s0, Shape s1)
    {
        Area a = new Area(s0);
        a.intersect(new Area(s1));
        return a;
    }


    /**
     * Compute all closed regions that occur in the given shape, as
     * lists of points, each describing one polygon
     * 
     * @param shape The shape
     * @param flatness The flatness for the shape path iterator
     * @return The regions
     */
    static List<List<Point2D>> computeRegions(
        Shape shape, double flatness)
    {
        List<List<Point2D>> regions = new ArrayList<List<Point2D>>();
        PathIterator pi = shape.getPathIterator(null, flatness);
        double coords[] = new double[6];
        List<Point2D> region = Collections.emptyList();
        while (!pi.isDone())
        {
            switch (pi.currentSegment(coords))
            {
                case PathIterator.SEG_MOVETO:
                    region = new ArrayList<Point2D>();
                    region.add(new Point2D.Double(coords[0], coords[1]));
                    break;

                case PathIterator.SEG_LINETO:
                    region.add(new Point2D.Double(coords[0], coords[1]));
                    break;

                case PathIterator.SEG_CLOSE:
                    regions.add(region);
                    break;

                case PathIterator.SEG_CUBICTO:
                case PathIterator.SEG_QUADTO:
                default:
                    throw new AssertionError(
                        "Invalid segment in flattened path");
            }
            pi.next();
        }
        return regions;
    }

    /**
     * Computes the (signed) area enclosed by the given point list.
     * The area will be positive if the points are ordered 
     * counterclockwise, and and negative if the points are ordered 
     * clockwise.
     * 
     * @param points The points
     * @return The signed area
     */
    static double computeSignedArea(List<? extends Point2D> points)
    {
        double sum0 = 0;
        double sum1 = 0;
        for (int i=0; i<points.size()-1; i++)
        {
            int i0 = i;
            int i1 = i + 1;
            Point2D p0 = points.get(i0);
            Point2D p1 = points.get(i1);
            double x0 = p0.getX();
            double y0 = p0.getY();
            double x1 = p1.getX();
            double y1 = p1.getY();
            sum0 += x0 * y1;
            sum1 += x1 * y0;
        }
        Point2D p0 = points.get(0);
        Point2D pn = points.get(points.size()-1);
        double x0 = p0.getX();
        double y0 = p0.getY();
        double xn = pn.getX();
        double yn = pn.getY();
        sum0 += xn * y0;
        sum1 += x0 * yn;
        double area = 0.5 * (sum0 - sum1);
        return area;
    }

    /**
     * Compute the (signed) area that is covered by the given shape.<br>
     * <br>
     * The area will be positive for regions where the points are 
     * ordered counterclockwise, and and negative for regions where 
     * the points are ordered clockwise.
     * 
     * @param shape The shape
     * @param flatness The flatness for the path iterator
     * @return The signed area
     */ 
    public static double computeSignedArea(Shape shape, double flatness)
    {
        double area = 0;
        List<List<Point2D>> regions = computeRegions(shape, flatness);
        for (List<Point2D> region : regions)
        {
            double signedArea = computeSignedArea(region);
            area += signedArea;
        }
        return area;
    }
}

(Note: The mechanisms for dragging the shapes are not particularly elegant. In a real application, this should be solved differently - this is just for the demonstration of the area computation methods)

Answer 2

I will give you an easy solution that counts for any shape - not only arcs:

  public Vector measureArea(int[] pix) {
    int i;
    Vector v=new Vector();
    for(i=0; i<pix.length; i++)
      if((pix[i]&0x00ffffff)==0x00000000) v.add(i);
    return v;
  }

This finds the pixels that belong to this area: you could fill the arc as follows then call this function:

BufferedImage bim=new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
Graphics g=bim.getGraphics();
g.setColor(Color.white);
g.fillRect(0, 0, w, h);
g.setColor(Color.black);
g2.fillArc(x, y, 2*w/16, 2*h/16, 270, 250);
int[] pix=bim.getRGB(0, 0, w, h, null, 0, w);
Vector v=measureArea(pix);

Repeat with the second arc then find the common points.

for(i=0; i<v.size(); i++) {
  int I=((Integer)v.get(i)).intValue();
  for(j=0; j<v2.size(); j++) {
    int J=((Integer)v2.get(j)).intValue();
    if(I==J) ..... // do something
  }
}

If you want more of a mathematical approach you have to define the filled arc in terms of circle (or maybe two wedges) and find the area of the intersecting these shapes.

There is a third approach using Areas in java.

Area a=new Area(new Arc2D.Double(x+3*w/4-w/16, y+h/4-h/16, 2*w/16, 2*h/16, 270, 250, Arc2D.OPEN));
Area a2=new Area(new Arc2D.Double(x+3*w/4, y+h/4, 2*w/16, 2*h/16, 270, 200, Arc2D.OPEN));
Area intrsct=new Area(new Arc2D.Double(x+3*w/4-w/16, y+h/4-h/16, 2*w/16, 2*h/16, 270, 250, Arc2D.OPEN));
intrsct.intersect(a2);

Now intrsct has the intersection.

If we expand this to simple Shapes we have:

Arc2D.Double a=new Arc2D.Double(x+3*w/4-w/16, y+h/4-h/16, 2*w/16, 2*h/16, 270, 250, Arc2D.OPEN);
Arc2D.Double a2=new Arc2D.Double(x+3*w/4, y+h/4, 2*w/16, 2*h/16, 270, 200, Arc2D.OPEN);
Rectangle b=a.getBounds();
int intrsct=0;
for(i=0; i<b.getWidth(); i++)
for(j=0; j<b.getHeight(); j++)
  if(a.contains(b.x+i, b.y+j) && a2.contains(b.x+i, b.y+j)) intrsct++;

A fourth approach.

--

If you want an arc with a given color you need to check for that color in the first approach. So we change measure area as follows:

  public Vector measureArea(int[] pix, int color) {
    int i;
    Vector v=new Vector();
    int c=color&0x00ffffff;
    for(i=0; i<pix.length; i++)
      if((pix[i]&0x00ffffff)==c) v.add(i);
    return v;
  }

and call it measureArea(pix, Color.red.getRGB()) for example.

And make sure you clear the image for each shape to be counted on its own:

 public Image init( Graphics g )
    {
         bim=new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
         g=bim.getGraphics();
         g.setColor(Color.yellow);
         g.fillRect(0, 0, w, h);
         g.setColor(Color.red);
         g.fillArc(x, y, 300, 300, 270, 75);  // 2*w/16, 2*h/16 
         int[] pix=bim.getRGB(0, 0, w, h, null, 0, w);
         Vector v1=measureArea(pix, Color.red.getRGB());
         g.setColor(Color.yellow);
         g.fillRect(0, 0, w, h);
         g.setColor(Color.blue);
         g.fillArc(x+100, y+100, 150, 150, 270, 45); //2*w/32, 2*h/32,
         pix=bim.getRGB(0, 0, w, h, null, 0, w);
         Vector v2=measureArea(pix, Color.blue.getRGB());
         System.out.println( intersect(v1, v2) );
         return bim;
    }

Notes 3: the method with Areas is independent of color - use that if it works. The method with pixels can be used later if you have complicated shapes:

To draw all the shapes together just do what you do now: keep them in one image. To measure the area use another image bim2 where you draw each shape successively call the measure area function clear the image etc - it doesnt have to be shown any where - you have the other image to show all the shapes together. I hope this works.