Это моя реализация алгоритма отсечения полигонов Сазерленда-Ходжмана.
я использую Библиотека BGI из университета Колорадо. Я использую OS = Win7. Visual C ++ 2008 Express.
Эта программа не работает правильно.
//Sutherland-Holdgman Line Clipping
#include "Line2d.h"#include "Rectangle2d.h"#include "Coordinates2d.h"#include "Bits.h"#include "Polygon2d.h"#include <list>
typedef enum PointPosition
{
Left, Right
} PointPosition;
typedef enum LinePosition
{
CompletelyOut, CompletelyIn, ClippingCandidate, ClippingCandidateExtended
} LinePosition;
class ClippingPolygon2d
{
private:
Rectangle2d rectangle;
Polygon2d polygon;
public:
ClippingPolygon2d(){}
//ClippingPolygon2d(Rectangle2d & rectangle, Polygon2d & polygon): rectangle(rectangle), polygon(polygon){}
void SetCandidatePolygon(Polygon2d & pol)
{
polygon = pol;
}
void SetClippingPolygon(Rectangle2d & rect)
{
rectangle = rect;
}
public:
std::vector<Point2d> GetClippedPoints()
{
std::vector<Point2d> vertexList = polygon.GetVertices();
std::vector<Point2d> clipping = rectangle.GetVertices();
for (size_t i = 0; i < clipping.size(); i++)
{
//obtaining one vertex and the next one from the clipping region.
//Then, constructing a line from them.
Line2d clippingEdge(clipping[i], clipping[(i + 1) % clipping.size()]);
std::vector<Point2d> temp;
for (size_t j = 0; j < vertexList.size(); j++)
{
Point2d polygonEdgeStart = vertexList[j];
Point2d polygonEdgeEnd = vertexList[(j + 1) % vertexList.size()];
if (clippingEdge.onLeft(polygonEdgeStart))
{
if (clippingEdge.onLeft(polygonEdgeEnd))
{
// point on the left, just add to vertexList
temp.push_back(polygonEdgeEnd);
}
else //Right
{
// calculate intersection I and add it to vertexList
temp.push_back(clippingEdge.GetIntersection(Line2d(polygonEdgeStart, polygonEdgeEnd)));
}
}
else //Right
{
if (clippingEdge.onLeft(polygonEdgeEnd))
{
//calculate intersection I and add I and polygonEdgeEnd to vertexList
temp.push_back(clippingEdge.GetIntersection(Line2d(polygonEdgeStart, polygonEdgeEnd)));
temp.push_back(polygonEdgeEnd);
}
else //Right
{
// nothing to do: outside of the window
}
}
}
vertexList = temp;
}
return vertexList;
}
};
int main()
{
//////////////////////// Initialize ///////////////////////
Coordinates2d::ShowWindow("Sutherland-Hodgeman Line Clipping");
///////////////////////////////////////////////////////////////
Rectangle2d rectangle(Point2d(20, 20), Point2d(200, 140));
Polygon2d polygon;
polygon.Add(Point2d(30, 40));
polygon.Add(Point2d(110,40));
polygon.Add(Point2d(130,110));
polygon.Add(Point2d(70,150));
polygon.Add(Point2d(10,110));
ClippingPolygon2d clip;
clip.SetClippingPolygon(rectangle);
clip.SetCandidatePolygon(polygon);
std::vector<Point2d> clippedVerticesList = clip.GetClippedPoints();
Coordinates2d::Draw(polygon, Red);
Coordinates2d::Draw(rectangle, Magenta);
Coordinates2d::Draw(clippedVerticesList, Thick, Yellow);
//////////////////////// Draw /////////////////////////
Coordinates2d::Wait(); return 0;
///////////////////////////////////////////////////////////////
}
double Line2d :: orientationOf(Point2d & point)
{
return (end.x - start.x) * (point.y - start.y) - (end.y - start.y) * (point.x - start.x);
}
bool Line2d :: onRight(Point2d & point)
{
return orientationOf(point) < -E; //for precision reason
}
bool Line2d :: onLeft(Point2d & point)
{
return orientationOf(point) > E;//for precision reason
}
Я нашел как минимум 2 проблемы в GetClippedPoints
функция:
if(i)
— это не правильно, потому что i
повторяется по краям окон. Я думаю, что вы предполагаете использовать if(j)
,for(size_t i=0 ; i<clippingRegionLines.size() ; i++)
должен преобразовать (генерировать новый) vertexList
(первоначально vertexList==allPolygonVertexes
) и используйте его в следующем шаге. (поэтому после всех итераций этого цикла вы получите обрезанный многоугольник). Поэтому мой совет здесь: представлять входной многоугольник в виде списка вершин вместо списка ребер.Также вы должны быть уверены, что std::vector<Line2d> clippingRegionLines = rectangle.GetLines();
возвращает сегменты, ориентированные против часовой стрелки.