//Точка пересечения прямых
static UPoint crossing_lines(ULine ln1, ULine ln2){
assert(!ln1.empty());
assert(!ln2.empty());
UPoint uPoint;
uPoint.SetPoint(
1000000*(1000000*ln2.vc()*ln1.vb()-1000000*ln1.vc()*ln2.vb())
/
(1000000*ln1.va()*ln2.vb()-1000000*ln2.va()*ln1.vb())/1000000
,
1000000*(1000000*ln2.vc()*ln1.va()-1000000*ln1.vc()*ln2.va())
/
(1000000*ln1.vb()*ln2.va()-1000000*ln2.vb()*ln1.va())/1000000
);
return uPoint;
}
Как реализована функция PtInRegion? Или как определить попадение точки в н-угольник?
Здравствуйте, такой вот вопрос... Может и странный.
Дело в том, что мне надо определять, попадает ли точка в н-угольник или нет.
Все конечно хорошо, если пользоваться API PtInRegion и CRgn::CreatePolygonRgn, вся беда лишь в том, что это надо сделать кроссплатформенным, т.е. надо самому реализовывать алгоритм.
Не знаю, есть ли способы посмотреть как реализованы библиотечные функции, но вдруг есть и мне не прийдется ломать голову :)
Смотрел я заголовочный файл, там только декларация классов, реализации нет :(
Дело в том, что мне надо определять, попадает ли точка в н-угольник или нет.
Все конечно хорошо, если пользоваться API PtInRegion и CRgn::CreatePolygonRgn, вся беда лишь в том, что это надо сделать кроссплатформенным, т.е. надо самому реализовывать алгоритм.
Не знаю, есть ли способы посмотреть как реализованы библиотечные функции, но вдруг есть и мне не прийдется ломать голову :)
Смотрел я заголовочный файл, там только декларация классов, реализации нет :(
1) Триангулиовать фигуру(разбить на преугольники.
2) В каждом треугольнике(ABC):
a) Провести через потенциальнцю точку перпендикуляры стронам(получится 3 линии).
б) Рассмотреть пересечение линии перпендикуляра со стороной(которой он перпендикулярен), если все три перечения лежат в пределах отрезка - точкат в треугольнике.
Ну вот и все. Правда гемморой. Но что поделать.
Вот вам помощь(файлы):
Посмотрите "CLine.h" и "CMathPoint.h"
там есть функции для перпендикуляров и пересечений.
2) В каждом треугольнике(ABC):
a) Провести через потенциальнцю точку перпендикуляры стронам(получится 3 линии).
б) Рассмотреть пересечение линии перпендикуляра со стороной(которой он перпендикулярен), если все три перечения лежат в пределах отрезка - точкат в треугольнике.
Ну вот и все. Правда гемморой. Но что поделать.
Вот вам помощь(файлы):
Посмотрите "CLine.h" и "CMathPoint.h"
там есть функции для перпендикуляров и пересечений.
Цитата: Lei fang
Не знаю, есть ли способы посмотреть как реализованы библиотечные функции, но вдруг есть и мне не прийдется ломать голову :)
Смотрел я заголовочный файл, там только декларация классов, реализации нет :(
Смотрел я заголовочный файл, там только декларация классов, реализации нет :(
Они все в DLL уже в двоичном коде.
Соврал - те были недоработары.
Вот.
Вот.
Благодарю, крутая вещь :) А есть еще что-нибудь для поворота фигуры относительно центра? Как узнать новые координаты вершин, если если известны первоначальные и угол поворота?
Цитата: sigmov
1) Триангулиовать фигуру(разбить на преугольники.
А как разбивать, если многоугольник не является выпуклым?
Как вариант: можно из каждого угла многоугольника провести отрезок к точке, и посмотреть: если хотя бы один пересекает стороны многоугольника нечетное количество раз - точка не лежит во многоугольнике.
Цитата: Lei fang
А есть еще что-нибудь для поворота фигуры относительно центра? Как узнать новые координаты вершин, если если известны первоначальные и угол поворота?
Где Вы видели у многоугольника центр? :) Или Вы имеете в виду какой-то другой центр? В любом случае, представьте каждую вершину в виде вектора от "центра" до вершины и поворачивайте их сколько угодно
Цитата: dreamer.mas
А как разбивать, если многоугольник не является выпуклым?
Т.е на первом шаге мы берем вершину №1.
Затем строим треугольник (1,2,3)
Далее:
(1,3,4)
(1,4,5)
...........
(1,n-1,n)
Главное, чтоб стороны ни одного из треугольников не пересекали стороны нашего n-угольника, но совпадать они могут(Это гарантировано при выпуклом и возможно при вогнутом).
В противном случае - с помощью треугольников достроить его до выпуклово(треугольники с помощью которых провели "достойку" объявляются "мертвыми").
Затем по обычному алгоритму, а в конце проверка на попадание в "мертвый" треугольник.
Цитата: dreamer.mas
Как вариант: можно из каждого угла многоугольника провести отрезок к точке, и посмотреть: если хотя бы один пересекает стороны многоугольника нечетное количество раз - точка не лежит во многоугольнике.
Допустим треугольник(ABC). Точка вне его(Пусть P сразу за A).
AP - не пересекает ничего.
BP - не пересекает ничего
CP - не пересекает ничего
dreamer.mas, на счет вашего варианта, посмотрите вложенную картинку. Пересечение с вершинами считать как пересечение с линией? Похоже не всегда, если количество пересечений нечетное, то точка вне полигона.
А под центром, я подразумевал м... не знаю какой центр. У всех полигонов есть центр, даже если он лежит вне полигона. Как-то его подсчитывали. И кажется он называется геометрический центр. Для простоты, наверное можно явно задать точку, относительно которой будет поворот.
А под центром, я подразумевал м... не знаю какой центр. У всех полигонов есть центр, даже если он лежит вне полигона. Как-то его подсчитывали. И кажется он называется геометрический центр. Для простоты, наверное можно явно задать точку, относительно которой будет поворот.
Цитата: Lei fang
Благодарю, крутая вещь :) А есть еще что-нибудь для поворота фигуры относительно центра? Как узнать новые координаты вершин, если если известны первоначальные и угол поворота?
Двухмерное пространство?
Да. К счастью не трехмерное :P
Цитата: Lei fang
Да. К счастью не трехмерное :P
Элементрарно
Код:
Xnew=Xolg*Cos(fi)
Ynew=Yold*Sin(fi)
Ynew=Yold*Sin(fi)
fi - угол поворота.
Но эт только вокруг центра (0,0)
Иначе - приводите центр к (0,0) и все остальные координаты изменятся на те же величины.
Хм, действительно элементарно :) Благодарю. Сейчас если разберусь с этими треугольниками, то все будет хорошо.
Возник вопрос. а что это за магическое число 1000000?
Возник вопрос. а что это за магическое число 1000000?
Код:
Цитата: Lei fang
Хм, действительно элементарно :) Благодарю. Сейчас если разберусь с этими треугольниками, то все будет хорошо.
Возник вопрос. а что это за магическое число 1000000?
Возник вопрос. а что это за магическое число 1000000?
Предохраняет от погрешности.
Тип double - округляемый дробной частью.
Допустим, у вас может быть 29,99999(9), а cout выведет 30.
В итоге: имеются 2 прямые.
2x+30y-6=0;
2x+30y-8=0;
И они оказываются не параллельны, т.к. одна из 30 - это 29,99999(9).
Причем данный баг может получиться 2.1/0.7+0.3=2.99999(9)
А вот (2100000/700000+300000)/10000000=3.0
Такие вот пироги.
И 1000000 - число предохраняет от ошибки, в определенной степени.