ГЕОМЕТРИЧЕСКАЯ ЗАДАЧА С++

[kochet-kov]

Составить программу, отображающую на экране дисплея в текстовом режиме исходные данные и требуемые результаты. Реализовать ввод исходных данных следующими способами по выбору пользователя:
1. Вручную с клавиатуры;
2. С помощью генератора псевдослучайных чисел.

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



как я понял нужно соединить эту точку с вершинами
если какая-то прямая пересекает сторону(до этой вершины ) многоугольника , то не видна точка
Тут весь вопрос, как определить пересечение.




пока сделал вот это:

#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "math.h"
#include "time.h"


int _tmain(int argc, _TCHAR* argv[])
{
int n, answ;
int i;
printf("vvedite kolichestvo toghek:");
scanf("%i",&n);
char ch;
do
{
	 printf("Zadat elementi sluchaino&(1/2)");
	 scanf("%d", &answ);
		 answ=getch(); printf("%c\n", answ);
} while((answ!='y')&&(answ!='n'));
int* X= new int[n];
int* Y= new int[n];
 if (answ=='y')
 {
	
	 for(i=0; i<n; i++)
	 { X[i]= rand();
	 Y[i]=rand();
	 printf("(X[%i],Y[%i])= (%i,%i)\n", i+1, i+1, X[i],Y[i]);
	 }
 }
 else
 {
	  for(i=0; i<n; i++)
	  {
		  printf("Vvedite element X[%i]= ", i);
		  scanf("%i", &X[i]);
	      printf("Vvedite element Y[%i]= ", i);
		  scanf("%i", &Y[i]);
	  }
 }
	
getch();

return 0;
}

[andrewpalkin]

Как определить что они пересекаются , это тебе не программирование надо сейчас в помощь , а математику ... Просто проверять все прямые как ты и сказал , соединив твою точку со всеми вершинами . Но вот формула для проверки всего этого математически я не помню

Но идея у тебя правильная !!!!

[KEA0301]

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

[kochet-kov]

это я понял, но как исключить пересечения вне многоугольника?

[KEA0301]

Сообщение от kochet-kov

это я понял, но как исключить пересечения вне многоугольника?

Если точка пересечения лежит на отрезке от B(x1;y1) до C(x2;y2), то её координаты должны (x,y) удовлетворяют условию:
min(x1,x2)<=x<=max(x1,x2)
min(y1,y2)<=y<=max(y1,y2)
И так в цикле для каждой точке составляешь уравнение прямой от А до этой точки, во вложенном цикле проверяешь по всем прямым многоугольника принадлежит ли какая нибудь точка пересечения на отрезке, и если такой не нашлось то значит из А эту точку видно.

[kochet-kov]

так, это понял..
но для начала мне нужно отсортировать точки так, что бы получался многоугольник без самопересечения. для этого
Находим нижнюю точку - min(y) (если их несколько, то берем любую)
Её координаты - (x0,y0)
Остальной массив сортируем по возрастанию значения (xi-x0)/(yi-y0)

но компилятор ругается(

int x0,y0;
x0=X[index_niznei_grani];
y0=Y[index_niznei_grani];
int* k= new int[n];
 for (i=0;i<n; i++)
 {	 k[i]=(((X[i]-x0))/((Y[i]-y0)));
 printf(" k[%i]=%i\n",i+1,k[i]);
 }

в этом участке кода где-то ошибка

[Stilet]

но компилятор ругается

Что такими словами что приводить стыдно?

[kochet-kov]

да, нет уже нашел ошибку.. на 0 не делит...

[kochet-kov]

я переделал начало программы..
теперь мне нужно отсортировать точки по алгоритму Джарвиса.. кто может с этим помочь?

#include <stdafx.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

//структура точка
struct Point {
  int x, y;
};





int main()
{
	
	Point *Points;
   Point *A;
	double *sDist, min;
	int N = 0, i, j, R1 = 0, R2 = 0, index = 0;
	bool flag = true;
	char ch;
	
	printf("Vvedite kol-vo tochek na ploskosti ");
	scanf("%d", &N);

	Points = new Point[N];
	sDist = new double[N];
      A=new Point[1];
	//Цикл пока не будет нажата y или n
	do {
		printf("Zadat elementi sluchaino?(y/n) ");
		scanf("%c", &ch);
		ch = getch(); printf("%c\n", ch);
	
	}while((ch != 'y')&&(ch != 'n'));

	//Если была нажата y
	if (ch == 'y'){
	srand((int)time(NULL));
	printf("Vvedite predel generacii dla tochek  ");
	scanf("%d %d", &R1, &R2); 

		for (i = 0; i < N; i++) {
          Points[i].x = rand() % (R2 - R1) + R1;
          Points[i].y = rand() % (R2 - R1) + R1;
          printf("Tochka %d: (%d, %d)\n", i+1, Points[i].x, Points[i].y );
        }
          A[1].x = rand() % (R2 - R1) + R1;
          A[1].y = rand() % (R2 - R1) + R1;
	printf("Tochka A: (%d, %d)\n", A[1].x, A[1].y );
	}
	else { //Если была нажата n
	printf("Zadaite koordinati tochkami\n ");

        for (i = 0; i < N; i++) {
			printf("Tochka %d ", i+1);
		  scanf("%d %d", &Points[i].x, &Points[i].y);
        }
	printf("Tochka A ");
		  scanf("%d %d", &A[1].x, &A[1].y);
	}


	//найдем самую левую из самых нижних
	
		int miny,minx, index_niznei_grani,index_samogo_levogo_iz_niznih;
       
	  miny =  Points[0].y;
	  minx=  Points[0].x;
      index_niznei_grani = 0;
	  index_samogo_levogo_iz_niznih = 0;
           for(i=0; i<N; ++i) 
		   {
              if(miny > Points[i].y) {
                       miny  = Points[i].y;
	                   index_niznei_grani= i;	
					   
                     }	 
                   }   
            for (j=0; j<N ; j++)
					   {if (Points[i].y ==  miny && minx > Points[i].x) 
                        minx = Points[i].x;
					   index_samogo_levogo_iz_niznih= i;}

printf("Tochka %i samaya levaya iz samixniznih: (%d, %d)\n",  Points[index_samogo_levogo_iz_niznih].x,  Points[index_niznei_grani+1].y );

если конкретнее на данном этапе на получается найти самую левую из самых нижних точку

//найдем самую левую из самых нижних
	 
		int miny,minx, index_niznei_grani,index_samogo_levogo_iz_niznih;
       
	  miny =  Points[0].y;
	  minx=  Points[0].x;
      index_niznei_grani = 0;
	  index_samogo_levogo_iz_niznih = 0;
           for(i=0; i<N; ++i) 
		   {
              if(miny > Points[i].y) {
                       miny  = Points[i].y;
	                   index_niznei_grani= i;	
					   
                     }	 
                   }   
            for (j=0; j<N ; j++)
					   {if (Points[i].y ==  miny && minx > Points[i].x) 
                        minx = Points[i].x;
					   index_samogo_levogo_iz_niznih= i;}

printf("Tochka %i samaya levaya iz samixniznih: (%d, %d)\n",  Points[index_samogo_levogo_iz_niznih].x,  Points[index_niznei_grani+1].y );