logo标签列表

在二维平面上找到共线的点中最多的点数

javaalgorithm
5
这是一道来自leetcode.com的题目：“给定二维平面上的n个点，找到位于同一直线上的最大点数。” 我正在尝试解决它，但我无法通过所有的测试用例。
我的做法是：使用一个哈希表，其键为通过斜率的正切得到的点之间的角度，并且我将每个斜率的值存储在哈希表中。最初，该点的出现次数为1，然后逐渐增加。
我还使用另一个哈希表来计算点的出现次数。
对于像（0,0），（1,0）这样的点，我的代码无法得出正确的答案，应该返回2，但实际上只返回1。
我错在哪里？
我的代码如下：
public class MaxPointsINLine {
    int max = 0;
    int same;

    public int maxPoints(Point[] points) {
        int max = 0;
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        Map<Point, Integer> pointmap = new HashMap<Point, Integer>();
        for(Point point: points)
        {
            if(!pointmap.containsKey(point))
            {
                pointmap.put(point, 1);
            }
            else
            {
                pointmap.put(point, pointmap.get(point)+1);
            }
        }
        if (points.length >= 2) {
            for (int i = 0; i < points.length; i++) {
                for (int j = i ; j < points.length; j++) {
                    double dx = points[j].x - points[i].x;
                    double dy = points[j].y - points[i].y;
                    double slope = Math.atan(dy / dx);
                    if (!map.containsKey(slope)) {
                        map.put(slope, pointmap.get(points[j]));
                    } else
                        map.put(slope, map.get(slope) + 1);
                }
            }
            for (Double key : map.keySet()) {
                if (map.get(key) > max) {
                    max = map.get(key);
                }
            }
            return max;
        } else if (points.length != 0) {
            return 1;
        } else {
            return 0;
        }
    } 

    public static void main(String[] args) {
        Point point1 = new Point(0,0);
        Point point2 = new Point(0,0);
        //Point point3 = new Point(2,2);
        MaxPointsINLine maxpoint = new MaxPointsINLine();
        Point[] points = { point1, point2};
        System.out.println(maxpoint.maxPoints(points));

    }

}

class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object obj) {
        Point that = (Point)obj;
        if (that.x == this.x && that.y == this.y)
            return true;
        else
            return false;
    }

    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 1;
    }
}
你填充了 pointmap，但是你从未使用过它。你是不是想将它纳入算法中？ - Chris Culter
抱歉，@Chris Culter，我正在使用点映射。例如，如果存在像（0,0）（0,0）这样的点，它会在映射中放入值2。代码如下：-if (!map.containsKey(slope)) {map.put(slope, pointmap.get(points[j]));} - user3649361
我不知道原始问题是什么，但我非常不愿意使用atan函数并依赖浮点数比较来解决这个问题。这可能会导致意外的答案（从数学角度来看）。 - Emile
1
请查看这个问题，它可能会对您有所帮助：https://dev59.com/ZW855IYBdhLWcg3wuG6W - Neo
1
如果您希望通过计算找到完全相同的“Double”（考虑到浮点不准确性！），那么使用“Double”作为查找的键非常可疑。此外，任何依赖于“斜率”的点的 几何计算都被认为会失败：当这些点具有相同的x坐标（或在您的情况下：x坐标为0）时，您将面临“无穷大”和“NaN”的问题。此外，即使该线未经过原点，也存在在同一条线上的点。因此，我认为该方法总体上是有缺陷的（但我可能也是错的...）。 - Marco13
3个回答
3

这种通用策略似乎无法奏效。假设我们已经成功地使用键值对 (a, N) 填充了 map，其中 a 是一个角度，而 N 是由角度 a 连接的点对数。考虑以下6个点的排列：

**
  **
**

明确地，这些点位于(0,0)，(1,0)，(2,1)，(3,1)，(0,2)和(1,2)。你可以检查任何一条直线上的最大点数为2。然而，有三对点被相同的角度连接：((0,0)，(1,0))，((2,1)，(3,1))和((0,2)，(1,2))。因此，map将包含一个键值对，其中N = 3，但这不是原问题的答案。
由于以上排列，仅计算斜率是不够的。一个成功的算法将必须以这样一种方式表示直线，使您可以区分平行线。
有其他的方法吗？ - user3649361
当然：对于每个点p，填充一个哈希表来计算从其他点到p的角度，并找到具有最大计数N的角度。然后在循环所有p时累加N的最大值。顺便说一句，就像Marco13所说，如果您想让它工作，请不要将角度表示为浮点数。相反，您可以将角度表示为一对整数(dx, dy)，其中dx和dy被归一化为相对质数。 - Chris Culter
谢谢，但是针对相同的点如[(0,0),(0,0)]，[(1,1),(0,0),(1,1)]，对于第一个情况它给出了1而不是2，对于第二个情况它给出了2而不是3。 - user3649361
没错，对于每个 p，您还需要计算与 p 重合的点数 n，然后将 n 加到 N 中。 - Chris Culter
2
这里最直接的解决方案似乎是：可以考虑每一对点，对于每一对点，计算每个其他点到连接两点的线的距离。如果这个距离几乎为零，则该点在该线上。
当对所有对进行此操作后，可以选择最多点位于连接线上的对。
当然，这不是非常优雅，因为它是O(n^3)并且会进行一些重复的计算。但它非常简单和可靠。我在这里实现了一个MCVE：
可以通过鼠标左键设置点，右键清除屏幕。显示一条线上的最大点数，并突出显示相应的点。
（编辑：根据评论更新以处理距离为0的点）
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.List;

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

public class PointsOnStraightLineTest
{
    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().setLayout(new BorderLayout());
        f.getContentPane().add(new PointsPanel());
        f.setSize(600, 600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

class PointsOnStraightLine
{
    // Large epsilon to make it easier to place
    // some points on one line with the mouse...
    private static final double EPSILON = 5.0; 

    List<Point> maxPointsOnLine = new ArrayList<Point>();

    void compute(List<Point> points)
    {
        maxPointsOnLine = new ArrayList<Point>();

        for (int i=0; i<points.size(); i++)
        {
            for (int j=i+1; j<points.size(); j++)
            {
                Point p0 = points.get(i);
                Point p1 = points.get(j);
                List<Point> resultPoints = null;
                if (p0.distanceSq(p1) < EPSILON)
                {
                    resultPoints = computePointsNearby(p0, points);
                }
                else
                {
                    resultPoints = computePointsOnLine(p0, p1, points);
                }
                if (resultPoints.size() > maxPointsOnLine.size())
                {
                    maxPointsOnLine = resultPoints;
                }
            }
        }
    }

    private List<Point> computePointsOnLine(
        Point p0, Point p1, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = Line2D.ptLineDistSq(p0.x, p0.y, p1.x, p1.y, p.x, p.y);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

    private List<Point> computePointsNearby(
        Point p0, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = p.distanceSq(p0);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

}



class PointsPanel extends JPanel implements MouseListener
{
    private final List<Point> points;
    private final PointsOnStraightLine pointsOnStraightLine;

    PointsPanel()
    {
        addMouseListener(this);

        points = new ArrayList<Point>();
        pointsOnStraightLine = new PointsOnStraightLine();
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;

        g.setColor(Color.BLACK);
        for (Point p : points)
        {
            g.fillOval(p.x-2, p.y-2, 4, 4);
        }

        pointsOnStraightLine.compute(points);

        int n = pointsOnStraightLine.maxPointsOnLine.size();
        g.drawString("maxPoints: "+n, 10, 20);

        g.setColor(Color.RED);
        for (Point p : pointsOnStraightLine.maxPointsOnLine)
        {
            g.drawOval(p.x-3, p.y-3, 6, 6);
        }
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
        if (SwingUtilities.isRightMouseButton(e))
        {
            points.clear();
        }
        else
        {
            points.add(e.getPoint());
        }
        repaint();
    }

    @Override
    public void mousePressed(MouseEvent e)
    {
    }

    @Override
    public void mouseReleased(MouseEvent e)
    {
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
    }

    @Override
    public void mouseExited(MouseEvent e)
    {
    }
}
你有检查过像(0,0)这样的相同点吗？对它们不起作用。 - user3649361
@user3649361，如何处理这些点并不完全清楚。也不清楚在考虑三个点是否“在一条直线上”时应该采用什么（浮点）容差。但是，我已经更新了示例以处理位于同一位置的点，即使它们没有定义线，但有无限多条线。 - Marco13
嗯...它怎么会是O(n^2)？O(n^2)只是遍历所有的配对。计算每个配对的距离另外需要O(n)。所以整个过程是O(n^3)。 - AnT stands with Russia
2
这是我的解决方案：

这个方法对我有用：

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {


        int result = 0;
        for(int i = 0; i<points.length; i++){
            Map<Double, Integer> line = new HashMap<Double, Integer>();
            Point a = points[i];
            int same = 1;    
            //System.out.println(a);
            for(int j = i+1; j<points.length; j++){
                Point b = points[j];
                //System.out.println(" point " + b.toString());
                if(a.x == b.x && a.y == b.y){
                    same++;
                } else {
                    double dy = b.y - a.y;
                    double dx = b.x - a.x;
                    Double slope;
                    if(dy == 0){ // horizontal
                        slope = 0.0;
                    } else if(dx == 0){//eartical
                        slope = Math.PI/2;
                    } else {
                        slope = Math.atan(dy/dx);
                    }
                    Integer slopeVal = line.get(slope);
                    //System.out.println(" slope " + slope + "  slope value " + slopeVal);
                    if(slopeVal == null){
                        slopeVal = 1;
                    } else {
                        slopeVal += 1;
                    }
                    line.put(slope, slopeVal);
                }
            }

            for (Double key : line.keySet()) {
                Integer val = line.get(key);
                result = Math.max(result, val + same);
            }
            // for all points are same
            result = Math.max(result, same);

        }
        return result;
    }



}
这怎么可能行呢？因为这只考虑了两点之间的斜率而没有考虑y轴截距。即使两条平行线之间的点不在同一条直线上，它们也会被计算在一起，尽管它们具有相同的斜率。 - John Allard
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接