51 / 51 / 14
Регистрация: 12.01.2013
Сообщений: 779
1

Попадание точки в фигуру на плоскости

04.09.2014, 20:35. Показов 7895. Ответов 40
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Мой друг, поступил в ВУЗ на программиста, и вот им дали, им лабу, и он попросил меня помочь, эта задача на первом курсе, после первой лекции
Попадание точки в фигуру на плоскости

Задача то легкая вроде бы кажеться, но я не могу понять к чему там цвета, и как их проверять, не могу ваше понять как ее решать может вы подскажите ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.09.2014, 20:35
Ответы с готовыми решениями:

Функция, проверяющая попадание точки с заданными координатами в фигуру
Помогите пожалуйста написать программу на С++, очень прошу.... Программа должна позволять...

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

Написать условие попадание точки в фигуру
Здравствуйте. Прошу написать условие для попадания точки в фигуру. Фигура прикреплена, попадать...

Определить попадание точки в заштрихованную область плоскости
18 и 19! Тема условные операторы (if else) Я бы сделал сам, но все плохо с математикой и не...

40
-=ЮрА=-
05.09.2014, 23:25     Попадание точки в фигуру на плоскости
  #21

Не по теме:

Повторюсь

Цитата Сообщение от Rookie Hose Посмотреть сообщение
Хотя, могу быть не прав
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Кому захочется поспорить со моим утверждением выше - даю подсказку как это делается по профессиональному http://www.microsoft.com/typog... TTCH01.htm

0
4 / 4 / 2
Регистрация: 25.08.2014
Сообщений: 36
06.09.2014, 04:08 22
-=ЮрА=-, я видел вашу ссылку, но для меня написанное там - темный лес, пока что.

По поводу вашего задания. Еще раз, я не спорю, что мой метод решения задачи ТС очень примитивен и не подходит для более сложных случаев. Возможно, дальше Вы будете смеяться , но попробую ответить на вопрос, решая задачу, как аналог задачи ТС:

1. Проведу условную координатную сетку;
2. Сниму координаты вершин фигур - насколько я понял из задания, они задаются по умолчанию, т.е. я должен их как-то описать. Фигур насчитал 6 + общая зона.
3. Далее ввожу точку.
4. Начинаю проверку, например, с треугольников (самый маленький я представил как часть общей зоны). Раскладываю на векторы и проверяю, находится ли точка в треугольниках.
5. Далее перехожу на прямоугольники. Тут понадобиться КУЧА условий, но ничего принципиально сложного не вижу.
6. Наиболее сложное, эллипс и незамкнутое кольцо...С первого взгляда, здесь придется поломать голову и освежить геометрию. С кругом проблем не должно быть (Пифагор).
Да, в итоге будет миллион if'ов, else'ов и т.д. Но, по-моему, задачу решит.

-=ЮрА=-, надеюсь, удовлетворил ваше любопытство Я не собираюсь с Вами спорить, у нас разные весовые категории, буду рад только спрашивать советы в данном форуме, по мере необходимости.

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

Добавлено через 3 часа 33 минуты
Решение задачи ТС.
Алгоритм (я полностью понимаю, что это, глазами опытного программиста, может выглядеть как жутко-длинный бесполезный велосипед, но я постарался логически разобрать эту задачу, наиболее просто и наглядно для такого же новичка, как и я ):
1. раскладываю вписанный квадрат (в программе он фигурирует как ромб) на отрезки-векторы и проверяю, как относительно них лежит наша точка, идя против часовой стрелки. Если все значения одного знака (в данном случае + )значит точка лежит внутри контура, 0 означает, что точка лежит на прямой. Если условие выполняется - цвет белый;
2. Далее проверяю наличие точки на окружности и сравнением координат четвертей с точкой, определяю цвет (красный или синий). Теорема Пифагора;
3. Далее, проверяю на наличие точки в описанном квадрате. Если есть, далее сравнением координат во II четверти окружности, задаю белый цвет;
4. Все остальное - желтое;

На граничных участках решил сделать главным цвет, описанный в коде первее, чем остальные.

Программу проверил на всех характерных точках - работает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <cstdlib>
 
int main()
{
    double spo; // Переменные специально разграничил, чтобы было удобнее понять...
    double r; // задаем радиус;
    printf("Enter radius of the circle: ");
    scanf("%lf", &r);
    double px, py; // задаем точку;
    // далее идет список вспомогательных переменных, для удобства я их разбил на принадлежность;
    double ox = r, oy = -r; // задаем центр окружности, границы четвертей берем из вершин ромба!!!;
    // определяем координаты вершин ромба и 4 переменные произведений векторов и точки. Первой вершиной выбрал левую;
    double rx1 = 0, ry1 = -r, rx2 = r, ry2 = -2 * r, rx3 = 2 * r, ry3 = -r, rx4 = r, ry4 = 0, tmp1, tmp2, tmp3, tmp4;
    //
    double sx1 = 0, sy1 = 0, sx2 = 0, sy2 = -2 * r, sx3 = 2 * r, sy3 = -2 * r, sx4 = 2 * r, sy4 = 0; // задаем вершины описанного квадрата;
    
    printf("Enter coordinates of the point [X Y]: ");
    scanf("%lf %lf", &px, &py);
    
    // См. 1 пункт алгоритма -идем против часовой стрелки - с точкой сравниваются последовательно вектора RX2RY2 RX1RY1 --> RX3RY3 RX2RY2 и т.д.;
    tmp1 = (rx2 - rx1)*(py - ry1) - (ry2 - ry1)*(px - rx1);
    tmp2 = (rx3 - rx2)*(py - ry2) - (ry3 - ry2)*(px - rx2);
    tmp3 = (rx4 - rx3)*(py - ry3) - (ry4 - ry3)*(px - rx3);
    tmp4 = (rx1 - rx4)*(py - ry4) - (ry1 - ry4)*(px - rx4);
 
    if ((tmp1 >= 0 && tmp2 >= 0 && tmp3 >= 0 && tmp4 >= 0) || (tmp1 <= 0 && tmp2 <= 0 && tmp3 <= 0 && tmp4))
    {
        printf("The point is inside the white zone\n");
        spo = px * py;
        printf("SPO = x * y = %.3lf\n", spo);
    }
    // См. 2 пункт алгоритма;
    else if ((r*r >= (oy - py) * (oy - py) + (ox - px) * (ox - px)) && ((px >= r && py >= -r) || (px <= r && py <= -r)))
    {
        printf("The point is inside the red zone\n");
        spo = (px + 10) / (px + py);
        printf("SPO = (x + 10) / (x + y) = %.3lf\n", spo);
    }
    else if ((r*r >= (oy - py) * (oy - py) + (ox - px) * (ox - px)) && ((px < r && py > -r) || (px > r && py < -r)))
    {
        printf("The point is inside the blue zone\n");
        spo = px + (1 / py);
        printf("SPO = x + (1 / y) = %.3lf\n", spo);
    }
    // См. 3 пункт алгоритма;
    else if ((r*r < (oy - py) * (oy - py) + (ox - px) * (ox - px)) && px < r && py > -r && px >= 0 && py <= 0)
    {
        printf("The point is inside the white zone\n");
        spo = px * py;
        printf("SPO = x * y = %.3lf\n", spo);
    }
    // См. 4 пункт алгоритма;
    else
    {
        printf("The point is inside the yellow zone\n");
        spo = px / (py - px);
        printf("SPO = x  / (y - x) = %.3lf\n", spo);
    }
 
    system("pause");
    return 0;
}
Добавлено через 14 минут
Надеюсь, ТС и его друг уже сами во всем разобрались....
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
06.09.2014, 04:19 23
Может я не правильно понял, что имел в виду -=ЮрА=-, и мой алгоритм однозначно нельзя назвать оптимальным по скорости и памяти, но это то, то получилось в лоб - и заливает всё что только можно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void my_fill(HWND hWnd, POINTS MP, COLORREF fill_c)
{
    HDC hdc = GetDC(hWnd);
    COLORREF MPc = GetPixel(hdc, MP.x, MP.y);
    if (MPc == fill_c) return;
 
    const unsigned int Pbufsize = 1000;
    POINTS P0[Pbufsize], *pf_beg = P0, *pf_end = P0, P1[Pbufsize], *pt_beg = P1;
    *pf_beg = MP;
    while (pf_end >= pf_beg) {
        POINTS *pf, *pt = pt_beg;
        for (pf = pf_beg; pf <= pf_end; pf++) {
            for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                POINTS P = *pf;
                P.x += dx;
                P.y += dy;
                COLORREF Pc = GetPixel(hdc, P.x, P.y);
                if (Pc == MPc) {
                    SetPixel(hdc, P.x, P.y, fill_c);
                    *pt++ = P;
                }
            }
        }
        pf = pf_beg;
        pf_beg = pt_beg;
        pf_end = pt - 1;
        pt_beg = pf;
    }
}
Миниатюры
Попадание точки в фигуру на плоскости  
1
Rookie Hose
06.09.2014, 04:25
  #24

Не по теме:

здорово! Но мне до этого как до Китая пока :(

0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
06.09.2014, 04:31 25
Rookie Hose, если вы внимательно всмотритесь в мой алгоритм, то увидите, что он тривиален и дубов - я просто беру цвет заданного стартового пикселя (ловлю его координаты по щелчку мыши) и делаю такое "растекающееся пятно", проверяя цвет соседних пикселей - пока он совпадает с цветом стартового пикселя
1
Заблокирован
Автор FAQ
06.09.2014, 10:26 26
_Ivana, у тебя реализован алгоритм для правила EvenOdd работающий в целочисленном растре и разбивающийся в хлам для пиксельной сетки меньше 20 пт, не говоря уже о том что о сглаживании при таком построении речи быть не может. Повторюсь для простого может работать всё что угодно, общий алгоритм я приводил выше, остальное дело сугубо личное.
0
-=ЮрА=-
06.09.2014, 10:31
  #27

Не по теме:

На счёт тетриса - чисто моё имхо - катастрофически неверный концепт отрисовки.

0
Заблокирован
Автор FAQ
06.09.2014, 10:44 28
Цитата Сообщение от Rookie Hose Посмотреть сообщение
По поводу вашего задания. Еще раз, я не спорю, что мой метод решения задачи ТС очень примитивен и не подходит для более сложных случаев. Возможно, дальше Вы будете смеяться , но попробую ответить на вопрос, решая задачу, как аналог задачи ТС:
- нет не буду это решение подходит для частного случая рассматриваемого в теме(всего лишь 1-го случая для конкретной конфигруации), поэтому я и привёл настоящий алгоритм который используют растеризаторы ВИН, КанджиТолк и др

Добавлено через 7 минут
здорово! Но мне до этого как до Китая пока
- почитай о GDI можешь начать с этого наглядного примера Как рисовать элементарные геометрические фигуры?


Добавлено через 50 секунд
Построить на экране рисунок одно подъездного дома, если известны координаты левого верхнего угла дома
1
4 / 4 / 2
Регистрация: 25.08.2014
Сообщений: 36
06.09.2014, 13:31 29
На 29 строке забыл добавить второе условие для переменной tmp4. Т.к. не могу отредактировать сообщение, приведу тут строчку:
C++
1
if ((tmp1 >= 0 && tmp2 >= 0 && tmp3 >= 0 && tmp4 >= 0) || (tmp1 <= 0 && tmp2 <= 0 && tmp3 <= 0 && tmp4 <= 0))
Хотя не обнаружил глюков и без условия, странно

_Ivana и -=ЮрА=-, большое спасибо за разъяснения. Ссылки сохранил, я к этому обязательно вернусь, сейчас же мне пока надо подучить элементарные основы
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
06.09.2014, 13:35 30
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
На счёт тетриса - чисто моё имхо - катастрофически неверный концепт отрисовки.
Сразу возникает комментарий и вопрос:
к: "критикуешь - предлагай" (С) Предложите верный концепт отрисовки.
в: вы судите о концепте отрисовки моего тетриса по приведенному коду заливки? В моей теме про тетрис представлен код первого релиза, там можно посмотреть как я его отрисовываю.

ЗЫ с ваших постов с примерами линий в консоли и началось мое рисование
0
Заблокирован
Автор FAQ
06.09.2014, 13:47 31
Цитата Сообщение от _Ivana Посмотреть сообщение
вы судите о концепте отрисовки моего тетриса по приведенному коду заливки?
- я лишь показал назилтую область и указал пределы использования "прямого бесстрашного" EvenOdd
Цитата Сообщение от _Ivana Посмотреть сообщение
к: "критикуешь - предлагай" (С) Предложите верный концепт отрисовки.
- постами пятью выше дал ссылку на спецификацию TrueType
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
06.09.2014, 13:53 32
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- постами пятью выше дал ссылку на спецификацию TrueType
Хотите с Безье и сплайнами, причем все руками без готовых функций графических библиотек? Хорошо, подумаю.

ЗЫ а в Тетрисе все беспощадно прямоугольное, там нет места для сложностей и подобных изысков
0
Заблокирован
Автор FAQ
06.09.2014, 14:09 33
Цитата Сообщение от _Ivana Посмотреть сообщение
Хотите с Безье и сплайнами, причем все руками без готовых функций графических библиотек? Хорошо, подумаю.
- я думал и работал над этим окло 8 месяцев, в итоге получил растеризатор эквивалетный ВИН 3.1 (касательно отрисовать - с нахрапу не получится даже меньше 30 пт хоть как то приемлимо отобразить даже простенький глиф, не говоря уже о глифах канджи).
Цитата Сообщение от _Ivana Посмотреть сообщение
ЗЫ а в Тетрисе все беспощадно прямоугольное, там нет места для сложностей и подобных изысков
- Тетрис рисуется объектами а не попиксельно. На счёт рисовать линию - линия это тоже кривая безье (1-t)P0 + t*P1
0
51 / 51 / 14
Регистрация: 12.01.2013
Сообщений: 779
06.09.2014, 21:31  [ТС] 34
Цитата Сообщение от Rookie Hose Посмотреть сообщение
=ЮрА=-, я видел вашу ссылку, но для меня написанное там - темный лес, пока что.
По поводу вашего задания. Еще раз, я не спорю, что мой метод решения задачи ТС очень примитивен и не подходит для более сложных случаев. Возможно, дальше Вы будете смеяться , но попробую ответить на вопрос, решая задачу, как аналог задачи ТС:
1. Проведу условную координатную сетку;
2. Сниму координаты вершин фигур - насколько я понял из задания, они задаются по умолчанию, т.е. я должен их как-то описать. Фигур насчитал 6 + общая зона.
3. Далее ввожу точку.
4. Начинаю проверку, например, с треугольников (самый маленький я представил как часть общей зоны). Раскладываю на векторы и проверяю, находится ли точка в треугольниках.
5. Далее перехожу на прямоугольники. Тут понадобиться КУЧА условий, но ничего принципиально сложного не вижу.
6. Наиболее сложное, эллипс и незамкнутое кольцо...С первого взгляда, здесь придется поломать голову и освежить геометрию. С кругом проблем не должно быть (Пифагор).
Да, в итоге будет миллион if'ов, else'ов и т.д. Но, по-моему, задачу решит.
-=ЮрА=-, надеюсь, удовлетворил ваше любопытство Я не собираюсь с Вами спорить, у нас разные весовые категории, буду рад только спрашивать советы в данном форуме, по мере необходимости.
После того, как решу задачу ТС, Вы сможете увидеть этот примитивный алгоритм в действии, ТС, надеюсь, подчерпнет идеи...А я, наконец-то, пойду начинать изучать циклы
Добавлено через 3 часа 33 минуты
Решение задачи ТС.
Алгоритм (я полностью понимаю, что это, глазами опытного программиста, может выглядеть как жутко-длинный бесполезный велосипед, но я постарался логически разобрать эту задачу, наиболее просто и наглядно для такого же новичка, как и я ):
1. раскладываю вписанный квадрат (в программе он фигурирует как ромб) на отрезки-векторы и проверяю, как относительно них лежит наша точка, идя против часовой стрелки. Если все значения одного знака (в данном случае + )значит точка лежит внутри контура, 0 означает, что точка лежит на прямой. Если условие выполняется - цвет белый;
2. Далее проверяю наличие точки на окружности и сравнением координат четвертей с точкой, определяю цвет (красный или синий). Теорема Пифагора;
3. Далее, проверяю на наличие точки в описанном квадрате. Если есть, далее сравнением координат во II четверти окружности, задаю белый цвет;
4. Все остальное - желтое;
На граничных участках решил сделать главным цвет, описанный в коде первее, чем остальные.
Программу проверил на всех характерных точках - работает
это точно рабочий, код моей задачи ?

Добавлено через 3 минуты
самое интересное что программа консольная
0
Заблокирован
Автор FAQ
06.09.2014, 21:38 35
CSharp, вообще решать задачу следует по теории множеств, ниже привожу каких, остальное - дело техники.
Выделяем 5 белых треугольников, и пересекаем с 2-мя множествами (красным и синим), которые образует кривая окружности. Каждое вхождение точки проверяем на принадлежность какому либо из множеств.
Миниатюры
Попадание точки в фигуру на плоскости  
0
2 / 2 / 1
Регистрация: 17.05.2013
Сообщений: 688
06.09.2014, 21:52 36
так какое правельно решение? мне как программисту интересно, я сам не могу понять как ее решать? а что за теория множист?
0
4 / 4 / 2
Регистрация: 25.08.2014
Сообщений: 36
06.09.2014, 23:44 37
CSharp, ну блин, а ты не удосужился скомпилировать и проверить? ...
Мое решение работает, но оно очень примитивное и преподу может не понравится сам метод. Делал я ее для себя лично, в целях самообразования.

Я бы на твоем месте прислушался к -=ЮрА=- и сделал бы задачу сам.
0
2 / 2 / 1
Регистрация: 17.05.2013
Сообщений: 688
08.09.2014, 09:33 38
А мне кажется что бы работала программа, а алгорит пофиг какой должен быть
0
51 / 51 / 14
Регистрация: 12.01.2013
Сообщений: 779
13.09.2014, 16:55  [ТС] 39
Цитата Сообщение от Rookie Hose Посмотреть сообщение
CSharp, ну блин, а ты не удосужился скомпилировать и проверить? ...
Мое решение работает, но оно очень примитивное и преподу может не понравится сам метод. Делал я ее для себя лично, в целях самообразования.
Сколько не вводил значения, никогда не появлялась красная и синяя зона. Все время желтая (ну тут понятное дело, она наиболее большая) и белая.
0
2 / 2 / 1
Регистрация: 17.05.2013
Сообщений: 688
16.09.2014, 13:01 40
в решенной задачи нету формулы окружности
0
16.09.2014, 13:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.09.2014, 13:01
Помогаю со студенческими работами здесь

Попадание точки в область плоскости. вывод формулы
ребят такая проблема не могу вывести формулу для написание в C# рисунок очень для меня далекий . По...

Попадание в фигуру
True при попадании, в противном случаи false. Помогите парни!

Попадание в фигуру (консоль)
True при попадании, в противном случаи false. Ссылка на свалку удалена. Для вложений...

Написать уравнение плоскости, проходящей через точки P и Q и перпендикулярной к заданной плоскости:
P(-1,2,1); Q(3 ,-4 , 2); 2x + 4y - 3z + 5=0.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru