计算二维空间中两点之间的对角线交点时如何确定+/-符号? [英] How to determine +/- sign when calculating diagonal intersections between two points in 2D space?

问题描述

这是另一个问题的一个分支 并且与 Keith Randall 对问题的回答有关.请快速查看那里的图片，看看下面的功能正在尝试做什么.

This is an offshoot of another question and has to do with Keith Randall's answer to the problem. Please do have a quick look at the image there to see what the function below is trying to do.

简而言之，如果x2 != x1 和y2 != y1，则二维网格上的任意两点都会有两个对角线交点.我实现了以下功能，但无法确定如何确定要从中减去增量的单元格以及要添加的单元格.因此，对于某些坐标对，结果是准确的，而对于其他坐标，结果是相反的.

In short, any two points on a 2D grid would have two diagonal intersections if x2 != x1 and y2 != y1. I implemented the following function but cannot figure out how to determine which cell to subtract delta from and which to add to. As a result, for some pair of coordinates, the results are accurate while for others they are reversed.

// This class is the same as [Point] except
// it uses BigInteger instead of Int32 types.
public class Cell
{
    System.Numerics.BigInteger X = 0;
    System.Numerics.BigInteger Y = 0;
}

public List<Cell> GetIntersections (Cell c1, Cell c2)
{
    List<Cell> cells = new List<Cell>();
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
    height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
    delta = System.Numerics.BigInteger.Abs(height - width);
    deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

    // INTRODUCE CONDITIONS HERE TO DETERMINE +/- COMBINATION.
    cells.Add(new Cell(c1.X - deltaHalf, c1.Y + deltaHalf));
    cells.Add(new Cell(c2.X + deltaHalf, c2.Y - deltaHalf));

    return (cells);
}

起初我认为这是一个简单的梯度/斜率问题，但我似乎无法在 slope 和 +/- deltaHalf 组合之间找到一致的相关性.

At first I thought this was a simple gradient/slope issue but I cannot seem to find a consistent correlation between slope and +/- deltaHalf combinations.

重要提示:请注意，可接受的答案应该只进行 x1、y1、x2、y2 比较.由于性能损失，实际上计算线的斜率不是一种选择.我们已经在除以 2，而且负担不起另一个.

IMPORTANT: Please note that acceptable answers should only do x1, y1, x2, y2 comparisons. Actually calculating the slope of the line is not an option due to performance penalties. We are already doing a division by 2 and cannot afford another.

推荐答案

我知道答案就在简单的比较中，而不必计算斜边.

I knew the answer was somewhere in simple comparisons instead of having to calculate hypotenuse.

public List<Cell> GetCellIntersections (Cell cell1, Cell cell2)
{
    Cell c1 = null;
    Cell c2 = null;
    List<Cell> cells = null;
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    cells = new List<Cell>();

    // Sorting on y reduces conditions from 8 to 4.
    if (cell1.Y < cell2.Y)
    {
        c1 = cell1;
        c2 = cell2;
    }
    else
    {
        c1 = cell2;
        c2 = cell1;
    }

    if ((c1.X != c2.X) && (c1.Y != c2.Y))
    {
        width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
        height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
        delta = System.Numerics.BigInteger.Abs(height - width);
        deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

        if ((c1.X < c2.X) && (c1.Y < c2.Y))
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y + deltaHalf));
            }
        }
        else
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y + deltaHalf));
            }
        }
    }

    return (cells);
}

这篇关于计算二维空间中两点之间的对角线交点时如何确定+/-符号?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！