区域外的点哪个最接近点内? [英] Point Outside of Area Which is Closest to Point Inside?

查看:25
本文介绍了区域外的点哪个最接近点内?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个程序,其中一个实体在二维空间中移动.为了移动一步,实体选择它的下一个点,然后将它设置为他的当前点.

I have a program where an entity moves around in two-dimensional space. To move one step, the entity picks its next point, and then sets it as his current point.

然而,有时实体的下一个点位于一个被禁止的Area (java.awt.geom.Area)(禁止区域"实际上是一个速度障碍).

Sometimes, however, the entity's next point lies in an Area (java.awt.geom.Area) that is forbidden (the "forbidden area" is actually a velocity obstacle).

实体如何选择Area之外最接近实体首选点的点?

How can the entity pick the point outside the Area which is closest to the entity's preferred point?

Area 由不同的形状组成(有时形状不相接触).

The Area is composed of different shapes (sometimes, the shapes are not touching).

我最初的计划是简单地画一条线到首选点.无论该线首先与 Area 相交的地方,这将是次佳点.然而,找到一条线和一个Area 之间的交点是相当复杂的.

My initial plan was to simply draw a line to the preferred point. Wherever the line intersected the Area first, this would be the next-best point. However, finding the intersection between a line and an Area turns out to be quite complex.

这不一定会找到最近的点.这只会在同一轨迹上找到壁橱点.我正在寻找最接近的点.

This wouldn't necessarily find the closest point. This would just find the closet point on the same trajectory. I'm looking for the closest possible point.

也许 Area 不是最好使用的类.我所需要的只是可以添加多个形状的东西,即使这些形状没有相互接触.

Perhaps Area isn't the best class to use. All I require is something that can add multiple shapes, even when the shapes aren't touching.

推荐答案

我已经解决了这个问题:

I've solved the problem:

首先,找出约束Area的所有线段.我已经编写了代码来做到这一点 另一种答案.

First, find all the line segments that constrain the Area. I've written code to do that on a different answer.

然后,只需遍历每个线段,并记录线段上最接近实体所需点的点.将这些存储在您选择的数据结构中(例如,ArrayList).

Then, it's just a matter of iterating through each line segment, and recording the point on the segment that's closest to the entity's desired point. Store these in the data structure of your choice (e.g., an ArrayList).

参见:点与线段之间的最短距离

最后,确定哪个点最接近所需的点.瞧!

Lastly, determine which of the points is closest to the desired point. Voilà!

这是一个演示:

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Random;

import javax.swing.JFrame;

public class AreaTest extends JFrame{
    private static final long serialVersionUID = -2221432546854106311L;

    Area area = new Area();
    ArrayList<Line2D.Double> areaSegments = new ArrayList<Line2D.Double>();
    Point2D.Double insidePoint = new Point2D.Double(225, 225);
    Point2D.Double closestPoint = new Point2D.Double(-1, -1);
    Point2D.Double bestPoint = new Point2D.Double(-1, -1);
    ArrayList<Point2D.Double> closestPointList = new ArrayList<Point2D.Double>();

    AreaTest() {
        Path2D.Double triangle = new Path2D.Double();
        Random random = new Random();

        // Draw three random triangles
        for (int i = 0; i < 3; i++) {
            triangle.moveTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.closePath();
            area.add(new Area(triangle));
            triangle.reset();
        }

        // Place a point inside the area
        if (!area.contains(insidePoint)); {
            while (!area.contains(insidePoint)) {
                insidePoint.setLocation(random.nextInt(400) + 50, random.nextInt(400) + 50);
            }
        }

        // Note: we're storing double[] and not Point2D.Double
        ArrayList<double[]> areaPoints = new ArrayList<double[]>();
        double[] coords = new double[6];

        for (PathIterator pi = area.getPathIterator(null); !pi.isDone(); pi.next()) {

            // Because the Area is composed of straight lines
            int type = pi.currentSegment(coords);
            // We record a double array of {segment type, x coord, y coord}
            double[] pathIteratorCoords = {type, coords[0], coords[1]};
            areaPoints.add(pathIteratorCoords);
        }

        double[] start = new double[3]; // To record where each polygon starts
        for (int i = 0; i < areaPoints.size(); i++) {
            // If we're not on the last point, return a line from this point to the next
            double[] currentElement = areaPoints.get(i);

            // We need a default value in case we've reached the end of the ArrayList
            double[] nextElement = {-1, -1, -1};
            if (i < areaPoints.size() - 1) {
                nextElement = areaPoints.get(i + 1);
            }

            // Make the lines
            if (currentElement[0] == PathIterator.SEG_MOVETO) {
                start = currentElement; // Record where the polygon started to close it later
            } 

            if (nextElement[0] == PathIterator.SEG_LINETO) {
                areaSegments.add(
                        new Line2D.Double(
                            currentElement[1], currentElement[2],
                            nextElement[1], nextElement[2]
                        )
                    );
            } else if (nextElement[0] == PathIterator.SEG_CLOSE) {
                areaSegments.add(
                        new Line2D.Double(
                            currentElement[1], currentElement[2],
                            start[1], start[2]
                        )
                    );
            }
        }

        // Calculate the nearest point on the edge
        for (Line2D.Double line : areaSegments) {

            // From: https://stackoverflow.com/questions/6176227
            double u = 
              ((insidePoint.getX() - line.x1) * (line.x2 - line.x1) + (insidePoint.getY() - line.y1) * (line.y2 - line.y1))
            / ((line.x2 - line.x1) * (line.x2 - line.x1) + (line.y2 - line.y1) * (line.y2 - line.y1));

            double xu = line.x1 + u * (line.x2 - line.x1);
            double yu = line.y1 + u * (line.y2 - line.y1);

            if (u < 0) {
                closestPoint.setLocation(line.getP1());
            } else if (u > 1) {
                closestPoint.setLocation(line.getP2());
            } else {
                closestPoint.setLocation(xu, yu);
            }

            closestPointList.add((Point2D.Double) closestPoint.clone());

            if (closestPoint.distance(insidePoint) < bestPoint.distance(insidePoint)) {
                bestPoint.setLocation(closestPoint);
            }
        }

        setSize(new Dimension(500, 500));
        setLocationRelativeTo(null); // To center the JFrame on screen
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setResizable(false);
        setVisible(true);
    }

    public void paint(Graphics g) {
        // Fill the area
        Graphics2D g2d = (Graphics2D) g;
        g.setColor(Color.lightGray);
        g2d.fill(area);

        // Draw the border line by line
        g.setColor(Color.black);
        for (Line2D.Double line : areaSegments) {
            g2d.draw(line);
        }

        // Draw the inside point
        g.setColor(Color.red);
        g2d.fill(
                new Ellipse2D.Double(
                        insidePoint.getX() - 3,
                        insidePoint.getY() - 3,
                        6,
                        6
                        )
            );

        // Draw the other close points
        for (Point2D.Double point : closestPointList) {
            g.setColor(Color.black);
            g2d.fill(
                    new Ellipse2D.Double(
                            point.getX() - 3,
                            point.getY() - 3,
                            6,
                            6
                            )
                );
        }

        // Draw the outside point
        g.setColor(Color.green);
        g2d.fill(
                new Ellipse2D.Double(
                        bestPoint.getX() - 3,
                        bestPoint.getY() - 3,
                        6,
                        6
                        )
            );
    }

    public static void main(String[] args) {
        new AreaTest();
    }
}

结果如下:

再说一遍:

这篇关于区域外的点哪个最接近点内?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆