Python或工具点之间的距离

Question

我正在使用工具或约束解算器查找房间中项目的工作位置。我使用CP解算器而不是背包解算器，因为我需要添加额外的约束

我将每个项目表示为x间隔和y间隔，并添加如下约束：

model.AddNoOverlap2D(x_intervals, y_intervals)

这有助于放置对象，使它们不会重叠，但我需要添加另一个约束，以确保对象之间有一定的距离。这应该是对象之间的基本2D距离，但此公式需要sqrt和pow函数，而IntVar项似乎不可用

我曾考虑过使用另一个以每个主对象为中心的“间隔对象”，并添加另一个NoOverlap2D约束，但这将导致在距离公式为更精确的距离且不会在房间中浪费太多空间的情况下，遮挡整个正方形的空间

编辑-下面的代码现在用于对项目设置距离约束

根据Laurent的建议，我尝试使用许多中间变量来处理此问题，但我一直坚持将定义形状位置间隔的INTVAR相乘或相除：

# Now lets make all possible combinations and make a distance between them
combos = list(combinations(range(len(rects_data)), 2))

print(combos) 

currentDistanceId = 0

distanceVariables = []

for listSet in combos:
    leftItem = all_vars[listSet[0]]
    rightItem = all_vars[listSet[1]]

    if leftItem.holderType == HolderType.Person and rightItem.holderType == HolderType.Person:
        print(f"Adding distances between {listSet[0]} and {listSet[1]} because both are people")
        
        currentDistanceId = currentDistanceId + 1

        # Add an intermediate variable to store the sum of x for the center of left object
        leftCenterXSum = model.NewIntVar(0, horizon.x*2, f"leftCenterXSum{currentDistanceId}")
        # Add constraint to it
        model.Add(leftCenterXSum == leftItem.x2 + leftItem.x1)
        # Add an intermediate variable to store the center of x of the left object
        leftCenterX = model.NewIntVar(0, horizon.x, f"leftCenterX{currentDistanceId}")
        # Add a constraint to divide it by 2 to make it te center
        model.AddDivisionEquality(leftCenterX, leftCenterXSum, 2)

        ## Repeat for x and y for left and right objects
        leftCenterYSum = model.NewIntVar(0, horizon.y*2, f"leftCenterYSum{currentDistanceId}")
        model.Add(leftCenterYSum == leftItem.y2 + leftItem.y1)
        leftCenterY = model.NewIntVar(0, horizon.y, f"leftCenterY{currentDistanceId}")
        model.AddDivisionEquality(leftCenterY, leftCenterYSum, 2)

        rightCenterXSum = model.NewIntVar(0, horizon.x*2, f"rightCenterXSum{currentDistanceId}")
        model.Add(rightCenterXSum == rightItem.x2 + rightItem.x1)
        rightCenterX = model.NewIntVar(0, horizon.x, f"rightCenterX{currentDistanceId}")
        model.AddDivisionEquality(rightCenterX, rightCenterXSum, 2)

        rightCenterYSum = model.NewIntVar(0, horizon.y*2, f"rightCenterYSum{currentDistanceId}")
        model.Add(rightCenterYSum == rightItem.y2 + rightItem.y1)
        rightCenterY = model.NewIntVar(0, horizon.y, f"rightCenterY{currentDistanceId}")
        model.AddDivisionEquality(rightCenterY, rightCenterYSum, 2)

        # Create variable for difference of x
        xDiff = model.NewIntVar(-horizon.x, horizon.x, f"xDiff{currentDistanceId}")

        # Create constraint for difference of x
        model.Add(xDiff == rightCenterX - leftCenterX)

        # Create variable for difference of y
        yDiff = model.NewIntVar(-horizon.y, horizon.y, f"yDiff{currentDistanceId}")

        # Create constraint for difference for y
        model.Add(yDiff == rightCenterY - leftCenterY)

        # Create variables for x and y squared
        xDiffSquared = model.NewIntVar(0, horizon.x**2, f"xDiffSquared{currentDistanceId}")
        yDiffSquared = model.NewIntVar(0, horizon.y**2, f"yDiffSquared{currentDistanceId}")

        # Add constraint to multiply them
        model.AddMultiplicationEquality(xDiffSquared, [xDiff, xDiff])
        model.AddMultiplicationEquality(yDiffSquared, [yDiff, yDiff])

        totalDistance = model.NewIntVar(0, horizon.x**2 + horizon.y**2, f"totalDistance{currentDistanceId}")

        model.Add(totalDistance == xDiffSquared + yDiffSquared)

        distanceVariables.append(totalDistance)

        model.Add( totalDistance >= distanceSquared )
    else:
        print(f"Skipping distances between {listSet[0]} and {listSet[1]} because one is furniture")

Answer 1

而不是

Sqrt((x1-x2)^2 + (y1-y2)^2) >= d

你为什么不写信

(x1-x2)^2 + (y1-y2)^2 >= d^2

这是支持的。您将需要编写（伪代码）

IntVar t_x
Add(t_x == x1 - x2)
IntVar t_sx
AddMultiplicationEquality(t_sx, [t_x, t_x])

IntVar t_y
Add(t_y == y1 - y2)
IntVar t_sy
AddMultiplicationEquality(t_sy, [t_y, t_y])

Add(t_sx + t_sy >= d * d)