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

问题描述

如何测试线段是否与 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 and x2 > xTR)，则没有交集(直线在矩形的右侧).
如果 (x1 < xBL and x2 < xBL)，则没有交点(线在矩形的左边).
如果 (y1 > yTR and y2 > yTR)，则没有交点(线在矩形上方).
如果 (y1 < yBL and y2 < yBL)，则无交集(线在矩形下方).
否则，有一个交叉点.做 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.

阿莱乔

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