How to determine intercession between polygons?

Question

How to determine a C polygon that is intersection of A and B in C ?

#include "TPoligono.h"
#include <stdlib.h>
#include <stdio.h>

TPoligono *criaPoligono()
{
    int i;  
    TPoligono *pol = (TPoligono *) malloc(sizeof(TPoligono));
    for(i=0;i<3;i++) {
        TPonto *q;
        q = criaPonto();
        pol->vertice[i] = q;
    }
    pol->tam=3;
    printf("Poligono criado com sucesso\n");        
    return pol;
}

void inserePonto(TPoligono *pol, TPonto *p)
{
    printf("Inserindo ponto\n");
    //acha fim do vetor de vertices


    pol->vertice[pol->tam] = p;

    pol->tam++;
    //coloca NULL na posicao seguinte pra mostrar que era o ultimo vertice
    return;
}

void removePonto(TPoligono *pol, int posic)
{    
    if (pol->tam == 3) {
        printf("Nao posso remover\n");
        return;
    }

    free(pol->vertice[posic]);
    pol->tam--;
    pol->vertice[posic] = pol->vertice[pol->tam];
}

Answer 1

I think it’s reasonable to assume that the polygons in question are convex polygons. If one of the polygons is concave, the intersection can be a multiplicity of polygons:

Before we begin to address the intersection of polygons, we need to address some issues that are requirements:

1. geometric concepts
2. vector operations
3. relevance from point to segment
4. intersection between lines
5. intersection between straight segments
6. point relevance to the internal area of triangle
7. convex wrap

With the exception of vector product (which requires 3D geometry), all the rest will be set around flat geometry.

Geometric concepts

The following geometric concepts are of extreme importance for the present case:

1. dot
2. origin
3. vector
4. straight
5. semirreta
6. line segment

Dot

In a plane, a dot is an entity per se that exists in the plane. A point is identified in the plane by two coordinates:

Origin

To origin is a particular point:

Vector

A vector is an entity that indicates the difference between two points. Be a vector the difference between and :

Like and are real numbers, we have to, in a generic way:

Every vector has, in itself, three properties that define them:

1. module
2. direction
3. sense

The module is the vector size.

The direction is the angle that the vector makes with the axis .

The direction is to which "side" of the angle the vector is pointing.

An array can be operated with real numbers, with other vectors, and with points, as seen in the next section.

Every point has its vector equivalent if we take your difference with the source:

Straight

The line is between a point and all multiples of a vector:

The direction of the line is given by the same direction of the vector that composes it.

Rewriting the above formula:

For the case of the direction of the straight line is non-vertical, its equation becomes:

In the case of straight line direction is vertical:

As a line is composed by a point and a vector, it is possible to compose it also through two points.

Semirreta

A semirreta is very similar to a straight line, but it only extends in the direction of the vector, never in the opposite direction.

As a semirreta is composed of a point and a vector, it is possible to compose it also through two points. Unlike the line where the direction of the vector does not matter, the choice of the base point is crucial.

Line segment

A line segment is a continuous finite part of a line. A line segment is always bounded by two points.

A segment between points and is the intersection between two opposite-way semirretas: the semirreta of sense and the Semirreta de sense . This interpretation will be crucial later.

Operations with vectors

I will summarize to the following operations with vectors:

1. vector multiples
2. vector with dot
3. vector added to vector
4. scalar product
5. vector product with vectors in the plane

Vector multiples

This is an operation between a real number and a vector, resulting in a vector. This operation results in a new vector in the same direction as the previous vector, but may have its module changed and its direction reversed.

If a negative number is used, the direction of the vector will be changed. Therefore, .

Every non-unitary number will change the vector module. If you want a vector half the size, you must multiply by 0.5; to double the size, multiply by 2.

Vector with dot

The addition of a vector to a point returns a point. Coming directly from the definition of vector.

Vector added to vector

By composing two vectors, we obtain a third vector:

It is also derived from the definition of vector.

Scalar product

This operation transforms two vectors into a real number. More details for generalized scalar product operations in this Wikipedia article.

The scalar product, in two dimensions, is given by:

An interesting fact is that the scalar product is directly proportional to the cosine of the direction difference angle. If the scalar product is negative, this means that the angle between the two vectors is obtuse; if the product is zero, the angle is right; if positive, it is acute.

Vector product with vectors in the XY plane

The vector product is an operation between two vectors that returns a new vector perpendicular to the two operands. It only exists in 3 dimensions, see this article from Wikipedia for more details.

The plan , in a three-dimensional space, it is given by the set of points at which the is 0. Therefore, at any time I can abstract that we are dealing with flat geometry for spatial geometry by doing the trick of adding an ordinate with value 0 to any point (or vector).

In this case, we use the vector product to define in which hand is the operation of two vectors. If we do the following operation:

result in a vector pointing upwards on the axis . In this case, the operation is right-handed. By reversing the order of the products into a vector product, the result has its hand reversed, but retains direction and module. In this case, the result would point downwards, thus being an operation left-handed.

The formula for the vector product, in these circumstances of plane vectors , is given by:

Relevance from point to segment

Be a point pertinent to the straight line . How to know if belongs to the segment ?

One of the possible solutions to this dilemma is the question about the relevance of the point to a semirreta. Through the concepts previously presented, if the point belongs to the semirreta and the Semirreta , then it belongs to the segment .

Next, I will answer the question belonging to the Semirreta ?. To know about the segment, just do also the analogue for the semirreta .

Between 3 points on the same line, there are only 2 possibilities of the angle value between them:

1. 0°
2. 180°

If is 0°, this means that and are in the same direction as the , therefore belongs to the Semirreta . Otherwise, if is in the opposite direction to , the angle shall be 180°.

Yeah, but so what? How does that help?

Simple. With vectors and scalar product.

Take the scalar product . If the result is positive, this means that the angle is acute, so 0°; if negative, then the angle is 180°.

Hence, if is positive, then belongs to the Semirreta .

Intersection between straight lines

Two straight lines may have one of the possible three relationships in a plan:

1. they can be coincidental;
2. they can be parallel noncoincident;
3. they may be competitors.

If they are coincident, they have the same equation as the line, so they have infinite points of coincidence:

If they are parallel, we have the same tilt factor, but it has a distinct offset:

And then, for straight contestants:

We are interested now only in the case of straight competitors, straight lines that intersect in only one point. If one of the lines is vertical, the value of of the meeting point, then one can find the value of using the parameter to the other straight.

If both lines are non-vertical, they will intersect at one point. To determine what that point is:

Calculate the value of then becomes trivial now.

Intersection between straight segments

Basically here, just calculate the intersection of the lines that make up the segments and check if the point found belongs to both segments.

Point relevance to the internal area of a triangle

Given the triangle , wonder if is contained in the internal area of .

If is in the opposite hand to concerning , then is outside the triangle. One sees this easily using vector product: must have the same sign as .

One of the ways to ensure that is inside the triangle to make sure he’s not outside. To make sure he’s not out, you need to check his hand against not only as spoken above, but also to and the .

Convex wrap

The convex wrap of a set of points is the smallest convex polygon that contains all the desired points. For more details, see this article from Wikipedia.

There is an algorithm proposal that I think is worth talking about right here, since it is important for the answer.

Be it the initial point of the convex wrap. To choose , take the leftmost point (with the lowest possible value in ).

Be it the next point of the wrap. To escollher , ensure that, for any point that does not belong to the points already included in the wrap, be right-handed in relation to and . That is to say, needs to be right-handed.

When it is no longer possible to select a new one , we finish the convex wrap and the vertices of the wrap will be in order.

Solving the problem

Take for example the intersection below:

What is the intersection between the blue and black polygon?

To know this answer, it is necessary to find all the points of the polygons that are contained within the other polygon (shown in the image inside red rectangles) and what are the intersections between the segments of the two polygons (shown in image inside red ellipses). These two sets of points are the vertices of the intersection polygon.

Besides knowing which are the vertices, it is necessary to order them. For this, detect which the convex wrap of these points.