Координаты в asm и функции для работы с ними

Хотелось бы узнать с помошью каких функций производится работа с координатами. Конкретная задача это создание многоугольника по координатам точек, и произвольной точки, и определение лежит ли точка в многоугольнике или находится за его пределами.
Буду рад любой полезной инфе по данной задаче, и благодарен всем кто поможет =)

 

Точно также как и в ЯВУ.

 

GoldFinch, замут в том что я яву никогда не изучал, поэтому и спрашиваю

 

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

 

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

 

MasterKenny
ЯВУ - это язык(и) высокого уровня, если че.

 

CyberManiac, спс идея гут, попробую

 

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

 

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

 

Многоугольник ведь это произвольная совокупность точек, тоесть любая фигура, разрезать её нет смыла. Я писал когдато про попиксельное описание фигуры. То что нужно, вобще класный способ, главное быстрый. Вот цитата:

Вот сам кодес:

Код (Text):

1. .code
2. VECTOR_UP       equ 0
3. VECTOR_RIGHT    equ 1
4. VECTOR_DOWN equ 2
5. VECTOR_LEFT equ 3
6.  
7. IMAGE_BORDERS struct
8. ImageWidth  ULONG ?
9. ImageHeight ULONG ?
10. IMAGE_BORDERS ends
11. PIMAGE_BORDERS  typedef ptr IMAGE_BORDERS
12.  
13. SLICING_DATA struct
14. ContextHandle   HANDLE ?
15. Borders     IMAGE_BORDERS <>
16. PointCallback   PVOID ?
17. Vector      ULONG ?
18. PointX      ULONG ?
19. PointY      ULONG ?
20. SLICING_DATA ends
21. PSLICING_DATA typedef ptr SLICING_DATA
22.  
23. Point proc C
24. ;Ebx = SLICING
25. ;Esi = X
26. ;Edi = Y
27.     assume ebx:PSLICING_DATA
28.     test esi,esi
29.     js carry_       ;X < 0
30.     test edi,edi
31.     js carry_       ;Y < 0
32.     cmp [ebx].Borders.ImageWidth,esi
33.     jbe carry_
34.     cmp [ebx].Borders.ImageHeight,edi
35.     jbe carry_
36.     Call [ebx].PointCallback
37.     test eax,eax
38.     ret
39. carry_:
40.     test ebx,ebx    ;Reset fz
41.     ret
42. Point endp
43.  
44. Slicing proc uses esi edi ebx SlicingData:PSLICING_DATA
45. ;Вычисляет координаты следующей точки контура и вектор в ней для оси OY направленной вверх.
46.     mov ebx,SlicingData
47.     assume ebx:PSLICING_DATA
48.     mov esi,[ebx].PointX
49.     mov edi,[ebx].PointY
50.     mov eax,[ebx].Vector
51.     add esi,dword ptr [FirstTable + eax*8]      ;X1
52.     add edi,dword ptr [FirstTable + eax*8 + 4]  ;Y1
53.     Call Point
54.     jnz First_Point_
55.     mov eax,[ebx].Vector
56.     add esi,dword ptr [NextTable + eax*8]       ;X2
57.     add edi,dword ptr [NextTable + eax*8 + 4]   ;Y2
58.     Call Point
59.     jnz Return_
60.     dec [ebx].Vector
61.     jmp Correct_Vector_
62. First_Point_:
63.     inc [ebx].Vector
64. Return_:
65.     mov [ebx].PointX,esi
66.     mov [ebx].PointY,edi
67. Correct_Vector_:
68.     and [ebx].Vector,11b
69.     ret
70. ;              dX  dY
71. FirstTable:
72.             DD +1, +1
73.             DD +1, -1
74.             DD -1, -1
75.             DD -1, +1
76.            
77. NextTable:
78.             DD -1,  0
79.             DD  0, +1
80.             DD +1,  0
81.             DD  0, -1
82. Slicing endp
83.  
84. SlicingOverwind proc uses esi edi ebx SlicingData:PSLICING_DATA
85. ;Вычисляет координаты следующей точки контура и вектор в ней для оси OY направленной вниз.
86.     mov ebx,SlicingData
87.     assume ebx:PSLICING_DATA
88.     mov esi,[ebx].PointX
89.     mov edi,[ebx].PointY
90.     mov eax,[ebx].Vector
91.     add esi,dword ptr [FirstTable + eax*8]      ;X1
92.     add edi,dword ptr [FirstTable + eax*8 + 4]  ;Y1
93.     Call Point
94.     jnz First_Point_
95.     mov eax,[ebx].Vector
96.     add esi,dword ptr [NextTable + eax*8]       ;X2
97.     add edi,dword ptr [NextTable + eax*8 + 4]   ;Y2
98.     Call Point
99.     jnz Return_
100.     dec [ebx].Vector
101.     jmp Correct_Vector_
102. First_Point_:
103.     inc [ebx].Vector
104. Return_:
105.     mov [ebx].PointX,esi
106.     mov [ebx].PointY,edi
107. Correct_Vector_:
108.     and [ebx].Vector,11b
109.     ret
110. ;              dX  dY
111. FirstTable:
112.             DD +1, -1
113.             DD +1, +1
114.             DD -1, +1
115.             DD -1, -1
116.            
117. NextTable:
118.             DD -1,  0
119.             DD  0, -1
120.             DD +1,  0
121.             DD  0, +1
122. SlicingOverwind endp
123.  
124. Describe proc uses esi edi ebx SlicingData:PSLICING_DATA
125. ;Описывает контур. Исходный вектор равен нулю(Up), фон слева, иначе войдёт в бесконечный цикл!
126.     mov ebx,SlicingData
127.     assume ebx:PSLICING_DATA
128.     mov esi,[ebx].PointX
129.     mov edi,[ebx].PointY
130.     invoke Slicing, SlicingData
131. loop_:
132.     invoke Slicing, SlicingData
133.     cmp [ebx].Vector,VECTOR_UP
134.     jne loop_
135.     cmp [ebx].PointX,esi
136.     jne loop_
137.     cmp [ebx].PointY,edi
138.     jne loop_
139.     xor eax,eax
140. return_:
141.     ret
142. Describe endp
143.  
144. DescribeOverwind proc uses esi edi ebx SlicingData:PSLICING_DATA
145. ;Описывает контур. Исходный вектор равен нулю(Down), фон слева, иначе войдёт в бесконечный цикл!
146.     mov ebx,SlicingData
147.     assume ebx:PSLICING_DATA
148.     mov esi,[ebx].PointX
149.     mov edi,[ebx].PointY
150.     invoke SlicingOverwind, SlicingData
151. loop_:
152.     invoke SlicingOverwind, SlicingData
153.     cmp [ebx].Vector,VECTOR_DOWN
154.     jne loop_
155.     cmp [ebx].PointX,esi
156.     jne loop_
157.     cmp [ebx].PointY,edi
158.     jne loop_
159.     xor eax,eax
160. return_:
161.     ret
162. DescribeOverwind endp
163. end

 

GoldFinch

- это называется вогнутый, и к тому же луч проводится в произвольном направление - можно и не попасть в сторону, а точки лежащие на стороне многоугольника нельзя просто взять и исключить - это не определяется или придется анализировать n лучей параллельных сторонам (для 2m угольника - n=m, для 2m-1 угольника - n=2m-1, многовато)
CrystalIC
и что это - квадратики рисует? проще задаться параметрами k, b и X (Х перебирать в цикле)
если не помните (Y=kX+b, k - tg(OX^line), b - смещение от (0,0), а X можно перебирать в цикле и получить Y точек (цикл выглядит примерно так

Код (Text):

1.   while (currentY<>nextY) {Y=k*X+b; X++}

возможно для перебора придется поменять знак прироста X, но это уже вне цикла. фон же определяется рисованием фона треугольника по трем точкам ((x1, y1), (x2, y2), (xn, yn)) где 2<n<m-1, m - количество точек в многоугольнике))

 

)))))

 

Можно использовать API
Polygon - рисует многоугольник
CreatePolygonRgn - создаёт регион из точек
PtInRegion - проверяет принадлежность точки региону
LineTo - рисует линию
SetPixel - рисует точку

Ещё загляни на www.algolist.ru

 

murder
а если пишешь не под винду, а под чистую платформу с нуля?

 

murder, спс за функции
всем огромное спасибо за помощь и потраченное время.
max7C4,я буду писать под винду, мне ограничений не говорили по этому поводу.

З.Ы. Если кому интересно могу потом выложить готовый проэкт сдесь.

 

max7C4
Ты не понял, читай есчо раз. Альтернативы этому способу нет.

 

Есть у меня сложная замкнутая фигура, ну давай, привиди пример как мне определить все её точки, проще говоря залить её. Только не нужно приводить в пример построчную заливку с затравкой, ибо это будет ответ гугля.

 

CrystalIC
Заливать её нет необходимости, т.к. это другая задача. Нужно проверить принадлежность точки многоугольнику. А многоугольник - это не произвольный набор точек, а набор точек и заданный порядок их обхода. В привычном определении он также должен иметь несамопересекающийся контур.
Т.о. предложение max7C4 с векторным произведением очень даже удачное:
1) выбираем направление обхода многоугольника
2) для каждого вектора-стороны многоугольника с учётом выбранного направления считаем третий коэффициент векторного произведения (первые два коэффициента - нули) с вектором, образованным началом вектора-стороны и проверяемой точкой.
3) если для всех сторон многоугольника знак третьего коэффициента векторного произведения одинаков, значит точка внутри.
Вполне понятно, что способ годится только для выпуклых многоугольников. Ну так это не проблема: предварительно обходим многоугольник, считая сумму внешних углов многоугольника. Если получится +360, то те углы, которые мы вычитали, - вогнутые, а если -360 - выпуклые. Дополним многоугольник (треугольниками), пока он не станет выпуклым, проверяя по вышеуказанному алгоритму принадлежность проверяемой точки к дополняемому треугольнику. Для полученного выпуклого многоугольника опять проверяем принадлежность точки по вышеуказанному алгоритму.

 

l_inc
Разумеется в заливки нет необходимости, проверяется принадлежность точки отрезку, между концами которого вектор при описании направлен в противоположные стороны и этот отрезок параллелен оси OX. А это и есть максимальное быстродействие и оптимальное решение.

Я не так понял поставленную задачу наверно, она оказалась примитивна, раз не произвольная фигура и все координаты известны.)