Целочисленная геометрия на плоскости

С.И.Хашин

igeom.h - заголовочный файл
igeom.cpp - реализация.

Координаты всех точек предполагаются целыми.

Если кому-то будут нужны точки с действительными координатами, то функции придётся переделывать. Однако для нужд компьютеной графики требуются именно целые точки.

В некоторых фукнциях координаты перемножаюся, поэтому они не должны превышать 40000.

Объекты

В этом модуле используются следующие объекты:

Pnt, Точка: массив из двух целых (x,y);
Edg, Отрезок: массив четырех целых (x0,y0)-(x1,y1) или пара точек (int *A, int *B)
Tri, Треугольник: массив 6 целых (x0,y0)-(x1,y1)-(x2,y2) или три точки (int *A, int *B, int *C)
Box, Четырехугольник: массив из 8 целых (x0,y0)-(x1,y1)-(x2,y2)-(x3,y3) или 4 точки (int *A, int *B, int *C, int *D)

Основные функции

Копирования объектов,
Перестановка точек,
Длина отрезка,
Нахождение оболочки, т.е. объемлющего прямоугольника,
Вычисление косинуса угла,
Сдвиг и поворот точки,
Уравнение прямой, проходящей через две точки,
Расстояние от точки до прямой,
Пересечение двух прямых, все возможные случаи,
Расстояние между отрезком и точкой,
Расстояние между двумя отрезками,
Для набора точек находим методом наименьших квадратов прямую, наиболее близ-кую к ним,
Будут ли точки (отрезки) почти совпадать?
Лежит ли точка в прямоугольном блоке?
Быстрая проверка того, что точки (отрезки) далеки друг от друга,
Из четырех точек строим отрезок,
Склеиваем два отрезка в один.
Пересечение отрезка с прямоугольным блоком,
Продлить отрезок в указанную сторону,
Проекция точки на отрезок,
Площадь треугольника,
Лежит ли точка внутри угла,
Лежит ли точка внутри треугольника,

Копирование:

void   copyPnt(int *src, int *dst);             // копирование точки
void   copyEdg(int *src, int *dst);             // копирование отрезка
void   copyEdg(int *A, int *B, int *dst);
void   copyTri(int *src, int *dst);             // копирование треугольника
void   copyTri(int *A, int *B, int *C, int *dst);
void   copyBox(int *src, int *dst);             // копирование 4-х угольника 
void   copyBox(int *A, int *B, int *C, int *D, int *dst);
void   swapE(int *edge);                        // переставить точки отрезка

Длина отрезка:

double lenE(int *edge);                     
double lenE(int x1, int y1, int x2, int y2);
double lenE(int *P0, int *P1);

Оболочка - прямоугольник:

void   envelEdg(int &minX, int &minY, int &maxX, int &maxY, int *edg);      // оболочка отрезка
void   envelSqu(int &minX, int &minY, int &maxX, int &maxY, int *di);       // оболочка квадрата с данной диагональю
void   envelEdg(int &minX, int &minY, int &maxX, int &maxY, int *A, int *B);// оболочка отрезка
void   envelTri(int &minX, int &minY, int &maxX, int &maxY, int *tri);      // оболочка треугольника
void   envelTri(int &minX, int &minY, int &maxX, int &maxY, int *A, int *B, int *C);
void   envelBox(int &minX, int &minY, int &maxX, int &maxY, int *box);      // оболочка 4-угольника
void   envelBox(int &minX, int &minY, int &maxX, int &maxY, int *A, int *B, int *C, int *D);

Углы:

double kAngle(int *edge);                       // угловой коэффициент ребра
//    / коэфф=-2
//   *
//    \ коэфф= 2


double CanglE(int x0, int y0, int x1, int y1);  // косинус угла между векторами
double CanglE(int *A, int *B, int *C);          // косинус угла ABC
double CanglE(int *edge1, int *edge2);          // косинус угла между отрезками (векторами)
double CanglE(int *A, int *B, int *C, int *D);  // косинус угла между лучами [AB) и [CD)
void   CSanglE(int x0, int y0, int x1, int y1, double &co, double &si );// co:=cos(angle), si:=sin(angle) 
void   TransfE(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3, 
            double &a0, double &a1, double &co, double &si);
            // найти преобразование, переводящще [01]->[23]

Функция TransfE находит аффинное преобразование вида (растяжение+поворот+сдвиг)

    x' = a0 + co*x + si*y
    y' = a1 - si*x + co*y

переводящее точки (x0,y0), (x1,y1) в (x2,y2), (x3,y3) соответственно.

Повороты и сдвиги:

void   rotate(int *A, int *B, int *C, double angle);
        // C:=поворот(B) вокруг A на угол angle

void   rotate(int Ax, int Ay, int Bx, int By, int &Cx, int &Cy, double angle);
        // C:=поворот(B) вокруг A на угол angle

void   shiftE(int *A, int *B, int h, int *C, int *D);
        // [CD] := сдвиг [AB] на расстояние h влево вдоль [AB]

void   shiftE(int x0, int y0, int x1, int y1, int h, int &x2, int &y2, int& x3, int &y3);
        // [(x2,y2)(x3,y3)] := сдвиг [(x0,y0)(x1,y1)] на расстояние h влево вдоль [(x0,y0)(x1,y1)]

Прямые:

void   lineEq(int *edge, double &a, double &b, double &c);       // уравнение прямой ax+by+c проходящей через отрезок
// 1. Если точки совпадают, то a=b=c=0
// 2. Уравнение нормализовано, т.е. a*a+b*b=1

void   lineEq(int *P0, int *P1, double &a, double &b, double &c);// уравнение прямой ax+by+c проходящей через отрезок
double lineDist(int *edge, int *P);             // расстояние от точки P до прямой, содержащей отрезок
double lineDist(int *A, int *B, int *P);        // расстояние от точки P до прямой, содержащей отрезок [A,B]

Пересечение прямых:

// Возвращает:
// 0 - прямые параллельны,
// 1 - пересекаются за пределами отрезков,
// 2 - точка пересечения принадлежит ВНУТРЕННОСТИ отрезка edge1
// 3 - точка пересечения принадлежит ВНУТРЕННОСТИ отрезка edge2
// 4 - точка пересечения принадлежит ВНУТРЕННОСТЯМ обоих отрезков
int    intersection(int *edge1, int *edge2, double &x, double &y);  
        // (x,y):=точка пересечения прямых, проходящих через отрезок

int    intersection(int *A, int *B, int *C, int *D, double &x, double &y);  
        // (x,y):=точка пересечения прямых (AB), (CD)

Расстояния

double distE0(int *edge, double x, double y);   
        // Расстояние между отрезком и точкой

double distE(int *edge1, int *edge2);           
        // Расстояние между отрезками. Равно 0, если отрезки пересекаются

Прямая, почти проходящая через данные точки

double fndLine(int N, const int *v, double &a, double &b, double &c);

Даны N>1 точек на плоскости ,...,. Методом наименьших квадратов найти прямую a*x+b*y+c=0 приближающуюся к ним.

Будут ли точки/отрезки близки?

bool   SameP(int *p1, int *p2);                 // будут ли точки совпадать?
bool   SameE(int *p1, int *p2);                 // будут ли отрезки совпадать?
bool   almostSameP(int *p1, int *p2, int h = 1);// будут ли точки почти совпадать?
bool   almostSameE(int *p1, int *p2, int h = 1);// будут ли отрезки почти совпадать?

"Почти" совпадение определяется величиной h, точки "почти" совпадают, если расстояние между ними меньше h. Не забываем, что отрезок [A,B] совпадает с [B,A].

Продолжение темы:

bool   isIn(int x0, int y0, int x1, int y1, int x, int y );
        // лежит ли точка (x,y) в блоке <(x0,y0)-(x1,y1)>

bool   edgFar(int *A, int *B, int *C, int *D, int h);
        // отрезки [AB] и [CD] далеко (h) друго от друга? Быстрая проверка

bool   edgFar(int *e1, int *e2, int h);         
        // отрезки e1 и e2 далеко (h) друго от друга? Быстрая проверка

Проверка возможности объединить отрезки:

double joinE(int *A, int *B, int *C, int *D, int *join);    
        // из 4-х точек отрезок, возвращает макс. отклонение от отрезка

double joinE(int *e1, int *e2, int *join);      
        // join:=склейка(e1,e2), возвращает макс. отклонение e1,e2 от нового отрезка

Увеличение/уменьшение/объединение отрезков:

bool   reduceTo(int *edge, int x0, int y0, int x1, int y1);
        // пересечение edge с блоком <(x0,y0)-(x1,y1)>

void   expandEdg(int *A, int *B, int h);
        // расширить отрезок [A,B] от стороны B на h точек
void   expandEdg(int x0, int y0, int &x1, int &y1, double q);
        // расширить отрезок [01] от стороны 1 в q раз

double edgProj( int *A, int *B, int *P);
        // x: проекция(P) на линию (AB) равна x*A +(1-x)*B 

bool   edgAdd( int *e1, int *e2, int h1, int h2);
        // к отрезку e1 добавить отрезок e2 (если они объединяются с точностью до h1, h2)

Треугольники:

double areaT(int*A, int *B, int *C);    
        // ориентированная площадь треугольника ABC

int    areaT2(int*A, int *B, int *C);   
        // 2*ориентированная площадь треугольника ABC

bool   inAngle(int *A, int *B, int *C, int *P);
        // точка P внутри угла ABC?

bool   inTriangle(int x1, int y1, int x2, int y2, int x3, int y3);
        // точка (0,0) внутри треугольника?

bool   inTriangle(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y);
        // точка (x,y) внутри треугольника?

bool   inTriangle(int *P1, int *P2, int *P3, int *P);
        // точка (P,P+1) внутри треугольника (P1,P1+1),(P2,P2+1),(P3,P3+1)?

Боксом (box) будем здесь называть 4-х угольник. Он будет представлять собой массив из 8 целых чисел или набор из четырех точек (вершин).

bool   makeBox(int *A, int *B,int *C,int *D,int *box);// из 4-х точек построить выпуклый 4-угольник. 
double CangleB(int *box, int k);                      // косинус угла при k-й вершине
double lenB(int *box, int k);                         // длина от k-й вершины до k+1
double areaB(int *box);                               // площадь
double areaB(int *A, int *B, int *C, int *D);         // площадь ABCD
bool   convex(int *A, int *B, int *C, int *D);        // выпуклый?
bool   convex(int *box);                              // выпуклый?
void   shiftB(int *box);                              // сдвиг вершин по часовой стрелке
void   boxLengthM(int *box, double &min, double &max);// самая короткая и самая длинная сторона
void   boxCAngleM(int *box, double &min, double &max);// самый большой и маленький косинус угла
void   boxCenter(int *box, int &x, int &y);           // (x,y):=центр(box)
void   shrink(int *src, int *dst, int h);             // dst:=сжать box(src) на h точек к центру
bool   inBox(int *box, int *P);                       // точка P лежит в боксе?
bool   InBox(int *box, int x, int y);                 // лежит ли точка (x,y) внутри box

Дополнительный объект: квадрат (может косо лежать), задается главной диагональю.

void   secondDiag(int *d1, int *d2);        
        // дана диагональ квадрата d1, находим вторую диагональ d2

void   getDiag(int *s, int *d);
        // дана средняя линия квадрата s, находим диагональ d

void   getDiag(int xa, int ya, int xc, int yc, int &x0, int &y0, int &x1, int &y1);
bool   almostSameSq(int *d1, int *d2);
        // даны диагонали двух квадратов. Эти квадраты почти одинаковы?

К оглавлению