| Вопрос: условие принадлежности точки к плоскости | Добавлено: 19.03.06 20:11 |
Автор вопроса:  КУДЕСНИК
|
| Ответы | Всего ответов: 22 |
|
Номер ответа: 16 Автор ответа:  vito Разработчик Offline Client Вопросов: 23 Ответов: 879 |
Web-сайт: Профиль | | #16 | Добавлено: 20.03.06 14:57 |
|
Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда у нас min_y = A.y, max_y = C.y, и нам надо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Мы знаем координаты всех вершин, поэтому мы можем написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как мы не знаем, какой из них левый, а какой правый, сравним их координаты по x и обменяем значения, если надо. Рисуем этот отрезок, повторяем процедуру для каждой строки - и вуаля, трегуольник нарисован.
Остановимся более подробно на нахождении пересечения прямой y = sy (текущей строки) и стороны треугольника, например AB. Напишем уравнение прямой AB в форме x = k*y+b: x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y) Подставляем сюда известное для текущей прямой значение y = sy: x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y) Вот, в общем-то, и все. Для других сторон пересечение ищется совершенно точно так же. А вот и пример кода. // ... // здесь сортируем вершины (A,B,C) // ... for (sy = A.y; sy <= C.y; sy++) { x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y); if (sy < B.y) x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y); else x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y); if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; } drawHorizontalLine(sy, x1, x2); } // ... Надо, правда, защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не стоит, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль. Код изменится совсем чуть-чуть: // ... // здесь сортируем вершины (A,B,C) // ... for (sy = A.y; sy <= C.y; sy++) { x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y); if (sy < B.y) x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y); else { if (C.y == B.y) x2 = B.x; else x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y); } if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; } drawHorizontalLine(sy, x1, x2); } // ... Вот и все. |
||
|
Номер ответа: 17 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #17 | Добавлено: 21.03.06 17:34 |
|
1) Сложить углы под которыми видны стороны треугольника из точки, если 360 градусов, то точка внутри
2) Построить на треугольнике параллелограмм, проверить принадлежность параллелограмму, провести отрезок через точку, параллельный стороне и равный ей, проверить в какой его половине лежит точка. 3) По площади треугольников, только не через формулу Герона, а через матричный вид: 1 | x1-x3 y1-y3 |
S = +- - | | 2 | x2-x3 y2-y3 | |
||
|
Номер ответа: 18 Автор ответа: VictorICQ: 345743490 Вопросов: 42 Ответов: 385 |
Web-сайт: Профиль | | #18 | Добавлено: 21.03.06 18:33 |
|
По-моему, ответ №13 способ 2 самый лучший. Простой и эффективный. Пишется короче всех. И никакой сортировки не надо.
Function VMul(byval dx1 as double, byval dy1 as double, _
byval dx2 as double, byval dy2 as double) as double vmul=dx1*dy2-dx2*dy1 End function Function InTriangle(byval x as double, byval y as double) as boolean intriangle=abs(sgn(vmul(x2-x1,y2-y1,x-x1,y-y1)) + _ sgn(vmul(x3-x2,y3-y2,x-x2,y-y2)) + _ sgn(vmul(x1-x3,y1-y3,x-x3,y-y3)))=3 End function Не проверял, но вроде должно работать. |
||
|
Номер ответа: 19 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74 |
Профиль | | #19 | Добавлено: 21.03.06 18:48 |
|
))
Когда-то такое писал, делал через площади. У этого метода большая погрешность. Вроде самый нормальный и точный метод. Есть треугольник: со сторонами A(Ax,Ay),B(Bx,By),C(Cx,Cy) точка D(Dx,Dy). Уравнение сторон: AB: Qabx*X+Qaby*Y+Qabc=0 BC: Qbcx*X+Qbcy*Y+Qbcc=0 CA: Qcax*X+Qcay*Y+Qcac=0 Где: Qabx = By-Ay Qaby = Ax-Bx Qabc = Ay*Bx-Ax*By Qbcx = Cy-By Qbcy = Bx-Cx Qbcc = By*Cx-Bx*Cy Qcax = Ay-Cy Qcay = Cx-Ax Qcac = Cy*Ax-Cx*Ay Если Qabx*Dx+Qaby*Dy+Qabc>=0 Qbcx*Dx+Qbcy*Dy+Qbcc>=0 Qcax*Dx+Qcay*Dy+Qcac>=0 или Qabx*Dx+Qaby*Dy+Qabc<=0 Qbcx*Dx+Qbcy*Dy+Qbcc<=0 Qcax*Dx+Qcay*Dy+Qcac<=0 То точка D лежит внутри треугольника ABC. В данном методе нет деления, соответственно в нем не будет деления на ноль(почти ноль) что приводить к большим погрешностям. |
||
|
Номер ответа: 20 Автор ответа: КУДЕСНИКВопросов: 10 Ответов: 13 |
Профиль | | #20 | Добавлено: 21.03.06 19:32 |
|
даа спасибо за инфу я долго мучался и всетаки спросил у препода как это сделать и он предложил мне тот метод который связон с площадями
самый простой |
||
|
Номер ответа: 21 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #21 | Добавлено: 21.03.06 20:36 |
| О блииин! точно!!!! помоему давноооо ещё шарп его предлагал | ||
|
Номер ответа: 22 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #22 | Добавлено: 21.03.06 22:33 |
Было дело 
ответ №13 способ 2 самый лучший Заметь его удивительное сходство с №17-3
|
||