Пересечение фигур.

qqwe
Любой пиксель, цвет которого отличается от P(0, 0) не принадлежит фону. Это задача не на распознавание предметов или есчо чего либо.

 

Посмотрел я на ваш рисунок и ко мне пришла идея. Можно растр хранить не просто в виде растра обычного, а в виде разряженной матрицы, которая описывает только контур фигуры (ведь нам нужен только контур?). Тогда при правильной структуре такой матрицы можно действительно повысить скорость обработки. Мне видится примерно такая структура:

Код (Text):

1. Строка1: 0
2. Строка2: {x1,y1},{x2,y2}
3. Строка3: {x1,y1},{x2,y2},{x3,y3},{x4,y4}
4. Строка4: {x1,y1},{x2,y2},{x3,y3},{x4,y4}
5. Строка5: {x1,y1},{x2,y2}
6. Строка6: 0

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

 

hivemind
Структура немного иной должна быть, это массив пиксель поверхности, где каждый пиксель описан двумя координатами и вектором. Тогда после описания обеих поверхностей трассируем тестируемую поверхность и для каждой точки этой поверхности проверяем условие вхождения в фигуру(трассируем её поверхность и проверяем условие выше). При выделении поверхности не будут затрагиваться внутренние точки фигуры, а только фон, тоесть по сути фон становится фигурой(а фигуры так скажем "дырками"). Если фигура содержит вложенные фигуры, тоесть отдельные учатки фона, то следует их обьеденить линиями с исходной поверхностью(это реализуется алго заливки используя эти свойства поверхности).

 

gaeprust
Вообще-то четное количество точек у меня заменяет информацию о векторах. Только у нас один аспект упущен из виду - а что если мы имеем горизонтальную прямую? Куда укажут ваши вектора тогда? Ну а у меня нарушится четность с вероятностью 0.5

Надо тогда вводить наверно не два вектора, а флаг:
- слева пусто-справа фигура
- справа пусто-слева фигура
- слева фигура-справа фигура

Слева пусто-справа пусто - такой флаг нам не нужен, ибо в разряженной матрице таких точек мы держать не будем

 

hivemind
Все точки горизонтальной прямой будут принадлежать поверхности.

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



Вот две фигуры пересекаются. Изображена только поверхность. Точки между двумя точками поверхности, в которых V = Down и V' = Up, где X' > X принадлежат фигуре, как сказано выше. Значит делаем вывод, что фигуры пересекаются, если точка поверхности первой фигуры лежит между точками другой поверхности с условием выше. Также все точки лежащие на одной прямой между двумя точками обеих поверхностей являются общими для обеих фигур.

 

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

Кстати, вы отлично заметили, что если работать со строками в массиве, то хранить Y у точек не обязательно

На самом деле "мой" флаг и "ваши" вектора - суть одно и то же. Только почему-то мне кажется, что будет удобнее все же работать как с флагом, хоть вектора и единичные. Конечно, если векторы не "вырождать" в флаг. Но это не принципиально.

 

gaeprust
сменил бы ник на нормальный, это вообще отвратительный =)

 

hivemind
Вот написал небольшой псевдокод(это блок-схема, только текстовая). Условно присвоим значения вектору V от нуля циклически по часовой стрелке, тоесть 0: Up, 1: Right.., тогда поверхность будет описывать следующий код(если V = Down, то поверхность справа, так удобнее):

Код (Text):

1. if V = Up
2. if Point(X + 1, Y + 1)
3.         X = X + 1
4.         Y = Y + 1
5.         V = Right
6.     elseif Point(X, Y + 1)
7.         Y = Y + 1
8.     else
9.         V = Left
10.     fi
11. elseif V = Right
12. if Point(X + 1, Y - 1)
13.         X = X + 1
14.         Y = Y - 1
15.         V = Down
16.     elseif Point(X + 1, Y)
17.         X = X + 1
18.     else
19.         V = Up
20.     fi
21. elseif V = Down
22. if Point(X - 1, Y - 1)
23.         X = X - 1
24.         Y = Y - 1
25.         V = Left
26.     elseif Point(X, Y - 1)
27.         Y = Y - 1
28.     else
29.         V = Right
30.     fi
31. elseif V = Left
32. if Point(X - 1, Y + 1)
33.         X = X - 1
34.         Y = Y + 1
35.         V = Up
36.     elseif Point(X - 1, Y)
37.         X = X - 1
38.     else
39.         V = Down
40.     fi
41. fi

Лучше описать дельту координат в двух массивах T1 и T2, тогда:

Код (Text):

1. Step(*X, *Y, *V):
2.     X0 = X
3.     Y0 = Y
4.     Do
5. if Point(X + T1.dX{V}, Y + T1.dY{V})
6.             X = X + T1.dX{V}
7. Y = Y + T1.dY{V}
8.             V = V + 1
9. elseif Point(X + T2.dX{V}, Y + T2.dY{V})
10.             X = X + T2.dX{V}
11. Y = Y + T2.dY{V}
12. else
13.             V = V - 1
14. fi
15.     Loop (X <> X0) or (Y <> Y0)
16. ret
17.  
18.  
19. T1{ dX  dY
20. +1  +1
21. +1  -1
22. -1  -1
23. -1  +1
24. }
25.  
26. T2{ dX  dY
27. 0   +1
28. +1  0
29. 0   -1
30. -1  0
31. }

На основе этого кода можем описать поверхность:

Код (Text):

1. CreateSurface(X, Y, P{}):
2.     V = 2   ; Down, поверхность справа.
3.     X0 = X
4.     Y0 = Y
5.     !dV ; Флаг изменения вектора V.
6.     !J  ; Индекс описателя точки в массиве P{}.
7.     Do
8.         P{J} = (X, Y, V)
9.         Step(X, Y, V)
10.         if V <> 2
11.             dV = TRUE
12.         fi
13.     J = J + 1
14.     Loop (X = X0) & (Y = Y0) & (V = 2) & dV
15.     ret

Тогда код, определяющий принадлежность точки фигуре будет следующим:

Код (Text):

1. P - координаты проверяемой точки.
2. S - координаты границы фигуры(она справа от этой точки).
3. ;
4. IsPointBelongToFigure(Px, Py, Sx, Sy):
5.     CreateSurface(Sx, Sy, P{})
6.     if P{Px, Py}    ; Точка принадлежит поверхности.
7.         End TRUE   
8.     fi
9.     A{X, Y} = FindLeftPoint(P{}, Px, Py)    ; Ищем точку слева.
10.     if A{}  ; Если точка найдена.
11.         B{X, Y} = FindRightPoint(P{}, Px, Py)   ; Ищем точку справа.
12.         if B{}  ; Точка справа найдена.
13.             As{X, Y, V} = FindPointInSurface(P{}, A{})  ; Ищем левую точку на поверхности.
14.             Bs{X, Y, V} = FindPointInSurface(P{}, B{})  ; И правую.
15.             if As & Bs  ; С двух сторон есть поверхность.
16.                 if As.X{} < Bs.X{}
17.                     As.X{} xchg Bs.{X}
18.                 fi
19.                 if (As.V{} = 2) & Bs.V{}    ; Проверяем вектора(Up...P...Down).
20.                     End TRUE
21.                 fi
22.             fi
23.         fi
24. fi

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

 

На современных видеокартах сравнение таких массивов очень быстро.

 

gaeprust

я и не понял сразу, что вы клерк. извините.