Почему мой перекрестный тест отрезка не вернет истину?

Я уже знаю, какой вывод должен быть для этой программы — моя проблема в том, что я не могу заставить программу выдавать правильный вывод или какой-либо вывод в этом отношении. Моя проблема: определить и отобразить все этапы данного тура, которые пересекают любой другой этап. Данные следующие: Туры («города»): {0, 4, 1, 3, 2}, а точки этих «городов»: {2,0}, {4,1}, {0,1 }, {3,2}, {1,2}. Вот моя программа:

    #include <iostream>

using namespace std;

const int MAX = 100;

bool doCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4);

int main()
{
int numPts = 5;
int tourAry[MAX] = {0, 4, 1, 3, 2};
int pointsAry[MAX][2] = {{2, 0},{4, 1},{0, 1},{3, 2},{1, 2}};for(int start = 0; start <= numPts - 3; start++)
{
int startPt = tourAry[0];
int endPt = tourAry[1];
int testSegmentX1 = pointsAry[startPt][0];
int testSegmentY1 = pointsAry[startPt][1];
int testSegmentX2 = pointsAry[endPt][0];
int testSegmentY2 = pointsAry[endPt][1];

for(int nextSeg = start + 2; nextSeg <= numPts - 2; nextSeg++)
{
startPt = tourAry[2];
endPt = tourAry[3];
int startX = pointsAry[startPt][0];
int startY = pointsAry[startPt][1];
int endX = pointsAry[endPt][0];
int endY = pointsAry[endPt][1];

if(doCross(testSegmentX1, testSegmentY1, testSegmentX2, testSegmentY2, startX, startY, endX, endY))
{
cout << tourAry[start] << " - " << tourAry[start+1] << " crosses " << tourAry[nextSeg] << " - " << tourAry[nextSeg+1] << endl;
}

}//for
}//for

return 0;

}//main

bool doCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
bool cross = true;
double denom, numerA, numerB, uA, uB;denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
numerA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
numerB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));

if(denom == 0.0)
{
if(numerA == 0.0 && numerB == 0.0)
{
cross = false;
}//if

}//if
else
{
float uA = numerA / denom;
float uB = numerB / denom;

if (uA > 0.0 && uA < 1.0 && uB > 0.0 && uB < 1.0)
{
cross = true;
}//if

else
{
cross = false;

}//else
}//else

return cross;

}//doCross

Я знаю, что выход должен быть: 0-4 пересечено 3-2
4-1 пересекли 3-2

Любая помощь будет принята с благодарностью.

0

Решение

Ваша индексация выглядит немного испорченной. Я, честно говоря, не слишком много отлаживал, когда понял, что алгоритм пересечения сработал.

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

    for(int i=0; i<numPts-1; i++) {
for(int j=i; j<numPts-1; j++) {
if(doCross(pointsAry[tourAry[i]][0],      // x1
pointsAry[tourAry[i]][1],      // y1
pointsAry[tourAry[i+1]][0],    // x2
pointsAry[tourAry[i+1]][1],    // y2
pointsAry[tourAry[j]][0],      // x3
pointsAry[tourAry[j]][1],      // y3
pointsAry[tourAry[j+1]][0],    // x4
pointsAry[tourAry[j+1]][1])) { // y4
cout << tourAry[i] << " - " << tourAry[i+1] << " crosses " << tourAry[j] << " - " << tourAry[j+1] << endl;
}
}
}

Это дает вывод:

0 - 4 crosses 3 - 2
4 - 1 crosses 3 - 2
0

Другие решения

Других решений пока нет …