jonyrock/aptucompgeometry

aptucompgeometry's Issues

ДОбавить пач от Андрея

diff --git a/headers/algorithms.h b/headers/algorithms.h
index 322e132..30ff8d3 100644
--- a/headers/algorithms.h
+++ b/headers/algorithms.h
@@ -10,6 +10,8 @@ using namespace std;

 namespace geom {
     namespace algorithms {
+
+        using namespace geom::structures;

         // return true if polygon was oriented clockwise
         int left_turn(point_type a, point_type b, point_type c);
diff --git a/src/algorithms.cpp b/src/algorithms.cpp
index ee7668e..916d715 100644
--- a/src/algorithms.cpp
+++ b/src/algorithms.cpp
@@ -6,7 +6,11 @@
 #include <math.h>
 #include <stack>

-using namespace geom::algorithms;
+#include "io/point.h"
+
+namespace geom {
+namespace algorithms {
+
 // return true if polygon was oriented clockwise

 int left_turn(point_type a, point_type b, point_type c) {
@@ -22,22 +26,21 @@ int left_turn(const segment_type& segment, point_type p) {

 bool point_on_line(const point_type& point, const segment_type& segment) {
     if (left_turn(segment, point) != 0) return false;
-    if (point.x < min(segment[0].x, segment[1].x)) return false;
-    if (point.x > max(segment[0].x, segment[1].x)) return false;
-    if (point.y < min(segment[0].y, segment[1].y)) return false;
-    if (point.y > max(segment[0].y, segment[1].y)) return false;
+    if (point.x < std::min(segment[0].x, segment[1].x)) return false;
+    if (point.x > std::max(segment[0].x, segment[1].x)) return false;
+    if (point.y < std::min(segment[0].y, segment[1].y)) return false;
+    if (point.y > std::max(segment[0].y, segment[1].y)) return false;
     return true;
 }

 bool segments_intersected(const segment_type& a, const segment_type& b) {
-
-    if (max(a[0].x, a[1].x) < min(b[0].x, b[1].x))
+    if (std::max(a[0].x, a[1].x) < std::min(b[0].x, b[1].x))
         return false;
-    if (max(b[0].x, b[1].x) < min(a[0].x, a[1].x))
+    if (std::max(b[0].x, b[1].x) < std::min(a[0].x, a[1].x))
         return false;
-    if (max(a[0].y, a[1].y) < min(b[0].y, b[1].y))
+    if (std::max(a[0].y, a[1].y) < std::min(b[0].y, b[1].y))
         return false;
-    if (max(b[0].y, b[1].y) < min(a[0].y, a[1].y))
+    if (std::max(b[0].y, b[1].y) < std::min(a[0].y, a[1].y))
         return false;

     int res1 = left_turn(a[0], a[1], b[0]);
@@ -168,3 +171,4 @@ void triangulate_monotonous(const vector<point_type>& pts_, vector<segment_type>

 }

+}}
diff --git a/visualization b/visualization
index 88da7d3..79712da 160000
--- a/visualization
+++ b/visualization
@@ -1 +1 @@
-Subproject commit 88da7d3777c3c6cacd7133537ad084242fa8a6ba
+Subproject commit 79712da6d53f89b8b66ef60adb84aa9807bdc8ea

Триангуляция впуклостей

(-72, 174)
(-109, 185)
(-156, 147)
(-177, 133)
(-201, 121)
(-225, 104)
(-260, 80)
(-293, 31)
(-299, -36)
(-285, -50)
(-265, -57)
(-222, -72)
(-202, -80)
(-43, -147)
(86, -193)
(88, -177)
(89, -133)
(89, -67)
(89, 9)
(89, 130)

вот это рашит вуклость сверху слева
и повилась диагонал на ребре

Порядок вертикальный линий

(125, -157)
(169, -75)
(193, 54)
(255, 74)
(305, 125)
(301, 162)
(294, 204)
(281, 229)
(234, 188)
(197, 153)
(173, 162)
(173, 203)
(147, 203)

косяк...

Потенциальный баг

Может получиться так, что вершины будут иметь одинаковую координату y и тогда не понятно как ее делать: regular, start или еще что ...

Выбитый split

19
(-33, 160)
(-165, 102)
(-60, 68)
(-174, -4)
(-39, -32)
(-143, -150)
(-13, -47)
(40, -154)
(102, -43)
(189, -160)
(264, -50)
(152, -16)
(250, 22)
(145, 59)
(248, 107)
(148, 143)
(257, 184)
(154, 231)
(52, 107)
5
(-13, 20)
(14, 76)
(61, 46)
(99, 84)
(125, 13)

Пофиксить readme

Весь процесс ввода дырок. Скачать что отрезок дорисуется.
Ну и что проверяются пересечения дырок и внутри ли они лежат

Algorithms в cpp

Я все написал как-то в хедер по-старинке

РСДС

У меня не получиться правильно порезать полигон пока я не предаставлю его как РСДС.

Умные тесты для дырок

Есть более идейный тест, который объединяет проверку:

а) лежит ли следующая точка дырки снаружи или внутри полигона
б) пересекается ли следующая дырка с предыдущими

Для этого нужно проверить, что каждая точка новой дырки лежит внутри полигона, притом рассматривая ближайший отрезок, который она пересекает.
Т.е. если это дырка, то закрутка по часовой стрелке, а если полигон - то против. И там и там должно выполняться, что луч от точки должен образовывать левый поворот с ближайшим отрезко, который она пересекла.

Одинокий merge

16
(317, 241)
(-171, -70)
(-164, -167)
(390, 201)
(427, 288)
(487, 505)
(147, 629)
(-315, 599)
(-312, 415)
(-231, 489)
(-17, 391)
(-38, 216)
(-107, 187)
(-258, 129)
(-180, -39)
(50, 185)

случай, когда merge вершина остается без друга

Запрет триангуляции плохого полигона

Запретить действия и в GUI

Ввод дырок пользователем

• Сделать специальный новый режим для этого.
• Завести новые структуры данных.
• Сделать специальный формат файлов
• Протестировать сохранение и загрузку файлов
• Протестировать возможность включения режима ввода дырок
• Проверить пересечения самих дырок
• Проверить, что дырка внури полигона

Удивительный баг вызова legend_pnt()

Почемуто происзодит segmentation fault если вызывать get_legend_pnt(), добавляя новыйц вектор в app_viewer

Пометить вершины

• Написать саму процедуру выбора типа вершины
• Отрисовать разные типы вершин

Оставшиеся диагонали

Посе перезагрузки полигона после триангуляции они остаются

Сам алгоритм триангуляции немнототонного полигона

Вот я и подобрался к содержательной части этой программы. Позравляю тебя @jonyrock.

• Подготовить данные для заметающей прямой
• Написать алгоритм заметающей прямой
• Случай с дырками
• Вытащать из этого монотонные полигоны

Мердж отсортированных цепей в один массив

На самом деле нижняя цепь отсортированна по возрастанию сева направо, а верхняя наоборот. Получается, что нужно просто смерджить два отсортированных массива в один, а не скидывать все точки, а потом сортировать.

Перебрать краевые случаи

Я еще сам не знаю точно, нужно пока просто перечислить и найти баги в случаях типа:

• Дырка касается полигона
• Дырка имеют общую точку
• Несколько дырок касаются полигона в одной точке

Легенда для типов вершин

Отобразить где-то как я помечаю вершины в видел легенды. Кстати у меня там еще как-то странно все едет, если делается перетасиквание полигона мышкой.

Вызов триангуляции

После начала работы с #8 отвался вызов триангуляции