如何测试线段是否与二维中的轴对齐矩形相交? [英] How to test if a line segment intersects an axis-aligned rectange in 2D?

问题描述

如何测试线段是否与二维中的轴对齐矩形相交?该段由其两端定义:p1，p2.矩形由左上角和右下角定义.

How to test if a line segment intersects an axis-aligned rectange in 2D? The segment is defined with its two ends: p1, p2. The rectangle is defined with top-left and bottom-right points.

推荐答案

原海报想检测线段和多边形之间的交点.没有必要找到交叉口，如果有的话.如果这就是你的意思，你可以做的工作比 Liang-Barsky 或 Cohen-Sutherland 少:

The original poster wanted to DETECT an intersection between a line segment and a polygon. There was no need to LOCATE the intersection, if there is one. If that's how you meant it, you can do less work than Liang-Barsky or Cohen-Sutherland:

令线段端点为 p1=(x1 y1) 和 p2=(x2 y2).
设矩形的角为 (xBL yBL) 和 (xTR yTR).

Let the segment endpoints be p1=(x1 y1) and p2=(x2 y2).
Let the rectangle's corners be (xBL yBL) and (xTR yTR).

那么你要做的就是

A.检查矩形的所有四个角是否都在直线的同一侧.通过 p1 和 p2 的直线的隐式方程为:

A. Check if all four corners of the rectangle are on the same side of the line. The implicit equation for a line through p1 and p2 is:

F(x y) = (y2-y1)*x + (x1-x2)*y + (x2*y1-x1*y2)

F(x y) = (y2-y1)*x + (x1-x2)*y + (x2*y1-x1*y2)

如果 F(x y) = 0，则 (x y) 在线.
如果 F(x y) > 0，则 (x y) 位于该线的上方".
如果 F(x y) <0, (x y) 位于该行的下方".

If F(x y) = 0, (x y) is ON the line.
If F(x y) > 0, (x y) is "above" the line.
If F(x y) < 0, (x y) is "below" the line.

将所有四个角都代入 F(x y).如果它们都是负面的或都是正面的，那么就没有交集.如果有些是正面的，有些是负面的，请转到步骤 B.

Substitute all four corners into F(x y). If they're all negative or all positive, there is no intersection. If some are positive and some negative, go to step B.

B.将端点投影到 x 轴上，并检查线段的阴影是否与多边形的阴影相交.在 y 轴上重复:

B. Project the endpoint onto the x axis, and check if the segment's shadow intersects the polygon's shadow. Repeat on the y axis:

如果 (x1 > xTR 和 x2 > xTR)，则没有交点(直线在矩形的右侧).
如果 (x1 如果(y1 > yTR 和 y2 > yTR)，则没有交点(直线在矩形上方).
如果(y1 否则，有一个交叉点.做 Cohen-Sutherland 或您问题的其他答案中提到的任何代码.

If (x1 > xTR and x2 > xTR), no intersection (line is to right of rectangle).
If (x1 < xBL and x2 < xBL), no intersection (line is to left of rectangle).
If (y1 > yTR and y2 > yTR), no intersection (line is above rectangle).
If (y1 < yBL and y2 < yBL), no intersection (line is below rectangle).
else, there is an intersection. Do Cohen-Sutherland or whatever code was mentioned in the other answers to your question.

当然，你可以先做 B，然后做 A.

You can, of course, do B first, then A.

阿莱霍

这篇关于如何测试线段是否与二维中的轴对齐矩形相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！