I created a 2D convex hull and wanted to check whether a point is inside it.

If the point is inside the polygon, the neighbor cross product vectors have the same directions. If the point is outside, one vector is toward the outside, the other one is toward the inside.



Here is a point P that is closed to the vertices A, B, and C. We have

    \[dir_0 = \overrightarrow{PC} \times \overrightarrow{PB}\]

    \[dir_1 = \overrightarrow{PB} \times \overrightarrow{PA}\]

The vector dir_0 is toward the outside screen, the vector dir_1 is toward the inside direction. So P is not in the convex hull.

#include <iostream>
#include <vtkSmartPointer.h>
#include <vtkSphereSource.h>
#include <vtkActor.h>
#include <vtkConeSource.h>
#include <vtkRenderer.h>
#include <vtkRenderWindow.h>
#include <vtkPolyDataMapper.h>
#include <vtkTextActor.h>
#include <vtkTextProperty.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkActor2D.h>
#include <vtkConvexHull2D.h>
#include <vtkDelaunay3D.h>
#include <vtkPNGReader.h>
#include <vtkImageMapper.h>
#include <vtkAppendFilter.h>
#include <vtkDataSetSurfaceFilter.h>
#include <vtkConnectedPointsFilter.h>
#include <vtkCamera.h>

#include "point.hpp"

#define vtkSPtr vtkSmartPointer
#define vtkSPtrNew(Var, Type) vtkSPtr<Type> Var = vtkSPtr<Type>::New();

using namespace std;

int main()
{
    vtkSPtrNew( points, vtkPoints );
    points->InsertNextPoint( 0, 0, 0 );
    points->InsertNextPoint( 0, 1, 0 );
    points->InsertNextPoint( 1, 0, 0 );
    points->InsertNextPoint( 1, 1, 0 );
    points->InsertNextPoint( 2, 1, 0 );
    points->InsertNextPoint( 2, 2, 0 );
    points->InsertNextPoint( 1, 2, 0 );
    vtkSPtrNew( polyData, vtkPolyData );
    polyData->SetPoints( points );

    vtkSPtrNew( hull2D, vtkConvexHull2D );
    hull2D->SetHullShape( 1 ); //0: BoundingRectangle or 1: ConvexHull.
    hull2D->SetInputData( polyData );
    hull2D->Update();

    Point pt[2] = { Point( 0.5, 0.5, 0 ), Point( -0.5, 0.5, 0 ) };
    auto data = hull2D->GetOutput();
    auto cell = data->GetCell( 0 );
    vtkIdList *cellPtIds = cell->GetPointIds();

    for( int i = 0; i < 2; ++i )
    {
        bool sameDir = true;
        for( int j = 0; j < cellPtIds->GetNumberOfIds()-1; ++j )
        {
            Point pt0( data->GetPoint( cellPtIds->GetId( j ) ) );
            Point pt1( data->GetPoint( cellPtIds->GetId( j+1 ) ) );
            Point pt2( data->GetPoint( cellPtIds->GetId( (j+2)%cellPtIds->GetNumberOfIds() ) ) );
            Point pt3( data->GetPoint( cellPtIds->GetId( (j+3)%cellPtIds->GetNumberOfIds() ) ) );

            auto dir0 = (pt0 - pt[i])^(pt1 - pt[i]);
            auto dir1 = (pt2 - pt[i])^(pt3 - pt[i]);
            if( dir0.Dot( dir1 ) < 0 )
            {
                sameDir = false;
                break;
            }
        }
        if( !sameDir )
        {
            cout << "outside point: " << i+1 << endl;
        }
    }

    return 0;
}
/*
outside point: 2
*/
Categories: MathVTK

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

3D Model Viewer: add grid plane and convex hull.
Add google translate tool at right-bottom position.

X
A prohibited operation
0
Would love your thoughts, please comment.x
()
x