[GIS] How to create points at shortest euclidean distance to other points

arcgis-10.0arcgis-desktopdistancemodelbuilder

So, I have a lot of points, and I need to site three new points so they will be at the shortest euclidean distance between all of the other points.

In other words, these three new points that I need to site will minimize the sum distance that the large group of points will be from any new point. I need to find the most efficient positioning the new points so the group of points will have the smallest total distance from a new point.

I'd like to be able to do this in Model Builder, or at least develop some kind of process that I can translate into Model Builder and possibly a python script later on (though I'm really bad at python). I assume this will involve some kind of iterative procedure, I just don't really know where to start.

Anyone have any awesome ideas?

P.S. This is in ArcGIS desktop 10.0

Edit: The idea is to site three new points that would be distributed to minimize total sum difference, thus they would, I guess, be taking a subset of the total point set to find the median center of them. It would look something like this (where the orange points would be something like the theoretical new locations):

Point Pattern

Edit 2: Okay, this has been confusing, but I was going on the description I was given for this particular problem. Yes, the minimized sum distance is the centroid. Mathematically, this is the best solution I've come up with so far, where the goal is the minimize Dist, but it just gets the total centroid:
Math

I've now talked to a spatial statistics instructor at an Ivy league university and two Ph.D.'s in math and we still can't figure out an appropriate answer that satisfies what I've been asked.

The only other thing that I can think to do is to somehow evenly divide the original points into three spatially equal parts and find their centroids, but I don't know how to do that.

Best Answer

If I am understanding your question correctly I think you can do this by calculating the median center of your point distribution and use that as your new point. Then repeat the process for the next two points.

Spatial Statistics>Measuring Geographic Distributions>Median Center

http://resources.arcgis.com/en/help/main/10.1/index.html#//005p00000019000000

I think you could accomplish this in Model Builder, although I have not used it in a while. It would be minimal code in Python if you run into issues with Model Builder.

model

Edit: I added a sample model you could use. I did this with a point dataset I created and it worked fine. What I think you will find is that the newly created points will be very close to one another (nearly coincident). Perhaps you have something else in mind for the additional points that I am not following.

Related Solutions

[GIS] Looking for a Tool to Calculate Distance Between Points (Between Layers)

Since you have ArcInfo, you can use the Near geoprocessing tool to find the distance. It's in ArcToolbox > Analysis > Proximity. Your input features will be Census tract centroids and your near features will be hospitals.

You may want to consider running the analysis simply on the Census tract polygons instead of their centroids. Tracts are large and often very odd-shaped, especially in rural areas. If you use centroids, you can end up with weird-looking results if elongated panhandles are close to a hospital but that tract's centroid is still far.

Moreover, you may also want to consider using a higher spatial resolution Census geography, e.g. block groups or blocks. American Community Survey data are available down to the block group resolution, and would probably produce better looking results.

Python – Calculate Distance Between Two Lat/Lon/Alt Points

As outlined in Calculating distance between two points using latitude longitude and altitude (elevation), Geopy: Calculating Distance, [GPS] Use pyproj to calculate distance, azimuth, and elevation from GPS latitude and longitude or Haversine formula that includes an altitude parameter?, you need to calculate first the 2D great-circle distance or the geodesic distance between the 2 points (distance between flat coordinates) and combine it with the difference in altitudes inside the Euclidean Formula for the 3D distance calculation. The solution assumes that the altitude is in meters and thus the great_circle's or geodesic's distance needs to be in meters

You can use GeoPy, pyproj or geographiclib for example.

With GeoPy

import numpy as np
# points with latitude,longitude units in degrees ,altitude unit in meters
pt1 =[35.3524,135.0302, 100]
pt2 =[35.3532,135.0305,500]
# 2D geodesic distance in meters
from geopy import distance 
distance_2d= distance.distance(pt1[:2], pt2[:2]).m
print(distance_2d)
92.85194331754518
# 3D euclidean distance
distance_3d = np.sqrt(distance_2d**2 + (pt2[2] - pt1[2])**2)
print(distance_3d)
410.6354628838632

With pyproj

from pyproj import Geod
g = Geod(ellps='WGS84')
# 2D distance in meters with longitude, latitude of the points
azimuth1, azimuth2, distance_2d = g.inv(pt1[1], pt1[0], pt2[1], pt2[0]) 
print(distance_2d)
92.85194331754519
# 3D euclidean distance
distance_3d = np.hypot(distance,pt2[2]-pt1[2])
print(distance_3d)
410.63546288386

With geographiclib

from geographiclib.geodesic import Geodesic
geod = Geodesic.WGS84 
g = geod.Inverse(pt1[0], pt1[1],pt2[0],pt2[1])
#2D geodesic distance in meters
print(g['s12'])
92.85194331754519
# 3D euclidean distance
distance_3d = np.hypot(g['s12'],pt2[2]-pt1[2])
print(distance_3d)
410.63546288386

Best Answer

Related Solutions

[GIS] Looking for a Tool to Calculate Distance Between Points (Between Layers)

Python – Calculate Distance Between Two Lat/Lon/Alt Points

Related Question