algorithm - 如何生成二维凹多边形的 "inner shape"？

Question

我有一个二维点列表，它是一个闭环、二维、凹多边形。

我想生成第二个多边形，它完全位于第一个多边形内部，并且第一个多边形的每个顶点/边与第二个多边形的每个顶点/边之间的距离恒定。

基本上，第一个多边形是“外墙”，第二个多边形是“内墙”，两墙之间的距离不变。

如何做这样的事情？

Answer 1

对于您不关心自交的情况，构造非常简单:

对于多边形的每个顶点:

• 取上一条和下一条线段
• 计算这些线段的法线
• 沿法线移动线段
• 计算移动线段的交点

下面是一个MCVE在 Java/Swing 中实现。实际计算发生在 computeOffsetPolygonPoints 中，将其转换为其他语言和 API 应该很容易。

对于您还必须处理自相交的情况，事情可能会变得更加棘手。然后有必要定义预期结果，特别是对于多边形本身自相交的情况...

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;

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

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

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

        InnerPolygonShapePanel innerPolygonShapePanel = 
            new InnerPolygonShapePanel();
        JSlider offsetSlider = new JSlider(0, 100, 40);
        offsetSlider.addChangeListener(e -> 
        {
            double alpha = offsetSlider.getValue() / 100.0;
            double offset = -50.0 + alpha * 100.0;
            innerPolygonShapePanel.setOffset(offset);
        });

        f.getContentPane().setLayout(new BorderLayout());
        f.getContentPane().add(innerPolygonShapePanel, BorderLayout.CENTER);
        f.getContentPane().add(offsetSlider, BorderLayout.SOUTH);
        f.setSize(800,800);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

}

class InnerPolygonShapePanel extends JPanel 
    implements MouseListener, MouseMotionListener
{
    private final List<Point2D> points;
    private Point2D draggedPoint;
    private double offset = -10.0;

    public InnerPolygonShapePanel()
    {
        this.points = new ArrayList<Point2D>();

        points.add(new Point2D.Double(132,532));
        points.add(new Point2D.Double(375,458));
        points.add(new Point2D.Double(395,267));
        points.add(new Point2D.Double(595,667));

        addMouseListener(this);
        addMouseMotionListener(this);
    }

    public void setOffset(double offset)
    {
        this.offset = offset;
        repaint();
    }

    @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.BLACK);
        paint(g, points);

        List<Point2D> offsetPolygonPoints = 
            computeOffsetPolygonPoints(points, offset);
        g.setColor(Color.BLUE);
        paint(g, offsetPolygonPoints);

    }


    private static void paint(Graphics2D g, List<Point2D> points)
    {
        for (int i = 0; i < points.size(); i++)
        {
            int i0 = i;
            int i1 = (i + 1) % points.size();
            Point2D p0 = points.get(i0);
            Point2D p1 = points.get(i1);
            g.draw(new Line2D.Double(p0, p1));
        }

        g.setColor(Color.RED);
        for (Point2D p : points)
        {
            double r = 5;
            g.draw(new Ellipse2D.Double(p.getX()-r, p.getY()-r, r+r, r+r));
        }

    }

    private static List<Point2D> computeOffsetPolygonPoints(
        List<Point2D> points, double offset)
    {
        List<Point2D> result = new ArrayList<Point2D>();
        Point2D absoluteLocation = new Point2D.Double();
        for (int i = 0; i < points.size(); i++)
        {
            // Consider three consecutive points (previous, current, next)
            int ip = (i - 1 + points.size()) % points.size();
            int ic = i;
            int in = (i + 1) % points.size();
            Point2D pp = points.get(ip);
            Point2D pc = points.get(ic);
            Point2D pn = points.get(in);

            // Compute the line segments between the previous and the current
            // point, and the current and the next point, and compute their
            // normal
            Point2D line0 = difference(pc, pp);
            Point2D direction0 = normalize(line0);
            Point2D normal0 = rotateCw(direction0);

            Point2D line1 = difference(pn, pc);
            Point2D direction1 = normalize(line1);
            Point2D normal1 = rotateCw(direction1);

            // Shift both line segments along the normal
            Point2D segment0p0 = add(pp, offset, normal0);
            Point2D segment0p1 = add(pc, offset, normal0);
            Point2D segment1p0 = add(pc, offset, normal1);
            Point2D segment1p1 = add(pn, offset, normal1);

            // Compute the intersection between the shifted line segments
            intersect(
                segment0p0.getX(), segment0p0.getY(),
                segment0p1.getX(), segment0p1.getY(),
                segment1p0.getX(), segment1p0.getY(),
                segment1p1.getX(), segment1p1.getY(),
                null, absoluteLocation);

            result.add(new Point2D.Double(
                absoluteLocation.getX(), absoluteLocation.getY()));
        }
        return result;
    }


    @Override
    public void mouseDragged(MouseEvent e)
    {
        if (draggedPoint != null)
        {
            draggedPoint.setLocation(e.getX(), e.getY());
            repaint();
        }
    }


    @Override
    public void mousePressed(MouseEvent e)
    {
        final double thresholdSquared = 10 * 10;
        Point2D p = e.getPoint();
        Point2D closestPoint = null;
        double minDistanceSquared = Double.MAX_VALUE;
        for (Point2D point : points)
        {
            double dd = point.distanceSq(p);
            if (dd < thresholdSquared && dd < minDistanceSquared)
            {
                minDistanceSquared = dd;
                closestPoint = point;
            }
        }
        draggedPoint = closestPoint;
    }

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

    @Override
    public void mouseMoved(MouseEvent e)
    {
        // Nothing to do here
    }


    @Override
    public void mouseClicked(MouseEvent e)
    {
        // Nothing to do here
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
        // Nothing to do here
    }


    @Override
    public void mouseExited(MouseEvent e)
    {
        // Nothing to do here
    }


    private static Point2D difference(Point2D p0, Point2D p1)
    {
        double dx = p0.getX() - p1.getX();
        double dy = p0.getY() - p1.getY();
        return new Point2D.Double(dx, dy);
    }

    private static Point2D add(Point2D p0, double factor, Point2D p1)
    {
        double x0 = p0.getX();
        double y0 = p0.getY();
        double x1 = p1.getX();
        double y1 = p1.getY();
        return new Point2D.Double(x0 + factor * x1, y0 + factor * y1);
    }

    private static Point2D rotateCw(Point2D p)
    {
        return new Point2D.Double(p.getY(), -p.getX());
    }

    private static Point2D normalize(Point2D p)
    {
        double x = p.getX();
        double y = p.getY();
        double length = Math.hypot(x, y);
        return new Point2D.Double(x / length, y / length);
    }


    // From https://github.com/javagl/Geom/blob/master/src/main/java/
    // de/javagl/geom/Intersections.java

    private static final double DOUBLE_EPSILON = 1e-6;

    /**
     * Computes the intersection of the specified lines.
     * 
     * Ported from 
     * http://www.geometrictools.com/LibMathematics/Intersection/
     *     Wm5IntrSegment2Segment2.cpp
     * 
     * @param s0x0 x-coordinate of point 0 of line segment 0
     * @param s0y0 y-coordinate of point 0 of line segment 0
     * @param s0x1 x-coordinate of point 1 of line segment 0
     * @param s0y1 y-coordinate of point 1 of line segment 0
     * @param s1x0 x-coordinate of point 0 of line segment 1
     * @param s1y0 y-coordinate of point 0 of line segment 1
     * @param s1x1 x-coordinate of point 1 of line segment 1
     * @param s1y1 y-coordinate of point 1 of line segment 1
     * @param relativeLocation Optional location that stores the 
     * relative location of the intersection point on 
     * the given line segments
     * @param absoluteLocation Optional location that stores the 
     * absolute location of the intersection point
     * @return Whether the lines intersect
     */
    public static boolean intersect( 
        double s0x0, double s0y0,
        double s0x1, double s0y1,
        double s1x0, double s1y0,
        double s1x1, double s1y1,
        Point2D relativeLocation,
        Point2D absoluteLocation)
    {
        double dx0 = s0x1 - s0x0;
        double dy0 = s0y1 - s0y0;
        double dx1 = s1x1 - s1x0;
        double dy1 = s1y1 - s1y0;

        double invLen0 = 1.0 / Math.sqrt(dx0*dx0+dy0*dy0); 
        double invLen1 = 1.0 / Math.sqrt(dx1*dx1+dy1*dy1); 

        double dir0x = dx0 * invLen0;
        double dir0y = dy0 * invLen0;
        double dir1x = dx1 * invLen1;
        double dir1y = dy1 * invLen1;

        double dot = dotPerp(dir0x, dir0y, dir1x, dir1y);
        if (Math.abs(dot) > DOUBLE_EPSILON)
        {
            if (relativeLocation != null || absoluteLocation != null)
            {
                double c0x = s0x0 + dx0 * 0.5;
                double c0y = s0y0 + dy0 * 0.5;
                double c1x = s1x0 + dx1 * 0.5;
                double c1y = s1y0 + dy1 * 0.5;

                double cdx = c1x - c0x;
                double cdy = c1y - c0y;

                double dot0 = dotPerp(cdx, cdy, dir0x, dir0y);
                double dot1 = dotPerp(cdx, cdy, dir1x, dir1y);
                double invDot = 1.0/dot;
                double s0 = dot1*invDot;
                double s1 = dot0*invDot;
                if (relativeLocation != null)
                {
                    double n0 = (s0 * invLen0) + 0.5;
                    double n1 = (s1 * invLen1) + 0.5;
                    relativeLocation.setLocation(n0, n1);
                }
                if (absoluteLocation != null)
                {
                    double x = c0x + s0 * dir0x;
                    double y = c0y + s0 * dir0y;
                    absoluteLocation.setLocation(x, y);
                }
            }
            return true;
        }
        return false;
    }

    /**
     * Returns the perpendicular dot product, i.e. the length
     * of the vector (x0,y0,0)x(x1,y1,0).
     * 
     * @param x0 Coordinate x0
     * @param y0 Coordinate y0
     * @param x1 Coordinate x1
     * @param y1 Coordinate y1
     * @return The length of the cross product vector
     */
    private static double dotPerp(double x0, double y0, double x1, double y1)
    {
        return x0*y1 - y0*x1;
    }    

}