Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Разделить треугольник на два контура по линии разреза

Разделить треугольник на два контура по линии разреза
Я
   DTX 4th
 
18.11.18 - 21:33
Дано:
Vector2 p1, p2, p3; - три точки треугольника
Vector2[] slice; - точки разреза (начало и конец принадлежат сторонам треугольника)

Получить:
Два контура, которые образуются в результате деления треугольника с помощью линии разреза.

Пример:
https://i.imgur.com/aBZ8dIj.png
Тут 5 точек разреза.
Голубым обозначил два выходных массива точек.

Возможен и такой вариант:
https://i.imgur.com/xf4t8Vz.png
 
 
   RomanYS
 
1 - 18.11.18 - 21:56
А в чём вопрос?
Берешь линию разреза как начало для обоих контуров, а дальше по часовой /против часовой. Для треугольника всего два варианта и ты их оба нарисовал.
   DTX 4th
 
2 - 18.11.18 - 22:01
(1) Как это закодить? Понятное дело, что нарисовать легко.
   RomanYS
 
3 - 18.11.18 - 22:05
(2) определить на каких сторонах концы разреза, добавить вершины исходного треугольника к разрезам(или 1+2(первый рисунок) или 0+3(второй))
   DTX 4th
 
4 - 18.11.18 - 22:13
(3) Хм, может сработать. Отпишусь, если получится провернуть
   jscript82
 
5 - 18.11.18 - 22:47
(0) Что за чемпионат? Дай ссылку, тоже поучаствую.
   RomanYS
 
6 - 18.11.18 - 22:54
(5) похоже на школьные задачи))
   DTX 4th
 
7 - 19.11.18 - 14:56
(3) Для одной линии разреза всё ок. Но тут внезапно оказалось, что их может быть несколько) Пересекаться не могут.

(5) Задача возникла в процессе разработки)
   RomanYS
 
8 - 19.11.18 - 14:58
"Задача возникла в процессе разработки)"
Класс! А какая исходная прикладная задача?
   RomanYS
 
9 - 19.11.18 - 15:01
(7) "их может быть несколько" ну это уже гораздо интереснее.
Нужно обходить вершины треугольника и концы разрезов.
   Garykom
 
10 - 19.11.18 - 15:03
Точки внутри "Vector2[] slice" упорядочены?
Соседние точки образуют именно начало-конец отрезка реза?

Если да то не вижу проблемы
 
 Рекламное место пустует
   Garykom
 
11 - 19.11.18 - 15:04
(10)+ Намек - алгоритм заливки замкнутого контура
   МимохожийОднако
 
12 - 19.11.18 - 15:07
(8) Стёкла режут или мебель изготавливают, например.
   Малыш Джон
 
13 - 19.11.18 - 15:25
(0)
1)делай соответсвующую структуру хранения данных, связанный список
получится два списка: список точек треугольник и список точек линии разреза
2) тупо перебором определяй какой отрезок(пара соседних элементов из списка) треугольника пересекается с отрезком линии разреза.
получается n точек пересечения, которые лежат и на треугольнике и на линии.
3) делишь список точек треугольника на несколько списков(в простейшем случае два), делишь список точек линии разреза(в простейшем случае вообще не делится)
4) объединяешь части списка точек треугольника с частями списка точек линии разреза
   DTX 4th
 
14 - 19.11.18 - 15:45
(11) Это?
http://expace.narod.ru/imageprocessing/algoritm.html
Что-то вообще не то

(12) Для игры)

(13) Это с учетом (7)? 4й пункт пока не уложился в голове
   Garykom
 
15 - 19.11.18 - 16:22
(14) >Что-то вообще не то

Все то, заливаешь каждый из контуров своим цветом (отличным от цвета снаружи), а затем берешь и двигаешься от любой из точек по границе разных цветов - обойдешь все нужные граничные точки (включая исходные) контура (которому принадлежит начальная что взял).

Найденные точки исключаешь и повторяешь обход контура, взяв за начальную точку любую оставшуюся.
   Garykom
 
16 - 19.11.18 - 16:24
(15)+ Когда двигаешься всегда сворачивать туда где основной цвет нужного контура, с другой стороны может быть смена цвета второго контура и наружного.
   Малыш Джон
 
17 - 19.11.18 - 16:26
(14) https://ibb.co/nNLgUf

треугольник: A1,А2,А3
линия: В1,В2,В3,В4,В5,В6
точки пересечения:
А1А2 х В1В2 = С1
А2А3 х В3В4 = С2
А2А3 х В4В5 = С3
А3А1 х В5В6 = С4

Итого: треугольник(список разбит в точках С): (А1,С1)+(С1,А2,С2)+(С2,С3)+(С3,А3,С4)+(С4,А1)
линия: (В1,С1)+(С1,В2,В3,С2)+(С2,В4,С3)+(С3,В5,С4)+(С4,В6)

(В1,С1) и (С4,В6) - концы снаружи треугольника, они по условиям не нужны.

Остальное сращиваем, т.е  по треугольнику идем до первой точки С, далее от неё - идем по линии разреза до след. точки С, далее по треугольнику и т.д., пока не замкнется цикл:

(А1,С1)+(С1,В2,В3,С2)+(С2,С3)+(С3,В5,С4)+(С4,А1) = (А1,С1,В2,В3,С2,С3,В5,А1)

второй кусок - соседний с первым, для него цепочки точек В идут в обратном порядке:
(С1,А2,С2)+(С2,В3,В2,С1) = (С1,А2,С2,В3,В2,С1)

третий кусок - не нужен, т.к внешний - (С2,В4,С3,С2)

четвертый, опять соседний с первый, опять цепочка В в обратном порядке:

(С3,А4,С4)+(С4,В5,С3) = (С3,А4,С4,В5,С3)
   Garykom
 
18 - 19.11.18 - 16:26
Я правильно понял что тебе нужно получить замкнутую последовательность точек каждого контура?
   RomanYS
 
19 - 19.11.18 - 16:31
(15) Что-то не понял идею. Предлагается эти векторы где-то "визуализировать" в пикселях и потом что-то заливать?
   Garykom
 
20 - 19.11.18 - 16:32
(0) Кстати у тебя два варианта:
1. точки начала и конца разреза принадлежат одной стороне треугольника
2. точки начала и конца разреза принадлежат разным сторонам треугольника
   Вафель
 
21 - 19.11.18 - 16:32
те нужно упорядочить массив разрезов?
   RomanYS
 
22 - 19.11.18 - 16:32
(17)  из (0): точки разреза (начало и конец принадлежат сторонам треугольника)
   Garykom
 
23 - 19.11.18 - 16:33
(19) Ну да, причем для действительных чисел округлять можно (попадание в пиксель), главное чтобы все исходно заданные точки были целыми
   Garykom
 
24 - 19.11.18 - 16:49
(21) Неа из 3 точек вершин треугольника и массива разрезов получить два новых разных массива контуров-фигур
   RomanYS
 
25 - 19.11.18 - 16:52
(23) ну допустим они целые, в диапазоне 0-1000000. Вы будете закрашивать 10^12 точек чтобы 5 вершин обойти, это даже не из пушки по воробьям, это гораздо круче
   Garykom
 
26 - 19.11.18 - 16:53
(20)+ Хм их этих двух вариантов и вытекает решение кста.

Точки начала/конца разреза на одной стороне треугольника.
1. Находим эту сторону
2. Находим ближайшие точки вершин треугольника к точкам начала/конца (определяем пары)
3. Добавляем третью вершину трегольника - готов один контур

А второй контур это всего навсего исходный массив разрезов ))

Вот для "точки начала и конца разреза принадлежат разным сторонам треугольника" чуть сложнее
   Garykom
 
27 - 19.11.18 - 16:56
(25) Да согласен глупость закрашивать это нафик не надо
   Garykom
 
28 - 19.11.18 - 17:07
(26)+ Хотя нифига не сложнее, там просто на первом шаге надо понять какая вершина треугольника соединяет эти две разные стороны (на которых точки начала и конца разреза)
   Вафель
 
29 - 19.11.18 - 17:23
Вот что бывает,когда нет базы по алгоритмике


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует