Проверка на то что точка лежит внутри многоугольника: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «==Идея== Если зафиксировать какую-либо вершину, то относительно нее углы будут расположе...») |
Глеб (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 3: | Строка 3: | ||
Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего. | Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего. | ||
+ | ==Код== | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | point zero;//какая-то точка, которую мы сохранили как 0, для того, чтобы определять по или против | ||
+ | //a = vector_angles; | ||
+ | point my = { q.y - zero.y, q.x - zero.x }; | ||
+ | auto it = upper_bound (a.begin(), a.end(), my); | ||
+ | if (it == a.end() && my.a == a[n - 1].a && my.b == a[n - 1].b) { | ||
+ | it = a.end() - 1; | ||
+ | } | ||
+ | if (it != a.end() && it != a.begin()) { | ||
+ | int p1 = int(it - a.begin()); | ||
+ | if (in(p[p1], p[p1 - 1], q) <= 0) {//проверка то что внутри | ||
+ | //внутри | ||
+ | } | ||
+ | } | ||
+ | //нет | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 14:28, 9 января 2021
Идея
Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего.
Код
point zero;//какая-то точка, которую мы сохранили как 0, для того, чтобы определять по или против
//a = vector_angles;
point my = { q.y - zero.y, q.x - zero.x };
auto it = upper_bound (a.begin(), a.end(), my);
if (it == a.end() && my.a == a[n - 1].a && my.b == a[n - 1].b) {
it = a.end() - 1;
}
if (it != a.end() && it != a.begin()) {
int p1 = int(it - a.begin());
if (in(p[p1], p[p1 - 1], q) <= 0) {//проверка то что внутри
//внутри
}
}
//нет
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin