为什么这个多边形裁剪代码没有给出预期的结果？

Question

This is my implementation of Sutherland-Hodgman Polygon Clipping Algorithm.

I am trying to clip a Positively Oriented and Convex polygon with a rectangular clipping area.

我正在使用 BGI library from colorado university。我正在使用 OS=Win7。 Visual C++ 2008 速成版。

此程序无法正常运行。

//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
}

Answer 1

我在 GetClippedPoints 函数中发现了至少 2 个问题：

您使用 if(i) - 这是不对的，因为 i 在 windows 边上迭代。我认为您应该使用 if(j).
假设for(size_t i=0 ; i<clippingRegionLines.size() ; i++)应该转换（生成新的）vertexList（最初是vertexList==allPolygonVertexes）并在下一步中使用它。（所以在这个循环的所有迭代之后你会得到裁剪的多边形）。所以我的建议是：将输入多边形表示为顶点列表而不是边列表。

您还需要确保 std::vector<Line2d> clippingRegionLines = rectangle.GetLines(); returns 段逆时针方向。

为什么这个多边形裁剪代码没有给出预期的结果？

Why doesn't this polygon clipping code give desired result?

c++

clipping