Category Archives: Geometry

Basis geometry

Area 3D polygon on a plane

Leave a reply

    static public double getSignedArea(List points, XYZ normal)
    {
        int nPoints = points.Count;

        XYZ sum = XYZ.Zero;
        for (int index = 1; index < nPoints; index++)
        {
            sum += points[index].CrossProduct(points[index - 1]);
        }
        sum += points[0].CrossProduct(points[nPoints - 1]); 

        double area = normal.DotProduct(sum);
        return -0.5 * area;
    }

To calculate the area of a 3D polygon on a plane. the normal is the plane’s normal.

Determine whether a point is above or below a vector (2D)

Leave a reply

Determine whether point P is above or below a vector through points A, B

Point above vector

$z = (B_x - A_x) (P_y - A_y) - (B_y - A_y) (P_x - A_x)$

Possible values for $z$ :

0 On the vector

> 0 Above the vector

< 0 Below the vector

The function above is the ‘2D cross product’, therefore z is the surface of vector $\overline{AB}$ and $\overline{AP}$ . Dividing the surface by the length of vector $\overline{AB}$ ( $\vert \overline{AB}\vert$ ) gives the ‘signed distance’ of the point perpendicular to the point $P$ .

Get the distance between a point and vector (2D)

Leave a reply

Determine the distance of point P and vector through points P1, P2

Distance point – vector

$dist = \dfrac{\left | (B_x - A_x) (P_y - A_y) - (B_y - A_y) (P_x - A_x) \right |}{||\overline{AB}||}$

This is a ‘2D cross product’ of $\overline{AB}$ and $\overline{AP}$ . Since the cross product is the parallelogram surface of the two vectors, dividing it by the length of $\overline{AB}$ to get the distance.

$\left\|\overline{AB}\right\| = \sqrt{(B_x - A_x)^2 + (B_y - A_y)^2}$

Calculate a point at a distance perpendicular to a vector offset (2D)

Leave a reply

To calculate a point at a distance perpendicular to a vector offset

Point perpendicular to offset

First the point on the vector $P'$ at the required offset needs to be calculated. This easy to do:

$P' = A + (B-A) * offset$

$P'_x = A_x + (B_x - A_x) * offset$
$P'_y = A_y + (B_y - A_y) * offset$

The vector to move the point P’ on is perpendicular to $\overline{AB}$ . This vector can be calculated using a 90 degree rotation matrix:

The matrix shows in the the first row $x'= -y$ and the second row shows $y'= x$

You can safely ignore the stuff above if you are only interested in getting the job done. The final formula is:

$\begin{pmatrix}x'\\y' \end{pmatrix}= \begin{pmatrix}-y\\x \end{pmatrix}$

We will call the vector ( $\overline{P'P}$ ) vector $C$ .

$C =\begin{pmatrix}- (B_y - A_y)\\ B_x - A_x \end{pmatrix}$

Vector $C$ needs to be normalized (divided by it’s length / magnitude).

$\hat{C} =\dfrac{C}{\left \|C \right \|}$

The resulting formula becomes:

$P = (A + (B-A) * offset) + \hat {C} * distance$

A positive distance will get the point above the vector, a negative below the vector.

Get point relative to another point with offset and angle (2D)

Leave a reply

To find a point relative to a point ${O}$ at a distance $length$ at angle $\alpha$ .

Image

$P_x = O_x + cos(\alpha) * length$
$P_y = O_y + sin(\alpha) * length$

Check whether two 2D lines are coincident.

Leave a reply

To check whether two 2D lines are coincident, the distance of $C$ and $D$ to $AB$ need to be calculated. For a coincident line both need to be (almost) zero.

The z component of the cross vector can be used for this quite elegantly.

Note: The cross vector is noted as an x e.g. $A$ x $B$

To check whether the two lines $AB$ and $CD$ are coincident, the z-component of two cross vectors need to be calculated. Both calculate the distance of the points on line $CD$ to $AB$ .

$AB$ x $AC$ is the area of the parallelogram $AB AC$ , dividing it with the length of $AB$ ( $|AB|$ ) gives the shortest distance of point $C$ to line $AB$ .

$AB$ x $AD$ gives the area of the parallelogram $AB AD$

After dividing with $|AB|$ this is also the shortest distance of $D$ to line $AB$ . If both distances are small enough the lines are coincident.

$dist_{abc} = \overline{AB}_x·\overline{AC}_y - \overline{AB}_y·\overline{AC}_x$
$dist_{abd} = \overline{AB}_x·\overline{AD}_y - \overline{AB}_y·\overline{AD}_x$

Check whether two 2d direction vectors are parallel

Leave a reply

The cross product of two parallel direction vectors has zero length. The magnitude (length) of the cross product is the area enclosed by the vectors. Two parallel direction vectors obviously do not have a surface since they can be considered the same origin.

In 2D the z axis is the normal to the x and y axis. The z-axis is calculated by using the cross vector of both vectors.

The cross vector Z-component can be calculated using:
$z = A_x B_y - A_y B_x$

if $z$ is very small, the vectors are parallel.

2D Line intersection using vectors

Leave a reply

In this note I will explain how to find the intersection point P between two line segments. Note that this method will also calculate intersections on extended line segments.

As a reminder the cross product is the area of the parallelogram enclosed by the two As a reminder, the cross product is the area of the parallelogram enclosed by the two vectors. In 2D graphics, we will calculate only the z-component of the cross-vector, which will be called the cross-product in this note.

It can be calculated using the following formula:

$a\times b = a_x b_y - a_y b_x$

Calculating the actual intersection:

As an example we will calculate the intersection point $P$ of line segments $AB$ and $CD$ as shown in image 1.

Image 1

We will consider the line segments as vectors, this gives us the following vectors.

$AB =\begin{pmatrix}6\\3\end{pmatrix}$ , $CD =\begin{pmatrix}-4\\4\end{pmatrix}$

To calculate the intersection point we will first calculate the area of the parallelogram formed by AB and CD as shown in image 2.

Image 2

The area can be calculated using the cross product of $AB \times CD$

$AB\times CD = \begin{pmatrix}6\\3\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (6.4)-(-4.3) = 24-(-12) = 36$

Calculating the offset on segment $CD$

We will now calculate the area below vector $AB$ as seen in image 3

Image 3

It can be seen the offset on segment on $CD$ will be equal to this area divided by the total area calculated earlier. Fortunately we can easily calculate the area by using the area shown in image 4.

Image 4

The areas shown in image 3 and image 4 are the same. Note that image 4 shows the parallelogram formed by $AC$ and $AB$ , we will use the cross-product to calculate it.

We will introduce vector $AC$ for this.

$AC =\begin{pmatrix}7-2\\3-2\end{pmatrix} = \begin{pmatrix}5\\1\end{pmatrix}$

$AC\times AB = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}6\\3\end{pmatrix} = (5.3)-(1.6) = 15-6 = 9$

Now we are almost done. We have both areas (9 and 36) so we can create the offset

$offset = \frac{9}{36}CD$ which can be simplified to $offset = \frac{1}{4}$

If we multiply the offset with $CD$ we find the point on the vector $CD$ .

Since the line segment $CD$ does not start on $\begin{pmatrix}0\\0\end{pmatrix}$ the actual point needs to be moved by $C$

$P = C + \frac{1}{4}CD$

Let’s check whether it is correct

$P = C + \frac{1}{4}CD = \begin{pmatrix}7\\3\end{pmatrix} + \begin{pmatrix} \frac{1}{4}(-4)\\ \frac{1}{4}4\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}$

As a general formula:

$\boxed{P = C + \frac{AC\times AB}{AB \times CD}CD}$

The offset on $CD$ can be negative or larger then one. In that case the intersection is on the extension of line segment $CD$ . This is an advantage of this method.

Calculating the offset on segment $AB$

For the offset of $P$ on $AB$ we repeat the steps above.

We know calculate the area as shown at image 5

Image 5

Which equals the area shown in image 6.

Image 6

$AC\times CD = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (5.4)-(1.-4) = 20-(-4) =24$

$P = A + \frac{24}{36}AB \to P = A + \frac{2}{3}AB$

Let’s check whether it is correct

$P = A + \frac{2}{3}AB = \begin{pmatrix}2\\2\end{pmatrix} + \begin{pmatrix} \frac{2}{3}(6)\\ \frac{2}{3}3\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}$

As a general formula:

$\boxed{P = A + \frac{AC\times CD}{AB \times CD}AB}$

Find out where a vector intersects a horizontal (or vertical) line

Leave a reply

Of course the line intersection method can be used but in case of horizontal or vertical lines a quicker solution is available.

Assume the vector V1 defined by points P1 and P2. and the horizontal line is through point P

The offset of the intersection is:

Lets say P1 is 10,10 P2 20,20 and P.y 0,15

In this case (15-10)/(20-10) is 0.5

If P1 and P2 is revered it will be (15-20)/(10-20) = -5/-10 = 0.5.

Note:
There is a special case if the vector is parallel or on the horizontal line, in that case, there is no intersection. In that case, p2.y – p1y is zero. This situation must be checked since it will also prevent a division by zero. You probably also want to limit very small values of this value since it may result in very large (positive or negatively) offset values.

Vertical lines:
In case of a vertical line replace all .y above by x.

Calculating the intersection point:
The offset when the vector is hit is always >= 0.0 and <= 1.0, otherwise, it is on the extended vector.

Calculating the intersection point on the(extended) vector is trivial

Get a vector perpendicular to another vector

Leave a reply

Get a vector perpendicular to another vector

Assume the vector is defined by two points P1 P2

$dx = p2_x - p1_x dy = p2_y - p1_y$

$p3_x = p1_x - dyp3_y = p1_y + dx$

Or in the other direction

$p4_x = p1_x + dyp4_y = p1_y - dx$

Developer notes

Stuff I need to remember

Category Archives: Geometry

Area 3D polygon on a plane

Determine whether a point is above or below a vector (2D)

Get the distance between a point and vector (2D)

Calculate a point at a distance perpendicular to a vector offset (2D)

Get point relative to another point with offset and angle (2D)

Check whether two 2D lines are coincident.

Check whether two 2d direction vectors are parallel

2D Line intersection using vectors

Find out where a vector intersects a horizontal (or vertical) line

Get a vector perpendicular to another vector