Hello,

I have written an simple QuadTree for three days to improve the performance of MapWinGIS in edit mode. With the test data I'm using, about 16,000 lines, containing 76,000 points, the refresh time have remarkable reduced when I zoom into a small area, and it runs much faster than in regular mode.

In case it helps, I can send my code to the project.

My modification have affected the Shapefile.cpp, Shapfile.h, TableClass.cpp, Map.cpp, Map.h, MapWinGIS.odl

The affected methods are:


CShapefile:
EditInsertShapes (insert the new shape into the quadtree). Also modified the behavior that always insert new shape back to the list)
EditDeleteShapes (add quadtree mode's behavior that only remove the reference in quadtree. The deleted index will cache in deleteElement member, defined below)
StartEditingShapes (rebuilding the quadtree)
StopEditingShapes (real delete the marked deleted element for saving, and release the quadtree)
Close (modify the behavior)
SaveAs (modify the behavior, that "save as" without exiting edit mode)
SelectShapes (using quadtree to query in edit mode. fixed an bug about select shapes in edit mode, too.)
ReleaseMemshapes (release the quadtree)
~CShapefile (release "shpBounds"(fixed a bug) and quadtree)
CShapefile (make using quadtree as default)
Open (I make the edit mode as default mode in my local copy, the modification is optional)

CMap
DrawShapefile (use the quadtree to query in edit mode)

TableClass
SaveAs (modify the behavior, that save as without exiting edit mode)

New methods and members are:


CShapfile:

inline void GenerateQTree();
inline void TrimMemShapes();
STDMETHOD(QuickQueryInEditMode)(/*[in]*/IExtents * BoundBox,int ** Result, int* ResultCount);
STDMETHOD(get_UseQTree)(VARIANT_BOOL * pVal);
STDMETHOD(put_UseQTree)(VARIANT_BOOL pVal);
STDMETHOD(Save)(/*[in, optional]*/ ICallback * cBack, /*[out, retval]*/ VARIANT_BOOL * retval);

QTree* qtree;
BOOL useQTree;
vector<int> deleteElement;

in odl file added
[ id(50),helpstring("method QuickQueryInEditMode")] HRESULT QuickQueryInEditMode([in] IExtents *BoundBox, [in, out] int** Result,[in, out] int* ResultCount);
[propget, id(51), helpstring("property UseQTree In Edit Mode (default true)")] HRESULT UseQTree([out, retval] VARIANT_BOOL *pVal);
[propput, id(51), helpstring("property UseQTree In Edit Mode (default true)")] HRESULT UseQTree([in,defaultvalue(TRUE)] VARIANT_BOOL pVal);
[ id(52), helpstring("method Save")] HRESULT Save([in, optional] ICallback * cBack, [out, retval] VARIANT_BOOL * retval);



If these are useful, that will be my pleasure.

Fistly, I attatch my quad tree here.

Thanks for reading.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司



Edited 1 time(s). Last edit at 07/24/2009 03:52AM by neio.

New methods:


//Neio 2009/07/21
STDMETHODIMP CShapefile::QuickQueryInEditMode(IExtents *BoundBox, int ** Result, int* ResultCount )
{
AFX_MANAGE_STATE(AfxGetStaticModuleState());

if(isEditingShapes == FALSE)
{
//IN WRONG MODE
lastErrorCode = tkSHPFILE_NOT_IN_EDIT_MODE;

if( globalCallback != NULL ) globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
return S_OK;
}
if(useQTree == VARIANT_TRUE)
{
double xMin, yMin, zMin, mMin, xMax, yMax, zMax, mMax;
BoundBox->GetBounds(&xMin,&yMin,&zMin,&xMax,&yMax,&zMax);

vector<int> r = qtree->GetNodes(QTreeExtent(xMin,xMax,yMax,yMin));
int size = r.size();
*Result = new int;

//Copy the result
for(int i = 0; i < size;i ++)
{
(*Result)[ i ] = r[ i ];
}
*ResultCount = size;

return S_OK;
}
else
{

}


return S_OK;
}

//Neio 2009/07/21
STDMETHODIMP CShapefile::get_UseQTree(VARIANT_BOOL *pVal)
{
AFX_MANAGE_STATE(AfxGetStaticModuleState());
*pVal = (useQTree)?VARIANT_TRUE:VARIANT_FALSE;
return S_OK;
}

//Neio 2009/07/21
STDMETHODIMP CShapefile::put_UseQTree(VARIANT_BOOL pVal)
{
AFX_MANAGE_STATE(AfxGetStaticModuleState());

if(isEditingShapes == FALSE)
{
//IN WRONG MODE
lastErrorCode = tkSHPFILE_NOT_IN_EDIT_MODE;

if( globalCallback != NULL ) globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
return S_OK;
}
if (pVal == VARIANT_TRUE && useQTree == VARIANT_FALSE)
{
GenerateQTree();
useQTree = VARIANT_TRUE;
}
else if(pVal == VARIANT_FALSE && useQTree == VARIANT_TRUE)
{
//release
delete qtree;
qtree = NULL;
useQTree = VARIANT_FALSE;
}
else
{
if(pVal == VARIANT_TRUE)
useQTree = VARIANT_TRUE;
else
useQTree = VARIANT_FALSE;
}
return S_OK;
}

//Neio 2009/07/22
inline void CShapefile::GenerateQTree()
{
//clear the qtree if exists
if(qtree != NULL)
{
delete qtree;
}
//generate QTree
IExtents* ext;
double xm,xM,ym,yM,zm,zM;
get_Extents(&ext);
ext->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);
qtree = new QTree(QTreeExtent(xm,xM,yM,ym));

for( int i = 0; i < (int)memShapes.size(); i++ )
{
memShapes[ i ]->get_Extents(&ext);
ext->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);
QTreeNode node;
node.Extent.left =xm;
node.Extent.right = xM;
node.Extent.top = yM;
node.Extent.bottom = ym;
node.index = i;
qtree->AddNode(node);
}
}

//Neio 2009/09/22 Trim Shapes In Memory
inline void CShapefile::TrimMemShapes()
{
VARIANT_BOOL retval = VARIANT_TRUE;

sort(deleteElement.begin(),deleteElement.end());

for(register int i = deleteElement.size() - 1; i >=0;i--)
{
int j = deleteElement[ i ];
//start from larger index
memShapes[j]->Release();
memShapes.erase(memShapes.begin() + j);

numShapes--;
dbf->EditDeleteRow(j,&retval);

//For cacheExtents
if(cacheExtents)
{
shpBounds[j]->Release();
shpBounds.erase( shpBounds.begin() + j );
}
}
deleteElement.clear();



}

//Neio, 2009/07/23, add "Save" Method for saving without exiting edit mode
STDMETHODIMP CShapefile::Save(ICallback *cBack, VARIANT_BOOL *retval)
{
AFX_MANAGE_STATE(AfxGetStaticModuleState())
USES_CONVERSION;

if( isEditingShapes == FALSE )
{ lastErrorCode = tkSHPFILE_NOT_IN_EDIT_MODE;
*retval = VARIANT_FALSE;
if( cBack != NULL )
cBack->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
else if( globalCallback != NULL )
globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
return S_OK;
}



//Verify Shapefile Integrity
if( verifyMemShapes(cBack) == FALSE )
{ //Error Code is set in function
*retval = VARIANT_FALSE;
return S_OK;
}

shpfile = freopen(shpfileName,"wb+",shpfile);
shxfile = freopen(shxfileName,"wb+",shxfile);

if( shpfile == NULL || shxfile == NULL )
{
if( shxfile != NULL )
{ fclose( shxfile );
shxfile = NULL;
lastErrorCode = tkCANT_OPEN_SHX;
}
if( shpfile != NULL )
{ fclose( shpfile );
shpfile = NULL;
lastErrorCode = tkCANT_OPEN_SHP;
}
*retval = FALSE;
if( cBack != NULL )
cBack->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
else if( globalCallback != NULL )
globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
return S_OK;
}

//Force computation of Extents
IExtents * box = NULL;
get_Extents(&box);
box->Release();

TrimMemShapes();

writeShp(shpfile,cBack);
writeShx(shxfile,cBack);

GenerateQTree();

shpfile = freopen(shpfileName,"rb+",shpfile);
shxfile = freopen(shxfileName,"rb+",shxfile);

if( shpfile == NULL || shxfile == NULL )
{
if( shxfile != NULL )
{ fclose( shxfile );
shxfile = NULL;
lastErrorCode = tkCANT_OPEN_SHX;
}
if( shpfile != NULL )
{ fclose( shpfile );
shpfile = NULL;
lastErrorCode = tkCANT_OPEN_SHP;
}
*retval = FALSE;
if( cBack != NULL )
cBack->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
else if( globalCallback != NULL )
globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
return S_OK;
}


*retval = VARIANT_TRUE;
return S_OK;

}

====================================================================
Modified methods:
====================================================================
(StartEditingShapes)
.......
IShape * shp = NULL;
lastErrorCode = tkNO_ERROR;
IExtents * box=NULL;
double xm,ym,zm,xM,yM,zM;



long percent = 0, newpercent = 0;
double total = numShapes;

//Neio 2009/07/21
if(useQTree == VARIANT_TRUE){
get_Extents(&box);
box->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);
qtree = new QTree(QTreeExtent(xm,xM,yM,ym));

}

//Neio 2009/7/20
memShapes.resize(numShapes);
if(cacheExtents)
{
shpBounds.resize(numShapes);
}


for( int i = 0; i < numShapes; i++ )
{ get_Shape(i, &shp);
if( lastErrorCode != tkNO_ERROR )
{ if( cBack != NULL )
cBack->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
*retval = FALSE;
ReleaseMemoryShapes();

//Rob Cairns 20-Dec-05
//shp->Release(); This one is a invalid pointer because the call of "get_Shape" failed, and release a invalid pointer will crash the program. -- Lailin Chen
return S_OK;
}

//memShapes.push_back(shp);
memShapes[ i ] = shp;//Neio 07/21/09

if (cacheExtents) // lsu (07/04/09)
{ QuickExtents(i, &box);
box->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);

shpBounds[ i ] = box;//Neio 07/21/09 //shpBounds.push_back(box);
}
else
{
shp->get_Extents(&box);


//Neio 2009 07 21 Add
box->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);
}

//Neio 2009 07 21 QuadTree
if(useQTree == VARIANT_TRUE){
QTreeNode node;
node.Extent.left = xm;
node.Extent.right= xM;
node.Extent.top = yM;
node.Extent.bottom = ym;
node.index = i;
qtree->AddNode(node);
}


newpercent = (long)((i * 100 /total));
if( newpercent > percent )
{ percent = newpercent;
if( cBack != NULL )//Neio 2009 07 20
cBack->Progress(OLE2BSTR(key),percent,A2BSTR("Reading shapes into memory"));
else if( globalCallback !=NULL)
globalCallback->Progress(OLE2BSTR(key),percent,A2BSTR("Reading shapes into memory"));
}
}
.....


(StopEditingShapes, three similar places)

...
//Force computation of Extents
IExtents * box = NULL;
get_Extents(&box);
box->Release();

//Neio 2009 07 add
TrimMemShapes();

writeShp(saShpfile,cBack);
writeShx(saShxfile,cBack);

...

(EditInsertShapes)

...
else
{
//Neio, ShapeIndex would not use for input
*ShapeIndex = memShapes.size();
/*
if( *ShapeIndex < 0 )
*ShapeIndex = 0;
else if( *ShapeIndex > (int)memShapes.size() )
*ShapeIndex = memShapes.size();
*/


dbf->EditInsertRow( ShapeIndex, retval );
if( *retval == VARIANT_FALSE )
{ dbf->get_LastErrorCode(&lastErrorCode);
*retval = VARIANT_FALSE;
if( globalCallback != NULL )
globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
}
else
{ Shape->AddRef();

//Neio 2009/07/22 disable the ShapeIndex as Input
//memShapes.insert( memShapes.begin() + *ShapeIndex, Shape );
memShapes.push_back(Shape);

numShapes++;

// lsu 07/04/09 - caching of extents
//if (cacheExtents)
//{ IExtents * box;
// Shape->get_Extents(&box);
// box->AddRef();

//
// //shpBounds.push_back(box);
// shpBounds.insert( shpBounds.begin() + *ShapeIndex, box );
//}
//Neio remove these

//Neio modify the block upward 2009/07/22 when solar eclipse
if (cacheExtents || useQTree == VARIANT_TRUE)
{ IExtents * box;
Shape->get_Extents(&box);
box->AddRef();

//veryfy the new extent
double xm,ym,zm,xM,yM,zM;
box->GetBounds(&xm,&ym,&zm,&xM,&yM,&zM);
if(xm < minX) minX = xm;
if(xM > maxX) maxX = xM;
if(ym < minY) minY = ym;
if(yM > maxY) maxY = yM;

if(cacheExtents)
{
shpBounds.push_back(box);
}

if(useQTree == VARIANT_TRUE)
{
double xm,ym,zm,xM,yM,zM;
box->GetBounds(&xm,&ym,&zm, &xM,&yM,&zM);
QTreeNode node;
node.index = memShapes.size() - 1;
node.Extent.left = xm;
node.Extent.right = xM;
node.Extent.top = yM;
node.Extent.bottom = ym;
qtree->AddNode(node);
}

}

*retval = VARIANT_TRUE;
}
...

(EditDeleteShapes)

...
else
{

//Neio 2009/07/23 useQTree
if(useQTree == VARIANT_FALSE)
{
dbf->EditDeleteRow( ShapeIndex, retval );
}

if( *retval == VARIANT_FALSE )
{ dbf->get_LastErrorCode(&lastErrorCode);
*retval = VARIANT_FALSE;
if( globalCallback != NULL )
globalCallback->Error( OLE2BSTR(key), A2BSTR(ErrorMsg(lastErrorCode) ) );
}
else
{
//Neio modified for qtree 2009/07/21
if(useQTree == VARIANT_FALSE)
{
memShapes[ShapeIndex]->Release();
memShapes.erase( memShapes.begin() + ShapeIndex );
numShapes--;
}
else
{//when useQTree
bool success= qtree->RemoveNode(ShapeIndex);
deleteElement.push_back(ShapeIndex);

}


// lsu (07/03/09) releasing bounding box
if (cacheExtents)
{
//Neio modified for qtree 2009/07/21
if(useQTree == VARIANT_FALSE)
{
shpBounds[ShapeIndex]->Release();
shpBounds.erase( shpBounds.begin() + ShapeIndex );
}

}
*retval = VARIANT_TRUE;
}
}

return S_OK;
...


(SelectShapes)

...
if (ret != 0)
{
hasSpatialIndex = false;
//TODO throw error
}

}


vector<int> qtreeResult ;
//Neio fix the bug that select shapes in edit mode and add QTree
if(isEditingShapes != FALSE && useQTree == VARIANT_TRUE)
{
//s<<"useQtreeEnables"<<endl;
if(bPtSelection == true)
{
qtreeResult = qtree->GetNodes(QTreeExtent(b_minX,b_minX +1,b_minY + 1,b_minY));
}
else
qtreeResult = qtree->GetNodes(QTreeExtent(b_minX,b_maxX,b_maxY,b_minY));
}

int shapeVal;

//Neio fix(delete) and add qtree , 2009/07/22
//if ((isEditingShapes != FALSE && !hasSpatialIndex) || (isEditingShapes != FALSE && hasSpatialIndex && res->getLength() > 0)
// || (isEditingShapes != FALSE && useQTree == VARIANT_TRUE)
// )
{
int localNumShapes = numShapes;

//Neio 2009/07/22 fix and add qtree
if (hasSpatialIndex && isEditingShapes == FALSE)
localNumShapes = res->getLength();
else if(isEditingShapes != FALSE && useQTree == VARIANT_TRUE){
localNumShapes = qtreeResult.size();
}

//Point Selection
...


...
if( shpfiletype == SHP_POLYGON || shpfiletype == SHP_POLYGONZ || shpfiletype == SHP_POLYGONM )
{
for(i=0;i<localNumShapes;i++)
{
shapeVal = i;

//Neio fix the bug that select shapes in edit mode ,2009/07/22
if (hasSpatialIndex && isEditingShapes == FALSE)
{
shapeVal = (res->getValue(i)) - 1;
}
else if(isEditingShapes != FALSE && useQTree == VARIANT_TRUE)
{
shapeVal = qtreeResult[ i ];
}
else if(isEditingShapes != FALSE && useQTree == VARIANT_FALSE)
{
//do noting
}
...

if( shpfiletype == SHP_POINT || shpfiletype == SHP_POINTZ || shpfiletype == SHP_POINTM )
{
for(i=0;i<localNumShapes;i++)
{
shapeVal = i;

//Neio fix the bug that select shapes in edit mode ,2009/07/22
if (hasSpatialIndex && isEditingShapes == FALSE)
{
shapeVal = (res->getValue(i)) - 1;
}
else if(isEditingShapes != FALSE && useQTree == VARIANT_TRUE)
{
shapeVal = qtreeResult[ i ];
}
...

there are serveral similar code affected, I didn't list here


...
}
//Neio fix ,2009/07/22
if (hasSpatialIndex && isEditingShapes == FALSE)
delete res;
if( useQTree == VARIANT_TRUE && isEditingShapes != FALSE)
qtreeResult.clear();

if( selectResult.size() > 0 )
{
std::vector<long> finalSelectResult;
...



(ReleaseMemshapes)

...
shpBounds.clear();

//Neio 2009/07/21
//Clear the QTree
if(useQTree == VARIANT_TRUE)
{
delete qtree;
qtree = NULL;
}
return S_OK;
...


~CShapefile()
{
::SysFreeString(key);

//Close the files
if( shpfile != NULL )
fclose(shpfile);
shpfile = NULL;
if( shxfile != NULL )
fclose(shxfile);
shxfile = NULL;
//Close the dbf
if( dbf != NULL )
dbf->Release();
dbf = NULL;

//Neio 2009 09 23 for memory cleaning
/*for( int i = 0; i < (int)memShapes.size(); i++ )
{ int cnt = memShapes[ i ]->Release();
memShapes[ i ] = NULL;
}
memShapes.clear();*/
ReleaseMemoryShapes();
}


(DrawShapefile)

...
//Memory Based
else
{
VARIANT_BOOL cacheExtents;
ishp->get_CacheExtents(&cacheExtents);

//Neio 20090721 Add Query QuadTree
int* qtreeResult;
int qtreeResultCount = numberShapes; ///
IExtents * bBox = NULL;
VARIANT_BOOL _useQTree = VARIANT_FALSE;
ishp->get_UseQTree(&_useQTree);
if(_useQTree == VARIANT_TRUE){
CoCreateInstance( CLSID_Extents, NULL, CLSCTX_INPROC_SERVER, IID_IExtents, (void**)&bBox );
bBox->SetBounds(extents.left,extents.bottom,0,extents.right, extents.top,0);
ishp->QuickQueryInEditMode(bBox,&qtreeResult,&qtreeResultCount);
bBox->Release();
bBox=NULL;
}

...

if( shpfiletype == SHP_POINT || shpfiletype == SHP_POINTZ || shpfiletype == SHP_POINTM ||
shpfiletype == SHP_MULTIPOINT || shpfiletype == SHP_MULTIPOINTZ || shpfiletype == SHP_MULTIPOINTM )
{
register int i;
//Neio 2009/07/21 Add QuadTree Support
for(register int j = 0; j < qtreeResultCount ; j++)
//for( i = 0; i < numberShapes; i++ )
{
//Neio 2009/07/21
if(_useQTree == VARIANT_TRUE){
i = qtreeResult[j];
}
else
i = j;

ShapeInfo * si = sli->shapeInfo[ i ];

...
The similar codes for other type of shapefile are also affected

...
}

//Neio 2009/07/21 clearing
if(_useQTree == VARIANT_TRUE)
{
delete[] qtreeResult;
}
}


dc->SelectObject(slOldBrush);
dc->SelectObject(slOldPen);
...


(CShapefile::SaveAs)
}

//Neio 2009/07/23
TrimMemShapes();

writeShp(saShpfile,cBack);
writeShx(saShxfile,cBack);

//Neio 2009/07/23
GenerateQTree();

//Call SaveAs on the Dbf
//if unsuccessful then _unlink saShpfile, saShxfile
dbf->SaveAs(saDbffileName.AllocSysString(),cBack,retval);

....
prjfileName = saShpfileName.Left(saShpfileName.GetLength() - 3) + "prj";


//Neio remove belowing codes ,2009/07/23
//StopEditingShapes and StopEditingTable
//if( isEditingShapes != FALSE )
//{ //Release the memShapes
// for( int i = 0; i < (int)memShapes.size(); i++ )
// { memShapes[ i ]->Release();
// memShapes[ i ] = NULL;
// }
// memShapes.clear();
// isEditingShapes = FALSE;
//}
...

(TableClass::SaveAs)

...
//Flush all of the records
DBFClose(newdbfHandle);


//Neio remove belowing beavior , 2009/07/23
/*
if( isEditingTable != FALSE )
{ for( int i = 0; i < (int)memFields.size(); i++ )
{ memFields[ i ]->Release();
memFields[ i ] = NULL;
}
memFields.clear();
for( int j = 0; j < (int)memRows.size(); j++ )
{ if( memRows[j] != NULL )
delete memRows[j];
}
memRows.clear();
isEditingTable = FALSE;
}*/

Open(dbfFilename,cBack,retval);
*retval = VARIANT_TRUE;
return S_OK;
...


Thanks for reading it.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Hello, Neio.

You've done an amazing work. And of course it'll help.

Some questions:

Is it possible to use quad tree for regular mode? How difficult will it be to implement it?
Is it possible now in your version to have in-memory shapefiles without copy on the hard drive?
How does this method relates to spatial indexing introduced by Andrew Purkis (http://www.mapwindow.org/phorum/read.php?5,11535)?

I'm ready to test it. Thank you.

Regards Sergei

Hello, Sergei.

It's noting to do with the spatial indexing introduced by Andrew Pukis.

In regular mode, there is already an spatial index (using R*-Tree) exists (mentioned above, use CreateSpatialIndex to create it).

I build the quadtree when loading the data from hard drive (in StartEditingShapes), so the performance of loading is still a question.

My pleasure.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Neio,

I meant is it possible to extend your method on regular mode. For now it'll be needed to generate quad-tree on starting edit mode and to generate spatial index on turning to regular mode if we want a fast display and queries. It would be definately better to have one indexing for both modes. Advantages: faster pass between regular/edit mode, more simple coding inside and outside ocx.
I think we may consider such possibility. Thank you once more.

Regards Sergei

Hello, Sergei,

I know the problem you mentioned.

Actually, I made a change in my local copy that made the Edit Mode as default mode, and in this way, there are no switches between edit mode and regular mode.

I use the modified MapWinGIS.ocx like below:

sf.Open("shapfile.shp"); //already edit mode

AxMap1.AddLayer(sf, true); //display as edit mode

sf.EditInsertShape(.....);
sf.EditDeleteShape(.....);

sf.Save(); //If need the save the current change

sf.Close(); // without calling StopEditingShapes

By using these, I can save the time of passing between regular/edit mode.

Currently, I don't have any better idea about making the loading process (load the data from the disk) much faster. Do you have any idea to accelerate it?

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Hello Neio,

I see your point of view. Actually such model (permanent editing) suits me fine too. If nobody wants to read up-to-date version of the shapefile we edit nothing better is needed. For my application it's so. So I vote for it.

About speed of loading shapefile to the memory:

1. I noticed substantial (about two times) decrease in speed between versions 4.6 and 4.7 of ocx. I wasn't able to localize it's source, but I didn't explore it thoroughly. Maybe it makes sense to explore it better.

2. There is one more idea. Maybe it'll help.

Most significant losses of time while reading shapefile into memory are at point level I expect. Operations are very simple here but overhead because of COM usage is substantial. So to speed thing up I'd start with partial abolishing of CPoint class. It'd look something like this:

- In CShape class change type of allPoints deque from IPoint to simple structure of four variables (x,y,z,m) for easier and faster access.

- Add function ReadPointsInfo to CShape class. Pass shpfile handle and shape's offset to this function. Read values from file and write them directly to allPoints deque. The idea is to make it as fast as possible. The main part of procedure will go from CShape::GetShape.

- In CShapefile::GetShape after creating instance of shape use new ReadPointsInfo function to fill it.

- Add properties to CShape class to read values directly from allPoints not using Point class.
CShape::PointX(PointId)
CShape::PointY(PointId)
CShape::PointM(PointId)
CShape::PointZ(PointId)

- In CShape::GetPoint create an instance of point class if somebody wants it.

- In CShape::InsertPoint get information from point class instance and write it to the structure. Other implementation of InsertPoint can be added with PointId, x, y, z, m as parameters.

Regards Sergei

Hi Neio,

Would you like commit rights to the SVN repository for MapWinGIS? If so, please send me an e-mail at cmichaelis (at) happysquirrel.com with your full name and preferred username.

Thanks!
--Chris

Hi, Sergei and everyone

I agree with you that many simple operations, which can put into the succeeding operations, had consumed much time in loading process.

Months ago, I had written an very simple shapefile viewer(using C++ and OpenGL(software mode)) and tested in my notebook. The loading time is about 1+ seconds, compare to 7 seconds in MapWinGIS (my modified Edit Mode). And the fist time to show the whole map consumed about 2 seconds on generating the point classes for show. I think my method is close to your idea and it did reduce the time on reading process.

I some cases of use, we may not show the map after loaded the the shapefile. The reduced time by ignored the point level data parsing may suit this situation.

If we show the whole map after we loaded the shapefile, however, there will still much time wasted on parsing the point classes in drawing process.

I noticed the AutoCAD exists the similar problem in consuming of the time on loading. The AutoCAD do a lot of work in loading process to promise a great speed in other operations, such as drawing.

I think maybe we can provide an switch in MWGis for user to choose as to meet their own need. And I think it is the advantage or soul of OpenSource.

Thanks for reading and welcome to discuss and refine the idea.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Hi, Neio

Ok, here are further thoughts. There is little doubt that abolishing of point class will speed up loading of data from disk. Let's talk about drawbacks of such modification.

Abolishing of point class will lead to poorer performance of existing code in some cases. Extracts like following will work slower because an instance of IPoint class we'll be created on each call of get_Point.

// "old manner" work with points
IPoint * pnt = NULL;
double y, x;
shape->get_Point(i,&pnt);
pnt->get_X(&x);
pnt->get_Y(&y);
pnt->Release();

But if we replace it with the following lines it will work even faster than before. And also less lines of code are needed and it's important too.

// "new manner" work with points
double y, x;
shape->get_PointX(i,&x);
shape->get_PointY(i,&y);

So to keep speed of existing code changes like shown above are needed. And it's the main drawback of this modification I think.

Of course we may introduce additional switch (something like CShapefile::UsePointClass property) to keep things intact for existing code. But I don't like the idea. It'll make code inside ocx too comlicated.

Better approach, I think, is to rewrite access to point values in new manner in all time-consuming functions of ocx. It can be done in a day or so I belive. In my opinion it's acceptable price for faster loading (and saving) of shapefiles.

Certainly things will become clearer when we exactly know what gains and losses of speed are at stake.

What's your opinion, Neio?
Chris, Dan, Rob, Paul, what do you think?

Regards,
Sergei Leschinsky

Sergei, Neio,

I think we just should try it. If it is only a day work it isn't that bad if it is wasted.
We could start with timing some large shapefiles using v4.6, v4.7RC1, v4.7RC2, v4.7RC2+Quadtree and v4.7RC2+Quadtree+PointStructure.

After that we can say if it is an improvement or not. I'm in the process of building several VMs using the same XP version and the same hardware. Those could be used to test the changes.
A simple script with a few large shapefiles and we can measure.
As we say here in The Netherlands 'Measuring is knowing' (rhymes in Dutch ;))

How about that?

Paul

--
Don't forget to read the new documentation: www.mapwindow.org/documentation/mapwingis4.8
Join us Google+: MapWindow GIS Google+ Community
Join the MapWindow Group on LinkedIn! LinkedIn - MapWindow Group

Download the latest beta installer at:
tinyurl.com/mwMonthly 32-Bit
tinyurl.com/mwMonthlyx64 64-Bit
Follow me on Twitter MapWindow_nl to read when a new installer is published.

---
Paul Meems
The Netherlands
[www.bontepaarden.nl]
Release manager, configuration manager and
forum moderator of MapWindow GIS

Owner of MapWindow.nl - Support for
Dutch speaking users: www.mapwindow.nl

*******
Everything I say or write is my personal opinion and
not the opinion of the company I work for.
*******
View my profile on LinkedIn

If we are trying for efficiency, a small improvement on the above suggestion of separate calls for X and Y might be:

shape->get_PointXY(i,&x,&y);

Probably also want versions with z and/or m for shapefiles that have those.

If you want real speed on reading shapefiles, do not parse them very much as they are read. C++ should be a very easy language to read the shape structures as they exist on disk directly into the same structure in memory, you can read large sections in one operation instead of one byte or int at a time, just be sure to byte-swap a couple of wrong-endian parts before they get used.

Hi everyone,

I have committed my changes into SVN.

I agree that 'Measuring is knowing', and "tested data speaks the truth" is my guideline, too.

My test data of 16000 lines in shapefile. I have a small test application using C# to test the "EditMode","CacheExtents","UseQTree", but didn't record the time consuming exactly. Actually, I have little with this kind of test.

Generally, the combination of CacheExtents == true && UseQTree == true && EditMode == true runs fastest in Panning in part, but time the loading process (open-> startEditShapes-> AddLayer-> drawn on the screen) is the longest.

However, my test data can only tell one situation, and I think we need more exact test data to evaluate.

Hi Sergei, how is your PointClass going?

And hello Paul, how is your test going? Maybe we can share our scripts or test data, too.

Besides, hello Mark, it is a good idea of shape->get_PointXY(i,&x,&y), which remind me the method CExtents::GetBounds.

Waiting for good news.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Neio,

I think we should create a simple script which will test a few scenarios. That script and the used data should be shared. I'll start with that.

I'm having some trouble compiling the OCX with your new code.
I'm getting these errors:

Error	9	error LNK2019: unresolved external symbol "public: void __thiscall QTree::AddNode(struct QTreeNode const &)" (?AddNode@QTree@@QAEXABUQTreeNode@@@Z) referenced in function "public: virtual long __stdcall CShapefile::EditInsertShape(struct IShape *,long *,short *)" (?EditInsertShape@CShapefile@@UAGJPAUIShape@@PAJPAF@Z)	Shapefile.obj	MapWinGIS
Error	10	error LNK2019: unresolved external symbol "public: bool __thiscall QTree::RemoveNode(int)" (?RemoveNode@QTree@@QAE_NH@Z) referenced in function "public: virtual long __stdcall CShapefile::EditDeleteShape(long,short *)" (?EditDeleteShape@CShapefile@@UAGJJPAF@Z)	Shapefile.obj	MapWinGIS
Error	11	error LNK2019: unresolved external symbol "public: class std::vector<int,class std::allocator<int> > __thiscall QTree::GetNodes(class QTreeExtent)" (?GetNodes@QTree@@QAE?AV?$vector@HV?$allocator@H@std@@@std@@VQTreeExtent@@@Z) referenced in function "public: virtual long __stdcall CShapefile::SelectShapes(struct IExtents *,double,enum SelectMode,struct tagVARIANT *,short *)" (?SelectShapes@CShapefile@@UAGJPAUIExtents@@NW4SelectMode@@PAUtagVARIANT@@PAF@Z)	Shapefile.obj	MapWinGIS
Error	12	error LNK2019: unresolved external symbol "public: __thiscall QTree::QTree(class QTreeExtent)" (??0QTree@@QAE@VQTreeExtent@@@Z) referenced in function "public: virtual long __stdcall CShapefile::StartEditingShapes(short,struct ICallback *,short *)" (?StartEditingShapes@CShapefile@@UAGJFPAUICallback@@PAF@Z)	Shapefile.obj	MapWinGIS
Error	13	error LNK2019: unresolved external symbol "public: __thiscall QTree::~QTree(void)" (??1QTree@@QAE@XZ) referenced in function "public: void * __thiscall QTree::`scalar deleting destructor'(unsigned int)" (??_GQTree@@QAEPAXI@Z)	Shapefile.obj	MapWinGIS

It looks like I'm missing something. Do I need to recompile other parts of MW as well?

Thanks,

Paul

--
Don't forget to read the new documentation: www.mapwindow.org/documentation/mapwingis4.8
Join us Google+: MapWindow GIS Google+ Community
Join the MapWindow Group on LinkedIn! LinkedIn - MapWindow Group

Download the latest beta installer at:
tinyurl.com/mwMonthly 32-Bit
tinyurl.com/mwMonthlyx64 64-Bit
Follow me on Twitter MapWindow_nl to read when a new installer is published.

---
Paul Meems
The Netherlands
[www.bontepaarden.nl]
Release manager, configuration manager and
forum moderator of MapWindow GIS

Owner of MapWindow.nl - Support for
Dutch speaking users: www.mapwindow.nl

*******
Everything I say or write is my personal opinion and
not the opinion of the company I work for.
*******
View my profile on LinkedIn

Hello,

Paul,
you need to add QTree.H, QTree.cpp to the project.


Neio,

I have an exception in Qtree destructor (called from ReleaseMemShapes in Cshapefile destructor) if UseQTree is true in Cshapefile constructor.

Exception is here:
for(int i = 0;i<(int)nodes.size(); i++)
delete nodes[ i ];
nodes.clear();

When I turn UseQTree to VARIANT_FALSE in CShapefile constructor everything is ok.

Am I doing something wrong?

Also I think we must set cacheExtents to false by default as otherwise it can harm existing applications.

Regards,
Sergei

hello,

Paul,

Because my project file that specify the gdal directory has been changed, I did commit my project file into the SVN. You should update it in the SVN.

Sergei,

I didn't meet this kind of exception. Is you code from the latest SVN? Have you modified the code in QTree.cpp or QTree.h? Maybe there exists some bugs in my code, let's find it out. What's your test data?

And, I think you are right that I didn't think over carefully enough that whether my modification would harm some exist code or not.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Neio,

no changes whatsoever. I just added files to project and got this exception.
There following lines are in the main sub of my vb6 application:

Dim aObjects(1 to 8) As String
aObjects(1) = "MapWinGis.ShapeFile"

For i = 1 To UBound(aObjects)
sError = aObjects(i)
Set MyObject = VBA.CreateObject(aObjects(i)): Set MyObject = Nothing
Next i

And it's enough to generate exception.

Regards,
Sergei

I can compile again, so I'll start with the test script.
Which functions are affected by the Quadtree addition?

I was thinking of creating a script doing this:
Open file: ..\SampleData\Roads\200kTest.shp
Zoom in 3 times
zoom full extent
move/pan
select a shape and zoom to it (3 times)

Do any other functions need to be tested/timed?

--
Thanks,

Paul

--
Don't forget to read the new documentation: www.mapwindow.org/documentation/mapwingis4.8
Join us Google+: MapWindow GIS Google+ Community
Join the MapWindow Group on LinkedIn! LinkedIn - MapWindow Group

Download the latest beta installer at:
tinyurl.com/mwMonthly 32-Bit
tinyurl.com/mwMonthlyx64 64-Bit
Follow me on Twitter MapWindow_nl to read when a new installer is published.

---
Paul Meems
The Netherlands
[www.bontepaarden.nl]
Release manager, configuration manager and
forum moderator of MapWindow GIS

Owner of MapWindow.nl - Support for
Dutch speaking users: www.mapwindow.nl

*******
Everything I say or write is my personal opinion and
not the opinion of the company I work for.
*******
View my profile on LinkedIn

Hello, Sergei

I agree with you, and let us try this modification and evaluate it.

Best Regards,

Neio Zhou (ZHOU Conghui)
周聪辉
--------------------------------

Currently Master Candidate in Computer Science, The Chinese University of Hong Kong
现在为香港中文大学计算机科学硕士研究生

Quanzhou STrong Newtork Co. Ltd. , China from March 2009 to August 2010
2009年至2010年供职于中国泉州市视通光电网络有限公司

Hello, Neio

Problem disappeared when I initialized qtree with NULL in CShapefile constructor. I committed changes. Also I set cacheExtents, useQTree to false by default. In CShapefile::SaveAs GenerateQTree was called even if useQTree == false, I changed that to.

I work on other issues now and return to editing some time later. It’d be good if you’ll try the idea with point class.

Regards,
Sergei